A 星算法总结

A 星算法FPGA EDA工具VPR布线器所采用的布线算法，面试滴滴的时候听说他们的路径规模用的也是A 星算法，感觉这个算法还蛮厉害的，对这个算法进行一个总结。
文章http://www.tuicool.com/articles/MJrYz26 对这个算法用语言描述的很好，搬运下：

　　A星寻路算法显然是用来寻路的，应用也很普遍，比如梦幻西游。。。算法的思路很简单，就是在bfs的基础上加了估值函数。它的核心是 F(x) = G(x) + H(x) 和open、close列表。
　　G(x)表示从起点到X点的消耗（或者叫移动量什么的），H(X)表示X点到终点的消耗的估值，F(x)就是两者的和值。open列表记录了可能要走的区域，close列表记录了不会再考虑的区域。我们每次都选F值最小的区域搜索，就能搜到一条到终点的最短路径，其中估值H越接近准确值，需要搜索的节点就越少。

A星算法的步骤：
{
将起点区域添加到open列表中，该区域有最小的和值。
重复以下：
　　将open列表中最小F值的区域X移除，然后添加到close列表中。
　　对于与X相邻的每一块可通行且不在close列表中的区域T：
如果T不在open列表中：添加到open列表，把X设为T的前驱
如果T已经在open列表中：检查 F 是否更小。如果是，更新Ｔ的F值和前驱
直到：
　　终点添加到了close列表。（已找到路径）
　　终点未添加到close列表且open列表已空。（未找到路径）
}

估值函数H(X)很有意思，不同的估值函数会带来不同的路径，因此在二维坐标系统下作了个小小的测试：