A*算法——最好的寻路算法
步骤【例题】：
1，把起始格添加到开启列表。
2，重复如下的工作：
a) 寻找开启列表中F值最低的格子。我们称它为当前格。
b) 把它切换到关闭列表。
c) 对相邻的格中的每一个？
* 如果它不可通过或者已经在关闭列表中，略过它。反之如下。
* 如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
* 如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列表排序。
d)停止，当你
* 把目标格添加进了关闭列表(注解），这时候路径被找到，或者
* 没有找到目标格，开启列表已经空了。这时候，路径不存在。
3.保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。这就是你的路径。
自己理解:就是图上寻找路径的问题，每个格子计算估计函数f=g+h，g从他父节点继承过来的从起始点到当前节点的花费，加上h从当前节点到目标节点的估计花费例题中是曼哈顿距离，往预计小的方向找总会省时，找出最优解（当前）至少也可以达到剪枝，再过程中需要记录父节点，并维护他们的g和f，文章最后呢把a*和迪杰斯特拉进行对比。两者相似，但dij没有启发式，在搜索过程中会搜许多无用的“枝”，所以迪杰斯特拉会比a*慢那么一丢丢，但是dij可以计算出最近的距离，a*不能，就这样吧，还没做过题呢。
评论