A*算法详解（新手入门）——图文并茂，学习笔记分享

前言

本文是博主在学习A*算法时做的一个小案例，有不懂的地方可以私信博主一起讨论学习，由于博主水平有限，可能存在部分知识点遗漏或书写不够严谨，欢迎各位志同道合的朋友批评指教，博主定当虚心学习，感谢各位阅读。

一. 基本概念

A*算法在Dijkstra算法的基础上引入了启发函数，启发函数是对当前节点到目标节点所需代价的预估，有助于提高搜索速度。相较于Dijkstra算法，A*算法搜索最短路径的效率更高。启发式函数一般使用曼哈顿距离、欧几里德距离。原理：从起点开始不断向目标点的方向遍历（常见的遍历方式分为八邻域、四邻域），并记录下每一个遍历点的父节点（找到目标点后回溯路径），反复循环，直到搜索到目标点后停止，再从目标点回溯起点，找到成本最小的路径。

优点：启发式函数能提高算法的运行效率，更快的找到最优路径。

缺点：地图尺寸过大或精度过高时，需要搜索的节点数量较多，搜索速度慢。

成本函数： 

是从起点到目标点的成本估计； 是起点到达中间点的实际成本；中间点到目标点的估计距离。

假设起点：；中间点：；目标点：。

实际距离： ；

曼哈顿距离（如图1）：；

图1

欧几里德距离（如图2）：

图2

二. 寻路实例

这里通过一个实例来记录我学习A*寻路算法的全过程：以采用曼哈顿距离为估计代价的成本函数为例（因为欧几里德距离的计算涉及到平方和开根号，步骤更加复杂，对算力的要求更高，所以一般采用曼哈顿距离），深蓝色为障碍物，两个绿色点分别为起始点和目标点（前文已做假设），将横直线移动一格的距离记作10，斜移一格的距离记作14。

在实例中建立两个集合，分别是openlis和closelist。openlis用于记录所有已经遍历过的点（图中的红色格子），这些点可以被重复遍历并更新距离成本；closelist用于记录在当前位置所有遍历点中距离成本最小的点（来源于closelist集合，图中的浅蓝色格子），且放入closelist集合里的点不再重复遍历更新。

1.遍历起始点附近邻域的八个点（由于起始点位置原因例中只有五个），并通过代价函数计算邻域中每一个点的距离成本（已写在每个格子中），此轮遍历距离成本最小的点为10+130=144，将此点放入closelist中，并标记为浅蓝色，如图3。

图3

2.遍历图3中距离成本最小的点的附近邻域，同样通过代价函数计算邻域中每一个点的距离成本（如图4），此轮距离成本最小的点为28+110=138，将此点放入closelist中，并标记为浅蓝色。

图4

3.每一轮遍历都是按照此原理进行的，没有特殊情况便不再过多赘述，下面直接给出几轮遍历的结果（图5-图7），遇到特殊情况，后文会给出详细解释。

图5

图6

图7

4.图7中选出的上一轮成本最小的点为62+70=132，但遍历此点的邻域后发现此点邻域并不存在openlis中成本最小的点，所以此时从openlis中选出成本最小的点不再是62+70=132这个点的邻域（每一轮都是从openlis中选取最小的点放入colselist中，只是前几轮成本最小的点刚好在上一轮最小点的邻域）。如图8：此轮从openlis中选出的最小点是38+100=138（注意：此时出现了两个最小点，读者可以根据自己的习惯，在算法中设置优先选择先遍历到的那个点或者后遍历到的那个点。这里的两个点虽然都是第二轮最小点28+110=138的邻域，看似不能判断其先后顺序，但可在算法中设置遍历一个点邻域的顺序，这里假设从此邻域的正右方邻域顺时针计算每个邻域的距离，那么28+110=138正上方的点便是后遍历到的那个最小点），为了方便对比这两个点的区别，我在这里同时选中了这两个点放入colselist中，并同时计算两个点的邻域，这一轮遍历出现了对openlis中距离成本的更新（黄色字体为本轮遍历距离小于此前遍历距离的点，并更新了数据。注意：更新后的点，父节点也会随之改变为前一轮最小的点）。

图8

5.从上一轮遍历后的openlis中选出距离成本最小的点，刚好是上一轮更新的点48+90=138。

图9

6.图10中选出的上一轮成本最小的点为58+80=138，但遍历此点的邻域后发现此点邻域并不存在openlis中成本最小的点，所以此时从openlis中选出成本最小的点不再是58+80=138这个点的邻域，而是整个openlis中距离成本最小的点24+122=144，这一轮我依旧选择了两个点，如图11，同前文不再赘述。

图10

图11

7.我在此实例中遇到的特殊情况和要说明的重点基本讲完，下面我会直接给出每一轮遍历的结果。

图12

图13

图14

图15

图16

图17

图18

8.A*算法经过启发式遍历，最终找到了目标点，根据父节点的记录，从目标点向起始点回溯，找到了最短路径——黄色格子连线。（这里提出一个疑惑点：在图19的路径中从44+100=144这个点向58+80=138这个点移动时，需要从障碍物边缘经过，但不能保证机器人或车辆不碰到障碍物，如何通过优化算法来解决这个问题，欢迎大家评论区或私信讨论）

图19

9.以上实例是A*算法八邻域搜索的结果，在同样的条件下四邻域搜索的结果如图20和图21。图20和图21的区别是：当openlis中出现多个相同距离的最小点时，优先选择最先遍历的点和最后遍历的点。

图20

图21