A* 搜索

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

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

图中只列出开放集合里的两个候选 $n,x$，其他开放格省略。单位步长下，两点的 Manhattan 下界分别为五和七，已知前缀代价均为三，所以优先展开键为八的 $n$。

四邻接方格中每步代价为 $1$ 时，到目标的 Manhattan 距离是一致启发：移动一格最多让该距离下降一，故 $h(u)\le 1+h(v)$。无障碍时它等于真实剩余距离；有障碍时仍不高估绕行距离。多个候选的 $f$ 可能相等，具体展开次序还取决于平局规则。

目标被某条边首次发现时不能立即停止，因为另一个尚在队列中的顶点可能给出更短路线。使用一致启发时，应等待目标成为最小 $f$ 并被弹出。即使 $h$ 恰为真实剩余距离，也可能展开多条最优路线上的候选。例如 $s\to a,a\to t,s\to b,b\to t$ 四条边权均为一，精确启发使 $a,b,t$ 的候选键都为二，某种平局规则会先展开 $a,b$ 才取出 $t$；找到一条最优路其实只需其中一个分支。求得精确启发本身通常还需要解决反向最短路。

重新开放有一个四点反例。取 $s\to a:2,s\to b:1,b\to a:0.5,a\to t:2$，启发值为 $h(s)=h(a)=h(t)=0,h(b)=2.5$。这些值都可采纳，却在 $b\to a$ 上不一致。展开 $s$ 后，算法先取 $a$，产生目标代价四；随后取 $b$，发现 $g(a)=1.5$。若永久关闭 $a$，这个改进无法传给目标，最后错误返回四；重新开放 $a$ 才得到最优代价 $3.5$。

本页固定原边权非负的常用接口。更一般的图若另有势函数保证所有约化边权非负，也可用重赋权后的 Dijkstra 证明，但需重新核对启发、路径和负圈条件。

A* 用于地图、机器人规划、游戏寻路和状态空间搜索。在一致性及相应平局约定下，更紧的下界可缩小必须展开的区域；实际展开数仍受平局和重复状态处理影响，启发计算成本也可能上升。应比较“省下的展开”与“每次估计代价”。

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