A 星算法总结_数据结构与算法知识点总结

大家好，又见面了，我是你们的朋友全栈君。

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)很有意思，不同的估值函数会带来不同的路径，因此在二维坐标系统下作了个小小的测试：

曼哈顿距离

在二维平面中 点（x1，y1）和点（x2， y2）的曼哈顿距离：H(X)= abs（x1-x2）+ abs（y1 – y2）。其中红色的点表示考察过的点，绿色的点表示最终生成的路径。

曼哈顿距离

殴几里得距离

在二维平面中 点（x1，y1）和点（x2， y2）的曼哈顿距离：H(X)= sqrt（（x1-x2）* （x1-x2）+ （y1 – y2）*（y1 – y2））

这里写图片描述

水平距离

这是测着玩的： H(X)= abs(x1 – x2）

这里写图片描述

垂直距离

这也是我测着玩的：H(X) = abs（y1 – y2）

这里写图片描述

迪杰斯特拉算法

令H(x) = 0， A星算法就变成了 迪杰斯特拉算法，想想还真是！！

这里写图片描述

契比雪夫距离

H(X)= max( abs(x1 – x2), abs(y1 – y2) )

这里写图片描述

看来加上H（X）效果大有改善！！ 代码为原创：http://download.csdn.net/detail/wjwever1/9669482

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/188532.html原文链接：https://javaforall.cn