A*算法详解：启发式搜索与路径规划的完整实现

如果只让我推荐一个搜索算法无论是面试、竞赛、做游戏AI还是搞机器人导航我都会毫不犹豫地说A*。它不算难但总有人学完就忘、用到就错——要么在最简单的网格地图上绕远路要么把启发函数当成玄学随便拍一个数进去就以为万事大吉。我见过不少人把BFS改一改就当A*用结果搜索方向完全靠运气也见过有人把h值设得比实际代价还大跑出来的路径直接从“最优”变成了“看着终点猛冲、撞上墙再回头”。这篇文章我想把它讲透从它到底解决了什么问题、每一步运行逻辑是什么到手写一个可用版本再到那些容易被忽略的工程细节。适合刚接触搜索算法的同学也适合那些用过现成路径库但从未自己撸过一遍的人。1. 为什么绕不开A*从两个“不够聪明”的搜索方案说起1.1 广度优先搜索地毯式扫荡的代价先说最基础的广度优先搜索BFS。它的核心思路很朴素从起点出发一层一层往外扩散先把所有距离为1的点走完再走距离为2的点以此类推。如果每条边的代价一样BFS确实能找到最短路径因为它按“层数”严格推进第一次碰到终点时步数一定最省。问题在于它完全没有任何方向感。哪怕终点就在起点斜对面三个格子BFS也会把起点周围一整圈、再一整圈全部扩展掉才会碰触到终点。想象你在一个400×400格的网格地图上搜索一条路径目标只隔了三十个格子但BFS会把起点周围所有半径内的可达点几乎都塞进搜索队列里。实测下来这种“地毯式扫荡”动辄扩展几万个节点而A*可能只探几百个节点就收工了。BFS适用场景是那些“边权都相等、目标又足够近”的简单问题。一旦地图变大、路径变长它就是效率灾难。1.2 Dijkstra有代价意识却看不见终点Dijkstra可以看作BFS的加权版本。它不再按层数排序而是按“从起点走到当前节点已经付出的代价g”排序每次从待处理列表里挑g最小的节点继续扩展。这个改进让它能处理不同代价的边比如山地地图里爬山更耗时、河流穿越代价更高。但它依然缺少对“终点在哪里”的任何感知。Dijkstra只知道“我走到这一步花了多少”不知道“我还剩多远”。结果就是如果起点附近有一片低代价区域它会兴致勃勃地把那片区域几乎扫干净因为那些节点的g值实在太小了。可它们很可能和终点方向完全相反。换句话说Dijkstra是一台“只低头看路不抬头看天”的机器。它能保证最短路径但为了这个保证付出了大量无效探索的代价。1.3 三种策略的直观对比把BFS、Dijkstra和A*放在一起看差异非常清楚算法节点扩展顺序由什么决定是否利用终点位置信息典型表现BFS层数距起点步数否同心圆式扩散稳健但臃肿Dijkstra距起点累计代价g否围绕低代价区域蔓延方向感弱A*g hh是对终点代价的估计是从起点朝终点方向压缩搜索走廊A*最核心的变化就是在排序依据里多塞了一个h项。这个h是“对当前节点到终点还要花多少代价的估计”。有了它搜索就有了方向感算法不再像无头苍蝇一样四面八方铺开而是倾向于先处理那些“既离起点不远、又离终点不远”的节点。这也是A*被称为启发式搜索的原因。“启发”指的就是h这个估计值它并不来自确定计算而是来自你对问题结构的经验判断——对地图来说最常见的启发就是“直线距离还剩多远”。2. A*的核心机制f g h 背后的搜索哲学2.1 估值函数的拆解A*里有且只有一个核心公式f(n) g(n) h(n)三个字母分别代表g(n)从起点走到节点n已经付出的实际代价。这个值每个节点都不同由搜索过程逐步累加得到。h(n)从节点n到终点还需要付出代价的估计值。它不用算准但必须“合理”。f(n)经过节点n的完整路径的总代价估计。A*每次扩展时从待处理节点里选f最小的那个先下手。可以用赶早班高铁来类比。假设你从家出发去高铁站g就是你已经走完的路程h是你看地图估摸着“应该还有多远”f就是你判断“走这条路全程大概要多少”。你不会先跑去和火车站反方向的商场蹭一圈——除非你误以为那条路更近。A*做的事情本质上就是永远优先尝试那些全程预估距离最短的方案。2.2 open列表与close列表搜索过程在维护什么大多数A*实现里都有两个核心容器一个是open表一个是close表虽然代码里不一定直接这样命名。open表里装的是“已经被发现但还没来得及扩展”的节点。它们按f值排序每次取出f最小的那个出来扩展——这就是“待办清单”。close表里装的是“已经完成扩展”的节点代表已经考察完毕不会再动它们。不过在现代实现里close表通常不是一张显式的表而是依靠g_score这样的字典来隐式判断如果某个节点已经扩展结束那它的g值已经确定是最优后续再被其他路径发现时新g值大概率不会比它还小自然会被丢弃。关键点在于A扩展的是open表里f最小的节点而不是g最小或h最小的节点。f值兼顾了过去和未来所以A的行为既不像Dijkstra那样只向低代价区域倾斜也不会像贪婪搜索那样完全被h牵着鼻子走。2.3 一个5×5网格的完整推演拿一个最简单的5×5无障网格说事。起点S在左上角(0,0)终点G在右下角(4,4)四方向移动每格代价为1启发函数用曼哈顿距离。曼哈顿距离的计算方式h(n) |nx - gx| |ny - gy|起点(0,0)的h是8f088。扩展它得到两个邻居(1,0)和(0,1)它们的f都等于8g1h7。所以A*会优先扩展其中任意一个然后又会生成新的邻居。整个过程非常有意思在无障碍的矩形网格里绝大多数被扩展节点的f值都保持为8直到真正抵达终点。这说明A正在沿着“从起点到终点自然的方形走廊”推进。它没有把周围无用区域全部扫掉而是紧紧贴着那条直线走廊展开。如果地图左下方有一大片空地BFS会迫不及待地把它填满A却只会象征性地看一眼然后继续朝终点走。这里还有一个细节值得注意当f值相同的节点有多个时A*的下一步扩展可能是任意的。不同实现可能选择g更小的、h更小的或者干脆按坐标顺序取。这个“平局策略”对搜索效率影响很大后面工程部分我会单独讲。3. 启发函数的设计决定“聪明程度”的那一半3.1 可采纳性与一致性最优性从哪来很多教程会直接甩出两个数学名词可采纳性和一致性。听起来吓人其实不难理解。可采纳性说的是h(n)必须不大于从n到终点的真实最短代价。也就是说你可以低估距离但不能高估。只要h永远不超估A*就能保证找到最短路径。用打车类比这就是“司机预估里程时只许说短了不许说长了”。如果司机说“还有20公里”但实际只要5公里你可能听了他的话直接换路线反而绕远。A*同理h一旦超估搜索就会过早相信某些看似f很小的节点反而错过真正的捷径。一致性是更强的条件对任意节点n和它的后继节点n必须满足h(n) cost(n, n) h(n)这个条件保证“从起点看过去每走一步f值都不会回退”。一致性比可采纳性更强满足一致性的h通常也满足可采纳性而且实现起来更省心因为不需要处理f值下降导致的重复更新问题。3.2 曼哈顿、欧几里得、对角线不同网格模型的h选择h不是随便写的它必须和你的移动模型匹配。我见过太多人把三种距离函数混着用结果搜索效率一塌糊涂。移动模型推荐h说明四方向网格上下左右曼哈顿距离单格代价固定h永远小于等于真实代价可采纳八方向网格含斜对角对角线距离对角移动代价约1.414不能再用曼哈顿连续空间/任意方向欧氏距离直线距离是真实路径的下界天然可采纳四方向网格里真实移动一步至少需要横纵坐标差之和那么多次所以曼哈顿距离就是可采纳的。八方向网格里斜着走比横竖快真实代价可能更多依赖对角线距离。如果此时仍用曼哈顿距离h会比真实代价大路径就会失去最优性。网格路径规划中常见的“对角距离”公式dx abs(nx - gx) dy abs(ny - gy) h max(dx, dy) (sqrt(2) - 1) * min(dx, dy)这个公式的含义是尽量多走斜线剩下的用直线补齐。它精确匹配八方向移动模型是最贴近真实代价的可采纳启发之一。3.3 h设置过高或过低分别会发生什么h设得太小比如h恒等于0A就退化成Dijkstra搜索面积剧烈膨胀效率优势完全消失。h设得太大甚至超过真实代价A虽然跑得飞快但得到的路径不再是最优路径。也就是说h的取值其实是效率和最优性之间的一个开关。如果你带着“必须要最优解”的心态就不要让h超估。如果你做的是游戏AI寻路玩家根本不在乎你绕了0.3格的路那就可以放权重A*把h乘上一个1.2到3的系数。实测中这个技巧能大幅减少搜索节点数路径代价稍有增加但视觉上几乎看不出区别。在代码里实现权重A*只需改一行f g w * h # 比如 w 1.5如果你用启发式搜索处理“大世界地图”或“实时寻路”这个改动比任何花哨优化都立竿见影。4. 手写一个能用的A*地图路径规划的完整实现4.1 场景定义与数据结构我拿一个最经典的地图寻路场景来写完整实现。地图用二维数组表示0代表可通行1代表障碍四方向移动每步代价为1。需要准备的数据结构其实很少一个优先队列用Python里的heapq按f值排序。一个g_score字典记录起点到每个节点的最小代价。一个came_from字典记录每个节点的前驱用于最后回溯路径。这些就够了不需要额外维护close表。4.2 完整代码实现import heapq def manhattan(a, b): 四方向网格的启发函数曼哈顿距离 return abs(a[0] - b[0]) abs(a[1] - b[1]) def a_star(grid, start, goal): rows len(grid) cols len(grid[0]) # 优先队列里存 (f, 节点坐标)f 小的先弹出 open_heap [] heapq.heappush(open_heap, (manhattan(start, goal), start)) # 起点到节点的最小代价 g_score {start: 0} # 记录路径前驱 came_from {} # 四方向移动 directions [(1, 0), (-1, 0), (0, 1), (0, -1)] while open_heap: cur_f, cur heapq.heappop(open_heap) # 处理优先队列里的过期节点 if cur_f ! g_score[cur] manhattan(cur, goal): continue if cur goal: # 回溯路径 path [] while cur in came_from: path.append(cur) cur came_from[cur] path.append(start) path.reverse() return path for dx, dy in directions: nx, ny cur[0] dx, cur[1] dy if 0 nx rows and 0 ny cols and grid[nx][ny] 0: neighbor (nx, ny) new_g g_score[cur] 1 if new_g g_score.get(neighbor, float(inf)): came_from[neighbor] cur g_score[neighbor] new_g f new_g manhattan(neighbor, goal) heapq.heappush(open_heap, (f, neighbor)) return None # 无路径 if __name__ __main__: grid [ [0, 0, 0, 0, 0], [0, 1, 0, 1, 0], [0, 1, 0, 0, 0], [0, 0, 1, 1, 0], [0, 0, 0, 0, 0], ] start (0, 0) goal (4, 4) path a_star(grid, start, goal) print(path)运行这段代码会输出类似[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4)]4.3 关键代码段说明判断过期节点的那一行特别重要if cur_f ! g_score[cur] manhattan(cur, goal): continue因为优先队列不会自动删除旧记录。同一个节点可能因为g值被更新而多次入队旧记录的f比当前最优f大。如果不加这个判断A*会重复扩展已经过时的节点严重拖慢搜索速度甚至在某些实现里可能造成逻辑错误。路径回溯的部分也很基础。从终点开始不断通过came_from向前找前驱直到回到起点然后把列表反转就是完整路径。注意我用的是闭区间起点和终点都包含在里面。这个版本虽然简单但已经能应对大部分二维网格寻路需求。如果你想支持地图的出入点、动态代价、加权地图只需修改两个地方一是邻居遍历的代价二是g_score的累加方式。框架完全不用动。5. 换个场景八数码问题里的A*5.1 为什么状态空间搜索更像“解题”网格寻路里“状态”是坐标转移是上下左右移动一步。但并非所有搜索问题都有这么直观的坐标体系。八数码是另一个经典例子一个3×3的棋盘上有1到8共八个数字方块加上一个空格你可以把空格和相邻方块交换最终目标是让数字按顺序排列。这里的“地图节点”不是坐标而是整个棋盘排列。一个状态就是一个tuple比如(1, 2, 3, 4, 5, 6, 7, 8, 0)0表示空格。每一步滑动都对应一次“状态转移”。八数码的状态空间非常大全部排列数接近36万个。用BFS硬搜也能出结果但效率满足不了多步难题。A*在这里重新体现了价值只要给每个状态设计一个合理的h搜索就能被极大地压缩。5.2 八数码的状态表示与启发函数八数码最常用的启发函数是所有数字各自当前位置与目标位置的曼哈顿距离之和。对状态中的每个数字val它在棋盘里的位置索引是pos目标位置索引是val - 1。比如数字5的目标索引是4对应第2行第2列。然后累加两者的行差和列差def h8(state): dist 0 for pos, val in enumerate(state): if val 0: continue target_pos val - 1 dist abs(pos // 3 - target_pos // 3) abs(pos % 3 - target_pos % 3) return dist这个h是不是可采纳的是的。因为每一步只能把某个数字移动一格空格不参与计数。所有数字当前位置到目标位置的行列差之和已经是最低必要步数的下界。真实步数一定不会小于这个值。5.3 完整求解代码与实现细节八数码A*的整体框架和地图寻路完全一样区别只在于节点状态是tuple。邻居生成逻辑变成“找空格位置尝试交换上下左右”。每步代价固定为1。还得多做一件事检查初始状态是否可解。八数码不是所有排列都能还原存在逆序数的奇偶性判定。跳过这一步可能出现循环无解的搜索白白跑到超时。import heapq def solvable(state): tiles [x for x in state if x ! 0] inversions 0 for i in range(len(tiles)): for j in range(i 1, len(tiles)): if tiles[i] tiles[j]: inversions 1 return inversions % 2 0 def get_neighbors(state): neighbors [] zero state.index(0) row, col zero // 3, zero % 3 for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]: nr, nc row dr, col dc if 0 nr 3 and 0 nc 3: npos nr * 3 nc lst list(state) lst[zero], lst[npos] lst[npos], lst[zero] neighbors.append(tuple(lst)) return neighbors def h8(state): dist 0 for pos, val in enumerate(state): if val 0: continue target_pos val - 1 dist abs(pos // 3 - target_pos // 3) abs(pos % 3 - target_pos % 3) return dist def solve_8_puzzle(start): if not solvable(start): return None target (1, 2, 3, 4, 5, 6, 7, 8, 0) heap [] heapq.heappush(heap, (h8(start), start)) g_score {start: 0} came_from {} while heap: cur_f, state heapq.heappop(heap) if cur_f ! g_score[state] h8(state): continue if state target: path [] while state in came_from: path.append(state) state came_from[state] path.append(start) path.reverse() return path for nxt in get_neighbors(state): new_g g_score[state] 1 if new_g g_score.get(nxt, float(inf)): came_from[nxt] state g_score[nxt] new_g heapq.heappush(heap, (new_g h8(nxt), nxt)) return None如果拿一个初始乱序作为输入这段代码会返回从初始状态到目标状态的滑动序列。每个状态是一个排列配合你的打印函数把每一步棋盘画出来就能看到清晰的解题过程。八数码的A*实现几乎可以直接平移去做十五数码或类似滑动拼图问题只需把尺寸参数和可解性判断稍作调整。6. 工程落地时容易踩的坑6.1 优先队列里的“过期节点”问题这是首次手写A*最常踩的坑。因为g_score中的值会被更新同一个节点可能被压入堆中多次。堆里堆外留下了大量“过时记录”如果不加判断搜索时间可能成倍增长。我的做法很固定取出堆顶节点时重新计算它当前应有f值如果和堆中记录的f不一致直接跳过。这个操作代价极低却能保证每个节点最多真正扩展一次。网格寻路和八数码的代码里我都加了这个判断建议你无论如何都别删。6.2 移动方向变了启发函数却没跟上八方向网格里如果沿用曼哈顿距离要么得到非最优路径要么搜索效率反而下降。解决方法是改用对角线距离。我再强调一次启发函数必须和移动模型匹配这是h设计的第一原则。同样的问题也会出现在图中带权边的情况。如果地图里道路的代价不是恒为1曼哈顿距离很可能高估真实代价因为真实路径可能通过代价更低的“高速路”。这种场景更稳妥的h是把地图预处理得到的距离表缓存下来但那是更高级的玩法初级阶段先把距离函数选对就足够。6.3 大型地图的搜索空间控制地图一旦超过几千×几千即使A*也有点吃力。实测中网格地图主要瓶颈在open表堆里的节点可能有数十万个内存和排序开销都很大。有两个实用优化一是双向搜索从起点和终点同时扩展相遇即结束能显著缩小搜索空间二是跳点搜索JPS专门适用于无权重网格地图它会在直线方向上直接跳过同质区域一次跳跃替代几十步扩展。JPS本质上是A*的加速变体如果游戏地图特别大值得花时间研究。如果地图是静态的还可以提前把所有关键路口的距离表算好运行时只做“点到路口”的局部A*。这类预处理思路在做服务器端路径规划时很常见。6.4 动态场景下的实时重规划思路真实项目里地图往往不是静态的。怪物会移动、车辆会变道、施工区会突然出现。每帧都从零跑一遍A*是不现实的。常见做法是分层处理先用A在静态地图上算出一条粗路径角色沿着走当遇到临时障碍时只在障碍周围局部区域重新规划绕过障碍后再回到原路径。整个体系里A依然承担最重要的全局规划职责但不再是每帧都全量运行。另外当世界很大而起点终点变化频繁时可以提前做一点“贪心预处理”定期给地图打标记把大量不可通行区域从搜索空间里剔除让A只在有效区域工作。这些小技巧比单纯优化A代码本身更能提升整体表现。6.5 平局策略的隐藏影响当两个节点f值相同时先扩展哪一个其实很讲究。简单实现往往按入队顺序来但实测中这会带来很大的搜索面积浪费。我常用的平局策略是“f相同优先h小”即优先扩展看起来更接近终点的节点。这样搜索会更快推往终点方向搜索面积更集中。在网格寻路里还有一个等价做法比较g值优先扩展g更大的节点因为这代表它已经走了更多实际路程离起点更远更容易接近终点。改动只要一行但对性能的影响非常可观。在复杂迷宫地图上好的平局策略能让扩展节点数减少百分之三十以上。我在上面给的网格代码里用的是默认的比较实际调优时加上这个规则即可。如果让我只推荐一个值得亲手实现一遍的搜索算法我仍然会选A*。把它的代码从零写通之后你会突然发现很多更“高级”的算法其实都是它的变体JPS是加速版A*D是动态环境下的A一些路径规划算法的采样策略里也有它的影子。项目里遇到搜索问题先想清楚状态怎么定义、h怎么设计再开始写代码通常不会跑偏。花一个下午把这篇里的两份代码跑通比囫囵吞枣背十遍原理有用得多。