最短路径算法——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 是空的，此时没有路径。

保存路径。使用回溯的方法，从终点开始，每个方格沿着父节点移动直至起点，这就是最终搜索到的路径。