提示：文章写完后，目录可以自## 标题动生成，如何生成可参考右边的帮助文档
文章目录
一、A*算法的由来及应用背景
二、A*算法的基本原理
1.基本数学原理
A*算法作为启发式搜索算法，其更新估值F来进行搜索
: 当前节点的总代价
: 开始节点到当前节点的移动距离（实际代价）
: 从当前节点到终点的估计移动距离（估计代价）
计算G代价为从起点到当前节点经过的所有边的距离之和。
计算H代价的启发函数h包括曼哈顿距离、对角距离（切比雪夫距离）、欧几里德距离。
注意点：
1.计算H时，要忽略路径中的障碍物。这是对剩余距离的估算值，而不是实际值，因此H代价为估计代价。
2.在进行全局地图路径规划时，将环境信息转化为一个网格地图，其中每个网格表示环境的一个区域，障碍物的区域可以标记为障碍物网格，因此障碍物节点是已知的。
3.已知A*算法保证能够找到最短路径的条件是满足以下两个条件：
（1）启发函数h(n)必须满足单调性（即估计的代价不会超过从节点n到目标节点的实际代价），
（2）地图必须是可行的，即不存在无法通过的障碍物或无法到达的区域。
2.启发函数的选择
2.1曼哈顿距离
曼哈顿距离：，如下图：
2.2对角距离（切比雪夫距离）
对角距离（切比雪夫距离）：,如下图：
2.3欧几里德距离
欧几里德距离：，如下图：
注意：
启发函数跟拓展方式没有一定的捆绑关系，上述只是建议在哪种拓展节点的方式用何种启发函数。选择哪种启发函数取决于应用场景的具体情况，可以根据实际情况进行选择或者结合多种启发函数进行综合考虑。上述部分内容由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.实验结果
在的栅格地图中，障碍物自定产生，启发函数h分别采用曼哈顿距离和欧几里德距离，每个节点可以朝四个方向扩展。得到的路径规划如左图。其中阴影部分为加入过列表（或搜索过）的方格。
四、A*算法的总结
A*算法的优缺点
优点：
1.最优性：在满足一定条件下， A算法能够保证找到最短路径。
2.快速性：相对于其他搜索算法， A算法的搜索速度较快，因为它能够通过启发式函数来减少搜索的路径数。这使得A算法在处理大规模的搜索问题时非常高效。
3.适用性广泛： A算法可以用于解决各种路径搜索问题，例如在计算机游戏中寻找最佳路径、在机器人导航中寻找最短路径等等。
缺点：
1.启发式函数不易设计： A算法需要使用启发式函数来估算每个节点到目标节点的距离，但是启发式函数2.的设计并不是一件容易的事情。如果启发式函数设计不好，那么搜索效率将会受到很大的影响。
存储空间占用较大： A算法需要存储搜索过程中的节点信息，因此当搜索的状态空间较大时，它需要占用较大的存储空间。
3.可能陷入局部最优解：虽然A算法能够保证找到最短路径，但是当启发式函数不够好时， A算法可能会陷入局部最优解，而无法找到全局最优解。
文章出处登录后可见！
