大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
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 是否更小。如果是,更新 T的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
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/188532.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...