上一篇讲了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)是可采纳的（admissible），A*保证找到最优路径。

证明（反证法）： 假设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) = 0（Dijkstra）：搜索所有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)

六、面试实战

Q：A*和Dijkstra的区别是什么？ A：A* = Dijkstra + 启发式函数。Dijkstra只看g(n)，A看g(n)+h(n)。A有方向性，Dijkstra是均匀扩散。

Q：什么是可采纳性？ A：启发式函数h(n)永远不会高估从n到终点的真实代价。即h(n) <= h_true(n)。可采纳性是A*保证最优解的充要条件。

Q：A*的时间复杂度是多少？ A：最坏情况O(b^d)，b是分支因子，d是深度。和Dijkstra一样。但好的启发式函数可以大幅减少实际搜索的节点数。

Q：如果h(n)不可采纳，A*还能用吗？ A：能用，但不保证最优解。工程上经常用加权A（Weighted A），把h(n)乘以一个大于1的权重，牺牲最优性换取速度。

Q：A*能处理动态环境吗？ A：标准A不能——每次环境变化都要重新搜索。动态环境用D Lite（后面会讲），它能在环境变化后增量更新路径，不用从头搜索。

小结

A*算法 = Dijkstra + 启发式函数。评估函数f(n) = g(n) + h(n)，g(n)是实际代价，h(n)是估计代价。

关键性质：如果h(n)可采纳（不高估），A*保证找到最优路径。

启发式函数的质量决定A*的效率。h(n)越接近真实代价，搜索越快。曼哈顿距离、欧几里得距离是常见的可采纳启发式。选择哪种启发式取决于地图的连接方式——4连接用曼哈顿，8连接用切比雪夫，连续空间用欧几里得。

下一篇讲启发式函数的设计——曼哈顿/欧几里得/对角线距离的选型。

---

如果这篇文章对你有帮助，欢迎点赞、在看、转发三连。 你的支持是我持续更新的最大动力。

「机器人软件开发面试·从入门到精通」连载系列 

上一篇：第208篇 Dijkstra算法——最短路径的经典解法

下一篇预告：第210篇 启发式函数设计——曼哈顿/欧几里得/对角线距离的选型

有任何问题欢迎评论区留言，我会尽量回复。