最短路径算法——A*算法
A*算法是静态路网中求解最短路径最有效的直接搜索算法,也是解决许多搜索问题的有效算法,广泛应用于机器人路径搜索、游戏动画路径搜索等。它是图搜索算法的一种。
A*算法是一种启发式的搜索算法,它是基于深度优先算法(Depth First Search, DFS)和广度优先算法(Breadth First Search, BFS)的一种融合算法,按照一定原则确定如何选取下一个结点。
参考:A*寻路算法详解 #A星 #启发式搜索_哔哩哔哩_bilibili
【路径规划】全局路径规划算法——A*算法(含python实现 | c++实现)_a*算法路径规划-CSDN博客
A*算法使用一个路径优劣评价公式为:
f ( n ) = g ( n ) + h ( n )
f(n) 是从初始状态经由状态n到目标状态的代价估计,
g(n) 是从初始状态到状态n的实际代价,
h(n) 是从状态n到目标状态的最佳路径的估计代价。
算法步骤:
1.首先确定两个数组,openlist和closelist,openlist存储当前要处理的点的集合,closelist存储处理过的点,把起点加入 openList 。
重复如下过程:
2.遍历 openList ,查找 F 值最小的节点,把它作为当前要处理的节点。把这个节点移到 closeList 。
3.如果是在二维平面中,这个点周围会有八个相邻点,根据不同的类型做如下处理。
◆ 如果它是不可抵达(障碍物阻挡)的或者它在 closeList(已处理过的点) 中,忽略它;
◆如果它不在 openList 中,则把它加入 openList ,并且把当前方格设置为它的父节点(方面记录路径),记录该方格的f、g、h值。
◆ 如果它已经在 openList 中,检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好,用 g 值作参考,更小的 g 值表示这是更好的路径。如果g gg值更小,把该节点的父节点设置为当前方格,并重新计算它的 g 和 h 值。
停止搜索的情况有两种:
◆把终点加入到了openList 中,此时路径已经找到了
◆查找终点失败,并且 openList 是空的,此时没有路径。
保存路径。使用回溯的方法,从终点开始,每个方格沿着父节点移动直至起点,这就是最终搜索到的路径。
原文地址:https://blog.csdn.net/m0_71240643/article/details/140518383
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!