A*算法详解 一看就会 手把手推导 完整代码注释
最新回答
风铃鹿
2024-11-26 08:02:24
译文链接：（已经打不开了）
本文在原文的基础上进行修改，以求能更好的理解。
A* 算法的遍历过程
搜索区域(The Search Area)
想象在图中，绿色表示起点A，红色是终点B，蓝色方块为不可通过的障碍物。假设你从A点出发，希望找到快速到达B点的路径。那么，如何选择最优路径呢？
首先，我们将搜索区域简化为栅格地图，将复杂环境转化为二维数组。每个元素对应一个网格方块，标记为可通过或不可通过。路径表示为从A到B经过的方块集合。找到路径后，从方格中心移动至另一方格，直至到达目的地。这些中点被称为“节点”。在其他寻路资料中，人们常讨论节点，而非方格，是因为路径可能由非方格结构组成。节点位置灵活，可位于形状内任意位置。我们使用节点系统，因为它是最简单的。
开始搜索
在A*寻路算法中，我们从起点A开始，逐步检查相邻节点，直至找到目标。
操作如下：
1. 开启列表 --- openlist
2. 关闭列表 --- closelist
步骤1
将点A加入待处理列表（开启列表），随后将其标记为已处理（加入关闭列表）。开启列表不断增长，包含待检查的节点。
步骤2
寻找点A周围可到达且可通过的节点，作为邻居点，跳过障碍物。将它们加入开启列表，并为每个节点指定点A作为父节点。父节点信息在描述路径时极为重要。
步骤3
从开启列表中移除点A，加入关闭列表。
经过上述步骤，形成如图所示结构。点A为中心，用浅蓝色描边，表示已加入关闭列表。所有相邻节点位于开启列表中，用浅绿色描边。每个方格有灰色指针指向父节点，即开始的点A。
继续遍历开启列表中选择具有最小F值的节点。
F值介绍
选择路径的关键是以下等式：
F = G + H
其中，G表示从起点A到当前节点的移动耗费，H表示从当前节点到终点B的预估移动耗费。H被称为启发式，可能让人感到困惑。这是因为它是一个猜测，我们无法预知实际路径长度，因为途中可能存在障碍物。路径是通过反复遍历开启列表并选择具有最低F值的节点来生成的。
具体而言，G值通过从父节点到当前节点的移动路径计算得出，水平或垂直移动耗费为10，对角线方向耗费为14。选择整数10和14简化计算，并加快计算机处理速度。H值通过计算当前节点到终点的曼哈顿距离估算，忽略对角线方向移动。忽略障碍物后，路径长度被估算。这称为启发式。
第一步搜索的结果如下图所示，标注了G、H和F值。
继续搜索
为了继续搜索，选择开启列表中F值最低的节点，执行以下操作：
步骤4
将节点从开启列表移出，加入关闭列表。
步骤5
检查移出的节点的相邻格子，跳过已在关闭列表中的或不可通过的格子，并将它们添加到开启列表中。将移出的节点作为新节点的父节点。
步骤6
如果相邻格子已在开启列表中，检查通过当前节点到达该格子的新路径是否更好。如果不是，不做任何更改。如果G值更低，将相邻格子的父节点更改为当前节点，并重新计算F和G值。
在9格方格中，移出点A后，剩余8格在开启列表中。F值最低的格子是右侧紧邻点A的格子，F值为40。因此，选择此格作为下一个处理节点。
重复此过程，直到目标格被加入关闭列表，路径被找到。
通过从目标格开始，沿箭头方向至父节点，直至回到起点，得到路径。
A*算法总结
1. 将起点添加到开启列表。
2. 重复以下操作：
a) 弹出F值最低的节点（当前节点）。
b) 将其添加到关闭列表。
c) 遍历相邻格子。
d) 停止条件：目标格被添加到关闭列表或开启列表为空。
3. 追溯路径：从目标格开始，沿箭头方向至父节点，直至回到起点。
A*算法伪代码
与Dijkstra算法不同，A*使用启发式函数进行贪心策略。
Python版本A*算法
下载A*算法
部分代码展示
预告：下次详解Dynamic A* (D*)算法。
热门标签
