A*算法

A*算法最初发表于1968年《A Formal Basis for the Heuristic Determination of Minimum Cost Paths》，由Stanford研究院的Peter Hart, Nils Nilsson以及Bertram Raphael发表。它可以被认为是Dijkstra算法的扩展：在 Dijkstra 的基础上加入了启发函数

$$F(n) = G(n) +H(n)$$

F(n)是节点n的综合距离。当我们选择下一个要遍历的节点时，我们总会选取综合优距离最小的节点。
G(n)是节点n到源点的距离。
H(n)是节点n到终点的预估距离，这也就是A*算法的启发函数。

启发函数

• 如果H(n)始终小于等于节点n到终点的距离，则A*算法保证一定能够找到最短路径。但是当H(n)的值越小，算法将遍历越多的节点，也就导致算法越慢。
• 在极端情况下，当启发函数H(n)始终为0，则将由G(n)决定节点的优先级，此时算法就退化成了Dijkstra算法。
• 如果H(n)完全等于节点n到终点的距离，则A*算法将找到最佳路径，并且速度很快。可惜的是，并非所有场景下都能做到这一点。因为在没有达到终点之前，我们很难确切算出距离终点还有多远。
• 如果H(n)的值比节点n到终点的距离要大，则A*算法不能保证找到最短路径，不过此时会很快。
• 在另外一个极端情况下，如果H(n)相较于G(n)大很多，则此时只有H(n)产生效果，这也就变成了最佳优先搜索。

由上面这些信息我们可以知道，通过调节启发函数我们可以控制算法的速度和精确度。因为在一些情况，我们可能未必需要最短路径，而是希望能够尽快找到一个路径即可。这也是A*算法比较灵活的地方。

1. A*算法的基本步骤

解释1 （参考：路径规划之 A* 算法）

• 初始化open_set和close_set；
• 将起点加入open_set中，并设置优先级为0（优先级最高）；
• 如果open_set不为空，则从open_set中选取优先级最高的节点n：
  • 如果节点n为终点，则：
    • 从终点开始逐步追踪parent节点，一直达到起点；
    • 返回找到的结果路径，算法结束；
  • 如果节点n不是终点，则：
    • 将节点n从open_set中删除，并加入close_set中；
    • 遍历节点n所有的邻近节点：
      • 如果邻近节点m在close_set中，则：
        • 跳过，选取下一个邻近节点
      • 如果邻近节点m也不在open_set中，则：
        • 设置节点m的parent为节点n
        • 计算节点m的优先级
        • 将节点m加入open_set中
      • 如果邻近节点m已经在open_set中，则
        • 检查这条路径是否更优，也就是说经由节点n到达节点m是否具有更小的 G 值。如果没有，不做任何操作。有则设置节点m的parent为节点n并计算节点m的优先级。

解释2 （参考：A星算法详解）

• A. 把起点加入 open list 。
• B. 重复如下过程：
  • a. 遍历 open list ，查找 F 值最小的节点，把它作为当前要处理的节点。
  • b. 把这个节点移到 close list 。
  • c. 对当前方格的 8 个相邻方格的每一个方格？
    • 如果它是不可抵达的或者它在 close list 中，忽略它。否则，做如下操作。
    • 如果它不在 open list 中，把它加入 open list ，并且把当前方格设置为它的父亲，记录该方格的 F ， G 和 H 值。
    • 如果它已经在 open list 中，检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好，用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样，把它的父亲设置为当前方格，并重新计算它的 G 和 F 值， H 值不变。如果你的 open list 是按 F 值排序的话，改变后你可能需要重新排序。
  • d. 停止，当你
    • 把终点加入到了 open list 中，此时路径已经找到了，或者
    • 查找终点失败，并且 open list 是空的，此时没有路径。
• C. 保存路径。从终点开始，每个方格沿着父节点移动直至起点，这就是你的路径。

特点：

• 根据启发函数的特点，A*算法不一定具备最优性
• 适用范围：适用于静态环境和低维度路径规划，特别适用于事先已知部分环境的场景，例如车辆拥有部分道路信息时，A算法可以利用启发式来减少不必要的状态遍历

2. A*算法和Dijkstra算法对比

• 两种算法均为静态规划算法(外界环境不变，计算最短路径)。
• Dijkstra算法计算源点到其他所有点的最短路径长度，A*关注源点到终点的最短路径。
• Dijkstra算法建立在较为抽象的图论层面，A*算法可以更轻松地用在诸如游戏地图寻路中。
• Dijkstra算法的实质是广度优先搜索(因为在搜索到目标点之前，搜索了所有可能的点)，是一种发散式的搜索，所以空间复杂度和时间复杂度都比较高。对路径上的当前点，A*算法不但记录其到源点的代价，还计算当前点到目标点的期望代价，是一种启发式算法，也可以认为是一种深度优先的算法。
• 由第一点，当目标点很多时，A*算法会带入大量重复数据和复杂的估价函数，所以如果不要求获得具体路径而只比较路径长度时，Dijkstra算法会成为更好的选择。
  ————————————————
  版权声明：本文为CSDN博主「hopeping128」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
  原文链接：https://blog.csdn.net/hopeping128/article/details/78960326 （链接中含动图说明）

文件说明

|--A_star_Matlab 基于栅格地图的A_star算法的Matlab实现
参考：B站 小黎的Ally：路径规划与轨迹跟踪系列算法学习_第4讲_A*算法
|--- A_star_python.ipynb 基于栅格地图的A_star算法的python实现(将原作者的python文件转为ipynb)
参考：Github: zhm-real/PathPlanning

其他参考