啟發式搜索：啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無畏的搜索路徑，提到了效率。在啟發式搜索中，對位置的估價是十分重要的。采用了不同的估價可以有不同的效果。
估價函數：從當前節點移動到目標節點的預估費用；這個估計就是啟發式的。在尋路問題和迷宮問題中，我們通常用曼哈頓（manhattan）估價函數（下文有介紹）預估費用。
A*算法與BFS：可以這樣說，BFS是A*算法的一個特例。對於一個BFS算法，從當前節點擴展出來的每一個節點（如果沒有被訪問過的話）都要放進隊列進行進一步擴展。也就是說BFS的估計函數h永遠等於0，沒有一點啟發式的信息，可以認為BFS是“最爛的”A*算法。
選取最小估價：如果學過數據結構的話，應該可以知道，對於每次都要選取最小估價的節點，應該用到最小優先級隊列（也叫最小二叉堆）。在C++的STL裡有現成的數據結構priority_queue，可以直接使用。當然不要忘了重載自定義節點的比較操作符。
A*算法的特點：A*算法在理論上是時間最優的，但是也有缺點：它的空間增長是指數級別的。
啟發函數：f=g+h;其中g是起點到當前結點的直線距離，h是當前結點到目的結點的某種度量函數，在本題中采用曼哈頓距離。
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <cstring>
using namespace std;
struct node{
int x,y,step;
int f,g,h;
bool operator<(const node & n)const { //優先隊列，需要重載操作符
return step>n.step;
}
}k;
int endx,endy;
int Heuristic(const node &a){ //manhattan估價函數
return (abs(a.x-endx)+abs(a.y-endy))*10;
}
bool isbond(const node &a){ //判斷是否是邊界
if(a.x<0||a.y>=8||a.x>=8||a.y<0)return 1;
return 0;
}
bool visit[10][10];
int dir[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};
priority_queue<node> Q; //8個方向
int bfs()
{
while(!Q.empty())Q.pop();
Q.push(k);
node p,q;
while(!Q.empty())
{
p=Q.top();
Q.pop();
if(p.x==endx&&p.y==endy){
return p.step;
}
visit[p.x][p.y]=1;
for(int i=0;i<8;i++)
{
q.x=p.x+dir[i][0];
q.y=p.y+dir[i][1];
if(visit[q.x][q.y])continue;
if(isbond(q))continue;
q.g=p.g+23;
q.h=Heuristic(q);
q.step=p.step+1;
Q.push(q);
}
}
}
int main()
{
string a,b;
while(cin>>a>>b)
{
k.x=a[0]-'a';
k.y=a[1]-'1';
endx=b[0]-'a';
endy=b[1]-'1';
k.step=k.g=0;
k.h=Heuristic(k);
k.f=k.g+k.h;
memset(visit,0,sizeof(visit));
cout<<"To get from "<<a<<" to "<<b<<" takes ";
cout<<bfs()<<" knight moves."<<endl;
}
return 0;
}
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <cstring>
using namespace std;
struct node{
int x,y,step;
int f,g,h;
bool operator<(const node & n)const { //優先隊列，需要重載操作符
return step>n.step;
}
}k;
int endx,endy;
int Heuristic(const node &a){ //manhattan估價函數
return (abs(a.x-endx)+abs(a.y-endy))*10;
}
bool isbond(const node &a){ //判斷是否是邊界
if(a.x<0||a.y>=8||a.x>=8||a.y<0)return 1;
return 0;
}
bool visit[10][10];
int dir[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};
priority_queue<node> Q; //8個方向
int bfs()
{
while(!Q.empty())Q.pop();
Q.push(k);
node p,q;
while(!Q.empty())
{
p=Q.top();
Q.pop();
if(p.x==endx&&p.y==endy){
return p.step;
}
visit[p.x][p.y]=1;
for(int i=0;i<8;i++)
{
q.x=p.x+dir[i][0];
q.y=p.y+dir[i][1];
if(visit[q.x][q.y])continue;
if(isbond(q))continue;
q.g=p.g+23;
q.h=Heuristic(q);
q.step=p.step+1;
Q.push(q);
}
}
}
int main()
{
string a,b;
while(cin>>a>>b)
{
k.x=a[0]-'a';
k.y=a[1]-'1';
endx=b[0]-'a';
endy=b[1]-'1';
k.step=k.g=0;
k.h=Heuristic(k);
k.f=k.g+k.h;
memset(visit,0,sizeof(visit));
cout<<"To get from "<<a<<" to "<<b<<" takes ";
cout<<bfs()<<" knight moves."<<endl;
}
return 0;
}
