上一篇讲了Dijkstra——像水波纹一样均匀扩散保证找到最短路径但搜索效率低。今天讲A*算法它在Dijkstra的基础上加了一个指南针——启发式函数让搜索朝着终点方向前进。A是1968年由Nilsson等人提出的至今已有50多年历史。讲真这是机器人路径规划领域最重要的算法之一没有之一。移动机器人、无人机、机械臂、自动驾驶——几乎所有需要路径规划的场景都会用到A或者它的变体。面试时如果不会A*基本等于运动规划这块没学过。一、A*的核心思想A*的评估函数f(n) g(n) h(n)g(n)从起点到节点n的实际代价和Dijkstra一样h(n)从节点n到终点的估计代价启发式函数Dijkstra只看g(n)——我从起点走了多远。贪心搜索只看h(n)——我离终点还有多远。A*两个都看——我已经走了多远 我离终点还有多远。import heapq def astar(graph, start, goal, heuristic): open_set [(0, start)] # (f值, 节点) g_score {start: 0} came_from {} closed_set set() while open_set: f, current heapq.heappop(open_set) if current goal: return reconstruct_path(came_from, current) if current in closed_set: continue closed_set.add(current) for neighbor, cost in graph[current]: tentative_g g_score[current] cost if tentative_g g_score.get(neighbor, float(inf)): came_from[neighbor] current g_score[neighbor] tentative_g f_score tentative_g heuristic(neighbor, goal) heapq.heappush(open_set, (f_score, neighbor)) return None二、启发式函数——A*的指南针启发式函数h(n)决定了A*的行为h(n) 0 → A*退化为Dijkstra保证最优但慢h(n) 真实代价 → A*只走最短路径最快但不可能知道h(n) 真实代价 → A*保证最优但搜索范围比理想情况大h(n) 真实代价 → A*不保证最优但搜索更快关键概念可采纳性admissibility。如果h(n)永远不会高估真实代价即h(n) h_true(n)对所有n成立那么A*保证找到最优解。这个条件也叫乐观估计——宁可低估不可高估。常见的可采纳启发式2D网格4连接曼哈顿距离2D网格8连接切比雪夫距离连续空间欧几里得距离def manhattan(a, b): return abs(a[0]-b[0]) abs(a[1]-b[1]) def euclidean(a, b): return ((a[0]-b[0])**2 (a[1]-b[1])**2) ** 0.5 def chebyshev(a, b): return max(abs(a[0]-b[0]), abs(a[1]-b[1]))三、最优性证明A*为什么能保证找到最优解证明思路如下定理如果h(n)是可采纳的admissibleA*保证找到最优路径。证明反证法 假设A找到了一个次优路径代价为C。那么最优路径上一定存在某个节点n还没被扩展且f(n) g(n*) h(n*) C*因为h可采纳。但A选择了次优路径上的节点来扩展说明那个节点的f值 f(n) C。这意味着A一定会在次优路径到达终点之前先扩展n*从而找到最优路径。矛盾。所以A*一定能找到最优路径。证毕。这个证明的核心在于可采纳的h(n)保证最优路径上的节点不会被跳过。只要最优路径上有一个节点还没被扩展A*就会继续搜索。四、A*的效率分析A*比Dijkstra快多少取决于启发式函数的质量。定义启发式的信息量h(n)越接近真实代价信息量越大A*越快。极端情况h(n) 0Dijkstra搜索所有g(n) C*的节点h(n) h_true(n)只搜索最短路径上的节点最优情况h(n) |h_true(n) - h(n)| epsilon搜索的节点数与epsilon成反比工程经验好的启发式函数可以把A*的搜索节点数减少到Dijkstra的1/10甚至1/100。举个例子100x100的网格起点(0,0)终点(99,99)。Dijkstra搜索了约5000个节点A*用曼哈顿距离只搜索了约200个节点。快了25倍而且找到的是同一条最短路径。五、A*的工程实现要点实际项目中用A*要注意几个问题1. 开放列表的数据结构。用二叉堆优先队列是最常见的选择。插入和取出最小值都是O(logN)。如果频繁更新节点的f值需要支持decrease-key操作。Python的heapq不支持工程上通常允许重复入队lazy deletion。2. 闭合列表。用哈希表HashSet存储已访问的节点。O(1)查询。3. 路径回溯。用字典HashMap存储每个节点的父节点。找到终点后从终点回溯到起点就得到完整路径。4. tie-breaking。当多个节点f值相同时优先选h(n)大的离终点更近的。这可以避免A*在等值区域闲逛。5. 内存管理。大规模地图上开放列表和闭合列表可能占用大量内存。工程上可以用更紧凑的数据结构或者限制搜索范围比如只在起点周围的矩形区域内搜索。# tie-breaking技巧 # f值相同时优先选h大的 f_score g h * (1 1e-6)六、面试实战QA*和Dijkstra的区别是什么AA* Dijkstra 启发式函数。Dijkstra只看g(n)A看g(n)h(n)。A有方向性Dijkstra是均匀扩散。Q什么是可采纳性A启发式函数h(n)永远不会高估从n到终点的真实代价。即h(n) h_true(n)。可采纳性是A*保证最优解的充要条件。QA*的时间复杂度是多少A最坏情况O(b^d)b是分支因子d是深度。和Dijkstra一样。但好的启发式函数可以大幅减少实际搜索的节点数。Q如果h(n)不可采纳A*还能用吗A能用但不保证最优解。工程上经常用加权AWeighted A把h(n)乘以一个大于1的权重牺牲最优性换取速度。QA*能处理动态环境吗A标准A不能——每次环境变化都要重新搜索。动态环境用DLite后面会讲它能在环境变化后增量更新路径不用从头搜索。小结A*算法 Dijkstra 启发式函数。评估函数f(n) g(n) h(n)g(n)是实际代价h(n)是估计代价。关键性质如果h(n)可采纳不高估A*保证找到最优路径。启发式函数的质量决定A*的效率。h(n)越接近真实代价搜索越快。曼哈顿距离、欧几里得距离是常见的可采纳启发式。选择哪种启发式取决于地图的连接方式——4连接用曼哈顿8连接用切比雪夫连续空间用欧几里得。下一篇讲启发式函数的设计——曼哈顿/欧几里得/对角线距离的选型。如果这篇文章对你有帮助欢迎点赞、在看、转发三连。 你的支持是我持续更新的最大动力。「机器人软件开发面试·从入门到精通」连载系列上一篇第208篇 Dijkstra算法——最短路径的经典解法下一篇预告第210篇 启发式函数设计——曼哈顿/欧几里得/对角线距离的选型有任何问题欢迎评论区留言我会尽量回复。