摘要：
在启发式搜索中，位置估计非常重要。A*算法和BFS：可以说，BFS是A*算法的一个特例。A*算法的特点：A*算法理论上是时间最优的，但它也有一个缺点：它的空间增长是指数级的。4,4,1A*算法步骤是：将起始晶格添加到打开列表中。
启发式搜索：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
估价函数：从当前节点移动到目标节点的预估费用；这个估计就是启发式的。在寻路问题和迷宫问题中，我们通常用曼哈顿（manhattan）估价函数（下文有介绍）预估费用。
A*算法与BFS：可以这样说，BFS是A*算法的一个特例。对于一个BFS算法，从当前节点扩展出来的每一个节点（如果没有被访问过的话）都要放进队列进行进一步扩展。也就是说BFS的估计函数h永远等于0，没有一点启发式的信息，可以认为BFS是“最烂的”A*算法。
选取最小估价：如果学过数据结构的话，应该可以知道，对于每次都要选取最小估价的节点，应该用到最小优先级队列（也叫最小二叉堆）。在C++的STL里有现成的数据结构priority_queue，可以直接使用。当然不要忘了重载自定义节点的比较操作符。
A*算法的特点：A*算法在理论上是时间最优的，但是也有缺点：它的空间增长是指数级别的。
启发函数：f=g+h;其中g是起点到当前结点的直线距离，h是当前结点到目的结点的某种度量函数，在本题中采用曼哈顿距离。
选择路径中经过哪个方格的关键是下面这个等式：F = G + H这里：
- G = 从起点A，沿着产生的路径，移动到网格上指定方格的移动耗费。
- H = 从网格上那个方格移动到终点B的预估移动耗费。这经常被称为启发式的，可能会让你有点迷惑。这样叫的原因是因为它只是个猜测。我们没办法事先知道路径的长度，因为路上可能存在各种障碍(墙，水，等等)。
4,4,1 A*算法步骤为：
- 把起始格添加到开启列表。
- 重复如下的工作：
- 寻找开启列表中F值最低的格子。我们称它为当前格。
- 把它切换到关闭列表。
- 对相邻的格中的每一个？
- 如果它不可通过或者已经在关闭列表中，略过它。反之如下。
- 如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
- 如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列表排序。
- 停止，当你
- 把目标格添加进了关闭列表，这时候路径被找到，或者
- 没有找到目标格，开启列表已经空了。这时候，路径不存在。
- 保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。这就是你的路径。
//Poj2243 #include<iostream> #include<queue> #include<stdlib.h> using namespace std; char ss[3]; char ee[3]; typedef struct node { int x; int y; int steps; int g; int h; int f; friend bool operator < (const node & a,const node &b); }node; inline bool operator < (const node & a,const node &b) { return a.f>b.f; } int d[8][2]={{-2,1},{-2,-1},{-1,-2},{-1,2},{2,-1},{2,1},{1,-2},{1,2}}; int visited[8][8]; node s; node e; int in(node n) { if(n.x<0||n.y<0||n.x>7||n.y>7) return 0; return 1; } int Heuristic(const node &a){ return (abs(a.x-e.x)+abs(a.y-e.y))*10; }//曼哈顿（manhattan）估价函数 priority_queue<node> q; //最小优先级队列(开启列表) 这里有点优化策略，因为我发现如果把q //放在Astar函数里头的话，代码跑起来是157MS，放在外面的话是47MS，有显著的区别 int Astar() { while(!q.empty())q.pop(); memset(visited,0,sizeof(visited)); q.push(s); while(!q.empty()) { node front=q.top(); node t; q.pop(); visited[front.x][front.y]=1; if(front.x==e.x && front.y==e.y) return front.steps; for(int i=0;i<8;i++){ t.x=front.x+d[i][0]; t.y=front.y+d[i][1]; if(in(t) && visited[t.x][t.y]==0){ t.g=23+front.g; t.h=Heuristic(t); t.f=t.g+t.h; t.steps=front.steps+1; q.push(t); } } } } int main(int argc, char *argv[]) { //freopen("in.txt","r",stdin); while(scanf("%s %s",ss,ee)==2) { s.x=ss[0]-'a'; s.y=ss[1]-'1'; e.x=ee[0]-'a'; e.y=ee[1]-'1'; s.steps=0; s.g=0; s.h=Heuristic(s); s.f=s.g+s.h; if(s.x==e.x&&s.y==e.y) printf("To get from %s to %s takes 0 knight moves. ",ss,ee); else printf("To get from %s to %s takes %d knight moves. ",ss,ee,Astar()); } return 0; }