A*算法的介绍

提示：文章写完后，目录可以自## 标题动生成，如何生成可参考右边的帮助文档

文章目录

• 一、A*算法的由来及应用背景
• 二、A*算法的基本原理
• • 1.基本数学原理
  • 2.启发函数的选择
  • • 2.1曼哈顿距离
    • 2.2对角距离（切比雪夫距离）
    • 2.3欧几里德距离
• 三、A*算法的程序实现
• • 1.算法逻辑
  • 2.实验结果
• 四、A*算法的总结
• • A*算法的优缺点

一、A*算法的由来及应用背景

二、A*算法的基本原理

1.基本数学原理

A*算法作为启发式搜索算法，其更新估值F来进行搜索
$$F=G+H$$
$F$: 当前节点的总代价
$G$: 开始节点到当前节点的移动距离（实际代价）
$H$: 从当前节点到终点的估计移动距离（估计代价）

计算G代价为从起点到当前节点经过的所有边的距离之和。
计算H代价的启发函数h包括曼哈顿距离、对角距离（切比雪夫距离）、欧几里德距离。

注意点：
1.计算H时，要忽略路径中的障碍物。这是对剩余距离的估算值，而不是实际值，因此H代价为估计代价。

2.在进行全局地图路径规划时，将环境信息转化为一个网格地图，其中每个网格表示环境的一个区域，障碍物的区域可以标记为障碍物网格，因此障碍物节点是已知的。

3.已知A*算法保证能够找到最短路径的条件是满足以下两个条件：
（1）启发函数h(n)必须满足单调性（即估计的代价不会超过从节点n到目标节点的实际代价），
（2）地图必须是可行的，即不存在无法通过的障碍物或无法到达的区域。

2.启发函数的选择

2.1曼哈顿距离

曼哈顿距离： D = ∣ x2− x1∣ + ∣ y2− y1∣D=|x_{2}-x_{1}|+|y_{2}-y_{1}|D=∣x2​−x1​∣+∣y2​−y1​∣，如下图：

如果图形中只允许朝上下左右四个方向移动，则可以使用曼哈顿距离。计算从当前栅格横向或纵向移动到达目标所经过的方格数。

例如在上图中中心节点可以朝着上下左右拓展，这时采用曼哈顿距离作为启发函数更有效。当拓展节点存在障碍物时：

A*算法会根据地图中的网格来判断每个节点的状态，即是否为障碍物节点。当算法扩展节点时，如果该节点是障碍物节点，则不会将其加入到待扩展节点集合中，从而避免沿着该节点继续搜索，这样就能够有效地避免穿越障碍物。

2.2对角距离（切比雪夫距离）

对角距离（切比雪夫距离）： D = m a x ( ∣ x2− x1∣ + ∣ y2− y1∣ )D=max(|x_{2}-x_{1}|+|y_{2}-y_{1}|)D=max(∣x2​−x1​∣+∣y2​−y1​∣),如下图：

如果图形中允许朝八个方向移动，则可以使用对角距离。对角距离更适合处理允许斜向移动的情况，因为它考虑了斜向移动时的额外距离，使得估算更加准确。

当拓展节点存在障碍物时：

2.3欧几里德距离

欧几里德距离： D =( x2− x1)2+ ( y2− y1)2D=\sqrt{(x_{2}-x_{1})^2+(y_{2}-y_{1})^2}D=(x2​−x1​)2+(y2​−y1​)2 ​，如下图：

允许朝任何方向移动则可以使用欧几里德距离。欧几里德距离直接计算两点之间的距离，更符合实际情况.。

注意：
启发函数跟拓展方式没有一定的捆绑关系，上述只是建议在哪种拓展节点的方式用何种启发函数。选择哪种启发函数取决于应用场景的具体情况，可以根据实际情况进行选择或者结合多种启发函数进行综合考虑。上述部分内容由ChatGPT-plus4.0给出，如有错误请大家自行判断。

三、A*算法的程序实现

1.算法逻辑

1.初始化开始节点S，最终节点G，初始化列表open，closed，初始化全局地图(网格地图)
2.从开始节点S出发，把S作为一个待检查的方格，放入open列表
3.寻找开始节点S周围可以到达的方格（最多八个），将它们放入open列表，并设置它们的父节点为S
4.从“open列表”中删除开始节点S，并将S放入到closed列表中
5.计算每个周围方格的F值 F=G+H
6.从open列表中选择F值最小的方格a，将其从open列表放入到closed列表中
7.检查a所有邻近的方格
1）障碍物和close列表中的方格不考虑
2）如果这些方格不在open列表中，将它们加入open列表，计算这些方格的F值，并设置父节点为a
3）如果某相邻的方格c已经在open列表中，计算新的路径从S到达方格c（即经过a的路径）， 判断是否需要更新父节点和F值：如果新节点c的G值更低，则修改父方格为方格a，重新计算F值，H值不需要改变（因为方格到达目标点的预估代价是固定的）,如果新节点c的G值比较高，则说明新的路径代价更高，则值不做改变（G值不变也不更新）
8.继续从open列表中找出F值最小的，从open列表中删除，添加到close列表，再继续找出周围可以到达的方块，如此循环
9.结束判断：当open列表中出现目标方块G时，说明路径已找到；当open列表中没有了数据，说明没有合适路径。

2.实验结果

在$20\ast 20$的栅格地图中，障碍物自定产生，启发函数h分别采用曼哈顿距离和欧几里德距离，每个节点可以朝四个方向扩展。得到的路径规划如左图。其中阴影部分为加入过列表（或搜索过）的方格。

当我们增大网格地图，此时利用A进行路径规划又会得到怎么的结果呢
在$200\ast 200$的栅格地图中，障碍物随机产生，障碍物覆盖率占地图的20%，启发函数h分别采用曼哈顿距离和欧几里德距离，得到的路径规划如左图。
A算法的启发式搜索过程中启发函数的估计值越接近真实值，规划效率越高。
在网格地图中，每个节点可以朝八个方向扩展，此时曼哈顿距离更能准确地反映两个节点之间的距离。相比之下，欧几里德距离计算的H值偏小，同时其需要进行开方运算，耗时较长。

有小伙伴需要程序的可以私我。

四、A*算法的总结

A*算法的优缺点

优点：
1.最优性：在满足一定条件下， A算法能够保证找到最短路径。
2.快速性：相对于其他搜索算法， A算法的搜索速度较快，因为它能够通过启发式函数来减少搜索的路径数。这使得A算法在处理大规模的搜索问题时非常高效。
3.适用性广泛： A算法可以用于解决各种路径搜索问题，例如在计算机游戏中寻找最佳路径、在机器人导航中寻找最短路径等等。

缺点：
1.启发式函数不易设计： A算法需要使用启发式函数来估算每个节点到目标节点的距离，但是启发式函数2.的设计并不是一件容易的事情。如果启发式函数设计不好，那么搜索效率将会受到很大的影响。
存储空间占用较大： A算法需要存储搜索过程中的节点信息，因此当搜索的状态空间较大时，它需要占用较大的存储空间。
3.可能陷入局部最优解：虽然A算法能够保证找到最短路径，但是当启发式函数不够好时， A算法可能会陷入局部最优解，而无法找到全局最优解。