A* 相比 Dijkstra 优化了什么问题？｜阿里巴巴算法面经解析

60 秒回答模板

A* 优化的不是 Dijkstra 的正确性，而是搜索效率，尤其是单起点到单目标最短路径时的扩展范围。Dijkstra 的优先级只看 g(n)，也就是从起点到当前节点的最短已知距离，所以它会像水波一样向四周均匀扩散，很多节点虽然离目标方向很远，但只要 g 值小也会被扩展。A* 在此基础上引入启发式函数 h(n)，用 f(n)=g(n)+h(n) 排序，其中 g(n) 是已走代价，h(n) 是当前点到目标的估计代价。这样搜索会被目标方向引导，通常能少扩展很多节点。只要 h(n) 不高估真实剩余代价，也就是可采纳启发式，A* 能保证找到最短路径；如果 h 还满足一致性，则每个节点通常第一次出队时就是最优状态，关闭列表处理更简单。h=0 时 A* 退化成 Dijkstra；只看 h 不看 g 时接近贪心最佳优先搜索，速度可能快但不保证最优。

考点 问题本质

主线 A* 的核心改进

易错点 把 A* 说成一定比 Dijkstra 快，忽略启发式…

深入解析

问题本质

Dijkstra 解决的是带非负边权图上的最短路径问题，核心策略是每次从优先队列中取出 g(n) 最小的节点。这个策略保证了最优性，但在单目标查询中缺少目标感知能力。即使目标在某个明确方向上，Dijkstra 也会扩展所有当前距离起点更近的区域，直到目标成为最小代价节点。这种扩展方式适合求单源到所有点的最短路，但对只关心一个终点的场景可能浪费大量搜索。

A* 的核心改进

A* 将节点优先级从 Dijkstra 的 g(n) 改为 f(n)=g(n)+h(n)。其中 g(n) 表示起点到当前节点的真实已知代价，h(n) 表示当前节点到终点的估计剩余代价，f(n) 表示经过当前节点到达终点的总路径代价估计。这样，A* 不再只偏好离起点近的节点，而是偏好总路径估计更小的节点，本质是在 Dijkstra 的代价累积基础上加入启发式引导。

最优性条件

A* 能否保证最短路径，关键取决于 h(n) 的性质。可采纳启发式要求 h(n) 永远不超过从 n 到目标的真实最短代价，也就是不能高估剩余路径成本。一致启发式要求对任意边 n 到 m，都有 h(n) <= cost(n,m)+h(m)，含义是启发式估计满足类似三角不等式。一致性比可采纳性更强，能保证 f 值沿路径不下降，节点第一次从开放列表弹出时通常就已经确定最优。

开放列表与关闭列表

A* 通常维护开放列表和关闭列表。开放列表保存已经发现但还没有最终扩展的候选节点，一般用按 f 值排序的优先队列实现；关闭列表保存已经扩展过的节点，用于避免重复处理。每次从开放列表取 f 最小的节点，如果它是目标，则在最优性条件满足时可以返回路径；否则遍历邻居，计算新的 g 值并更新父指针、g 值和 f 值。

与 Dijkstra 的关系

A* 可以看作 Dijkstra 的启发式版本。当 h(n)=0 时，f(n)=g(n)，A* 完全退化为 Dijkstra。因此 A* 没有改变最短路径问题的基本代价模型，而是在优先级排序中加入对目标距离的估计。Dijkstra 更适合需要从一个起点得到到所有节点最短距离的场景；A* 更适合起点和终点都明确、且可以设计有效启发式的路径查询。

与 BFS 和贪心搜索对比

BFS 适用于无权图或所有边权相同的图，本质上按层扩展，相当于特殊边权下的 Dijkstra。Dijkstra 适用于非负权图，按真实已走代价 g(n) 扩展，保证最短路径。贪心最佳优先搜索主要按 h(n) 扩展，目标导向很强，但可能忽略已经走过的代价。A* 位于 Dijkstra 和贪心搜索之间，既保留 g(n) 对真实代价的约束，又用 h(n) 提供方向感。

复杂度与启发式质量

A* 的最坏情况时间和空间复杂度仍可能很高，甚至接近穷举搜索；如果 h(n)=0，它的表现就是 Dijkstra。A* 的优势来自启发式质量：h 越接近真实剩余代价且不高估，扩展节点越少；h 太弱会退化为 Dijkstra；h 太激进并高估，可能更快但不再保证最优。空间上，A* 需要保存开放列表、关闭列表、g 值和父指针，通常也是重要瓶颈。

典型应用

A* 常用于地图导航、游戏寻路、机器人路径规划、网格地图搜索、自动驾驶局部规划等场景。比如在二维网格中，如果允许四方向移动，可以用曼哈顿距离作为启发式；如果允许八方向移动，可以用对角距离或欧氏距离。启发式必须和移动规则、边权定义匹配，否则可能出现效率差或最优性失效的问题。

易错点

把 A* 说成一定比 Dijkstra 快，忽略启发式质量和最坏情况。
只说 A* 加了启发式，却没有解释 f(n)=g(n)+h(n) 中 g 和 h 的作用。
认为 A* 优化了 Dijkstra 的正确性，而不是优化单目标搜索中的扩展效率。
混淆可采纳启发式和一致启发式，或者不知道一致性对关闭列表和重新打开节点的影响。
误以为 h(n) 越大越好，忽略高估会破坏最优性。
把 A* 和贪心最佳优先搜索混为一谈，没有指出 A* 仍然保留 g(n) 的真实代价约束。

面试官追问

为什么说 Dijkstra 是均匀扩展？

因为 Dijkstra 的优先级只由起点到当前节点的最短已知距离 g(n) 决定。所有 g 值较小的节点都会优先被扩展，不管它们是否朝向目标。因此在地图上看，它更像从起点向四周一圈圈扩散。

A* 一定比 Dijkstra 快吗？

不一定。A* 的效率取决于启发式函数 h(n)。如果 h 很弱，例如恒为 0，它就是 Dijkstra；如果 h 设计得好，能明显减少扩展节点；如果 h 设计不合理，可能收益很小，甚至因为维护额外信息带来开销。

A* 为什么还能保证最短路径？

因为在可采纳启发式下，h(n) 不会高估到目标的真实剩余代价，A* 不会因为过度相信错误估计而提前排除真正的最优路径。如果 h 进一步满足一致性，则每次弹出 f 最小节点时，相关最短代价的确定过程更接近 Dijkstra，最优性更容易保证。

可采纳和一致有什么区别？

可采纳关注单个节点到目标的估计不能超过真实代价；一致关注相邻节点之间的启发式变化不能超过边的真实代价。一致启发式一定可采纳，但可采纳不一定一致。一致性通常能避免节点被关闭后又需要重新打开。

A* 和贪心最佳优先搜索有什么区别？

贪心最佳优先搜索主要看 h(n)，倾向于选择看起来离目标最近的节点，但可能忽略已经走过的路径成本。A* 同时看 g(n) 和 h(n)，因此既有目标方向引导，也保留总代价约束。