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

文章目录

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

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

二、A*算法的基本原理

1.基本数学原理

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

计算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=x2x1+y2y1,如下图:

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

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

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

2.2对角距离(切比雪夫距离)

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

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

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

2.3欧几里德距离

欧几里德距离: D =( x2− x1)2+ ( y2− y1)2D=\sqrt{(x_{2}-x_{1})^2+(y_{2}-y_{1})^2}D=(x2x1)2+(y2y1)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 ∗ 2020*202020的栅格地图中,障碍物自定产生,启发函数h分别采用曼哈顿距离和欧几里德距离,每个节点可以朝四个方向扩展。得到的路径规划如左图。其中阴影部分为加入过列表(或搜索过)的方格。

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

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


四、A*算法的总结

A*算法的优缺点

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

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