A* 搜索

形式陈述 ​

输入是非负边权图、起点 $s$、目标 $t$ 与启发函数 $h(v)$；输出一条 $s$ 到 $t$ 的最短路径公理库最短路问题Shortest-path problem在带边代价图中寻找两点之间总代价最小路径的问题。或不可达。算法维护已知路径代价 $g(v)$、前驱和按

$$f(v)=g(v)+h(v)$$

排序的优先队列公理库优先队列Priority queue · Priority queue ADT按键的优先次序反复访问并移除当前最小元素的抽象数据类型。。初始化 $g(s)=0$，反复弹出最小 $f$ 顶点，对出边执行 $g(v)>g(u)+w(u,v)$ 的松弛并更新前驱。

令 $h^{\ast }(v)$ 为从 $v$ 到 $t$ 的真实最短距离。可采纳性要求 $0\le h(v)\le h^{\ast }(v)$ 且 $h(t)=0$；一致性进一步要求每条边满足

$$h(u)\le w(u,v)+h(v).$$

一致性使沿任意路径的 $f$ 值不减，等价于重赋权 $w^{\prime }(u,v)=w(u,v)+h(v)-h(u)\ge 0$；因此节点首次弹出即可定型，目标首次弹出时可终止。只有可采纳但不一致时，图搜索必须允许已关闭节点 reopen，或采用保证仍无未处理更优路径的终止条件。二叉堆最坏时间仍为 $O((V+E)\log V)$，启发式主要减少实际展开的子图。

直觉 ​

Dijkstra公理库Dijkstra 算法Dijkstra's algorithm在非负边权图中逐次确定最短距离的单源最短路算法。只按已经付出的 $g$ 扩张，A* 再加入不高估的剩余成本下界。$f$ 是任何经当前候选到达目标的乐观总价；若某条路线连乐观估计都更贵，就可暂缓展开。$h=0$ 时所有额外信息消失，算法正好退化为 Dijkstra。

启发函数的价值来自可证明的方向性，而非“猜得大胆”。高估可能让真正最优路径被延后到错误终止之后；一致性则保证局部估计沿边相容，使关闭集合安全。

例子与边界 ​

四邻接方格中每步代价为 $1$ 时，到目标的 Manhattan 距离是一致启发：移动一格最多让该距离下降一，故 $h(u)\le 1+h(v)$。无障碍时搜索直指目标；有障碍时估计仍不高估真实绕行距离，只是可能变得不够精确。

目标被某条边首次发现时不能立即停止，因为另一个尚在队列中的顶点可能给出更短路线。使用一致启发时，应等待目标成为最小 $f$ 并被弹出。若 $h$ 取真实剩余距离，A* 只展开位于最优前沿上的必要状态；但计算这个 $h$ 本身通常等同于先解决原问题。

可采纳不自动蕴含一致。树搜索没有重复状态时可采纳性足以支持标准最优性论证；图搜索若永久关闭节点而不 reopen，则不一致启发可能让后来更小的 $g$ 无法传播。负边也破坏重赋权后的 Dijkstra 视角，本页不覆盖。

推论与应用 ​

A* 用于地图、机器人规划、游戏寻路和状态空间搜索。更强但仍可采纳的启发通常支配较弱启发并减少展开，但计算成本也可能上升；应比较“省下的展开”与“每次估计代价”。

A* 保证的是精确最短路，不是近似算法。Weighted A* 把启发乘权以换速度，会改变正确性保证，必须另行给出次优界，不能把它当作同一算法的小优化。

参考资料

• Peter E. Hart, Nils J. Nilsson, and Bertram Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics 4(2), 1968, pp. 100–107.
• Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 4th ed., Pearson, 2021, Ch. 3.