POJ---2243 Knight Moves 使用A*算法的广度优先搜索

启发式搜索：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。

估价函数：从当前节点移动到目标节点的预估费用；这个估计就是启发式的。在寻路问题和迷宫问题中，我们通常用曼哈顿（manhattan）估价函数（下文有介绍）预估费用。

A*算法与BFS：可以这样说，BFS是A*算法的一个特例。对于一个BFS算法，从当前节点扩展出来的每一个节点（如果没有被访问过的话）都要放进队列进行进一步扩展。也就是说BFS的估计函数h永远等于0，没有一点启发式的信息，可以认为BFS是“最烂的”A*算法。

选取最小估价：如果学过数据结构的话，应该可以知道，对于每次都要选取最小估价的节点，应该用到最小优先级队列（也叫最小二叉堆）。在C++的STL里有现成的数据结构priority_queue，可以直接使用。当然不要忘了重载自定义节点的比较操作符。

A*算法的特点：A*算法在理论上是时间最优的，但是也有缺点：它的空间增长是指数级别的。

启发函数：f=g+h;其中g是起点到当前结点的直线距离，h是当前结点到目的结点的某种度量函数，在本题中采用曼哈顿距离。

#include  
#include  
#include  
#include  
#include  
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 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 "<
#include 
#include 
#include 
#include 
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 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 "<