A* 搜索

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* 把启发乘权以换速度，会改变正确性保证，必须另行给出次优界，不能把它当作同一算法的小优化。