003｜A*：用可信的剩余代价引导最短路搜索

系列首页 · 上一篇 · 下一篇

原论文：Peter E. Hart、Nils J. Nilsson、Bertram Raphael，A Formal Basis for the Heuristic Determination of Minimum Cost Paths，1968。作者主页原版PDF。作者书目还列有1972年的勘误，讨论理论时不能把所有后来的表述都无条件回填到1968年版本。

先接住前作的问题

D-H给出了一个构型对应的位姿，但没有回答怎样从起点走到目标；这里是几何表示与搜索的教学联系。搜索领域中，只按已走代价扩展与只看目标距离各有缺口，本篇用已走代价和可采纳下界共同排序。

五个前置概念

五个前置概念是：图状态描述决策位置；路径代价是目标；优先队列决定展开顺序；可采纳启发是不高估的剩余代价；一致性约束相邻节点的启发变化。

一、问题设定：图上的最短路怎样同时利用已走代价和目标下界

从机器人当前位置到出口，Dijkstra会优先扩展已经走到这里最便宜的节点，却不看它离出口还有多远。贪心搜索只看离出口的估计距离，又可能为了看起来近而绕大圈。A*把两种信息相加：已经支付的代价g，以及尚未支付代价的估计h。

问题定义：图上的最优不等于机器人的最优

给定图G、起点s、目标集合和边代价c，要寻找累计代价最小的路径。机器人栅格图只是一个应用：节点可以表示位置，也可以包括朝向、速度或时间。如果车不能原地侧移，只用二维位置的邻接关系可能生成不可执行路径。

如果转移代价依赖上一步方向，却没有把方向放入状态，那么“同一个节点的最好到达方式”不再足以概括未来，标准最短路建模已被破坏。算法正确性要从状态定义开始检查。

二、用g+h排序，并逐项检查重开与终止条件

评价函数与搜索流程

这里采用 1968 年八页扫描稿的算法步骤；1972 年勘误未纳入本篇证明核验。重开节点的教学反例应与原稿第 102 页算法一起读。

$$f(n)=g(n)+h(n),\qquad 0\le h(n)\le h^*(n).$$

g是当前已发现从起点到n的最好代价，h是到目标的下界，h*是真实最小剩余代价。每次从开放集合取f最小的节点展开。发现更好的到达路径时，必须更新g与父指针。

教学伪代码允许重新打开节点，因此可处理不一致但可采纳的启发。工程中若采用关闭节点后永不重开的版本，就需要额外依靠一致性等条件，不能只检查h不高估。

一致性要求 $h(n)\le c(n,m)+h(m)$。它类似三角不等式，使沿路径的f不会随意下降。可采纳性只比较每个节点到目标的总下界，两者不能互相替换。

把“可能需要重开”变成一条可手算的轨迹。原创图例取 $S\to A$ 代价3、$S\to B$ 代价1、$B\to A$ 代价1、$A\to G$ 代价2，启发取 $h(A)=0,h(B)=3,h(G)=0$。它们都不高估，但 $h(B)>1+h(A)$，所以不一致。

从 $S$ 展开后，$A$ 的 $f=3$，$B$ 的 $f=4$，先关闭 $A$ 并生成代价5的目标。接着展开 $B$，发现到 $A$ 的更短代价2；必须重开 $A$，才能把目标代价改成4。若永久忽略 CLOSED 中的节点，就错误返回5。问题不在启发“不够聪明”，而在用只对一致启发安全的剪枝规则处理了更宽的输入类别。原稿第102页算法明确保留重开步骤，不能在教学实现里悄悄删掉。

为什么找到的是最短路

以下是教学证明思路。假设弹出的目标代价大于最优路径代价C*。在最优路径上，总有一个尚未完成扩展的前沿节点；正确维护g时，该节点的f不超过C*。于是它应该比那个更贵的目标先被弹出，产生矛盾。

证明依赖关键条件：最优路径的前沿没有被错误删除；启发没有高估；到达目标是在队列弹出时判定，而不是第一次生成目标时就停止。有限图和适当的边代价条件还影响终止讨论。

“扩展节点最少”的说法更强，涉及比较算法类别、启发一致性及f相等节点的处理等条件。本文不把最短路正确性直接升级为无条件的计算最优性。

回到原文：算法保证的条件在哪里

直接对照原始搜索算法与重开步骤（PDF 第 3 页，印刷页 102）：第 4 步明确要求发现更便宜路径时重新打开已关闭节点。旁边的小图给出 $g$ 与 $h$ 的分工，不能把生成目标当成已经弹出最优目标。

这是一篇形式化分析论文，没有现代机器人任务基准。证据重点应是模型假设、算法步骤和定理比较的范围。

第 101 页，第 I.B 节。 有向图、后继有限、边成本有统一正下界 $\delta>0$；支持其搜索和终止讨论；不能删去前提后直接推广无限零代价链。

第 102 页，第 II.A 节。 选择最小 f，平局优先目标；目标被选中才停止；更好路径可重开 CLOSED；最优前沿不能被错误丢弃；首次生成目标不等于搜索完成。

第 103 页，Theorem 1。 启发不高估真实剩余代价时的 admissibility；给出列明条件下的解最优性，不给出实时期限。

第 104 页，第 III.B 节、式（5）及 Lemma 2。 一致性与闭合时 g 已最优的关系；解释何时可以避免重复打开；可采纳性与一致性不是同一个条件。

第 105–106 页，Theorem 2–3。 更强的节点展开比较涉及一致性、比较算法信息量和平局规则；不支持任意 A* 实现无条件展开最少节点。

第 107 页第 IV.B 节进一步强调：节点数量最少，不意味着计算资源最少。计算更精细的几何下界也有开销，廉价但较弱的下界可能具有实际价值。作者用欧氏距离计算和一个更便宜下界的比较说明这种取舍。

教学实验方案，未运行：固定图、邻接与边成本，比较零启发、符合动作模型的几何下界与更精确下界，分别记录路径成本、节点展开、内存与时间。目标是区分搜索减少多少和每次启发计算增加多少，而不是仅凭节点数宣布某个版本最快。

下界证明依赖最优前沿没有被错误丢弃；开放表实现因此必须保留更优路径的重开机会。两条候选路线的小例子将检查为什么生成目标还不能停止。

三、实现开放表，再用两条候选路径检查停止时机

输入：起点s，目标测试，后继函数，非负代价c，可采纳h
g[s] = 0，其他g = 无穷
优先队列加入(s, g[s]+h[s])
循环直到队列为空：
    弹出当前最小f节点n，跳过过期队列项
    若n通过目标测试：沿父指针返回路径
    对每个合法后继m：
        candidate = g[n] + c(n,m)
        若candidate < g[m]：
            更新g[m]和parent[m]
            将m加入或重新加入队列
输出：无路径，或外部预算耗尽时明确报告搜索未完成

教学例子与失败边界

设S到A的代价为2，A到G为2；S到B为1，B到G为10。若h(A)=2、h(B)=0，则A的f为4，B的f为1。B虽然先展开，A仍会在总代价11的目标之前展开，最后得到代价4的路线。A*可以暂时探索错误方向，并不意味着失去最优性。

若把h(A)错误设为100，A看起来极差，代价11的目标可能先被选中。这说明启发提供的是下界约束，不只是“总体上与距离相关”就够了。把神经网络预测的剩余时间直接当h，也需要另行验证下界性质。

四、把最优性证明与原稿算法步骤对照

读图：从 s 直接到 n₂ 的边成本为 7，经 n₁ 的成本是 3+3=6。这个小图把“更晚发现的路径更便宜”画了出来，解释为什么重开与更新不能因节点已经出现过而被省略。

五、保留状态模型、内存和启发质量的限制

栅格分辨率同样影响结论。粗栅格中最短路可能错过真实世界的窄通道；细栅格更准确却增加节点量。斜向移动允许时，曼哈顿距离可能高估，应该匹配允许的动作和代价选择启发。

队列中还可能保存同一节点的旧记录；弹出时应检查其g是否过期，否则会做重复工作。这个实现问题影响耗时，不能误解释为启发函数理论失效。

六、追问：把一个可采纳但不一致的启发换成一致启发，改变的是哪项实现责任？

七、为搜索补上几何，再让旧搜索可以修复

• 模块组合：构型空间：把有体积的机器人变成空间中的一个点。把机器人尺寸与姿态变成图需要尊重的构型禁区。
• 直接继承：D*：地图变了，怎样修复已经算过的最短路。在地图代价变化后复用搜索信息，新增的是增量修复。

八、自测与参考答案

问题1：h=0时A*变成什么，为什么仍然正确？

参考答案：在相应图搜索实现下退化为按累计代价扩展的Dijkstra。零是不高估的下界，所以最短路性质仍在，但没有利用目标方向信息，可能扩展更多节点。

问题2：第一次生成目标节点就停止，为什么可能错误？

参考答案：当时仍可能存在f更小的前沿节点，通过它到目标更便宜。生成目标只说明找到一条路线，队列弹出最低代价目标才与标准最优性论证一致。

问题3：路径是A*最优，为什么机器人还是撞墙？

参考答案：图可能只检查中心点、忽略机器人形状或跟踪误差，碰撞模型与真实任务不符。A*优化所给图，不替代构型空间建模、动态可行性或执行反馈。