A* 到底什么时候正确？从启发函数到重新加权后的 Dijkstra

初学 A* 时，最容易形成一种模糊印象：它是"加了启发函数的 BFS"，只要给一个"看起来靠谱的距离估计"，就能更快地找到最短路。真正做题时却很快遇到反例：同样是网格最短路，曼哈顿距离有时能用、有时会给出次优解；同样一份代码，把估计值乘以 1.5 之后立刻变快，答案却悄悄变差了。

这些差异不靠"启发函数调得好不好"解决。A* 背后有一个可以证明的结构：

A* 不是带估计值的 BFS，而是用一个势函数把边权重新加权之后的 Dijkstra；启发函数的一致性，就是重新加权后边权仍然非负这个条件。

理解"可加代价"“重新加权"和"一致性"这三件事，就能回答两个最重要的问题：什么时候可以用 A*，以及一个启发函数究竟要满足什么才不会破坏最优性。

本文假设你已经能写出 BFS 和堆优化的 Dijkstra；A* 的全部内容都建立在这两者之上。

阅读路线

全文比较长，建议分几遍读，每遍有明确的目标：

1. 第一遍只读第一到第四节，配动图 1 和动图 3：伪代码 → 三个成立条件 → 重新加权。读懂"A* 就是重加权后的 Dijkstra"这一句，这篇文章就值回票价了。
2. 第二遍读第五到第七节：f < C* 定理告诉你 h 到底买到了什么；第六节的松弛法是你以后自己构造 h 的唯一工具；第七节逐题练手。
3. 第九节的反例建议拿纸手推一遍那四步弹出过程。推完之后，你对"一致性为什么重要"的理解会从"背下来了"变成"我能自己造出反例”。
4. 第十二节双向搜索初学可以跳过，等刷到 127、752 想用双向 BFS 时再回来看。

一、A* 究竟在做什么

设 g(n) 是从起点到节点 n 的已知代价，h(n) 是对"从 n 到目标还需要多少代价"的估计，h*(n) 是这个剩余代价的真实值。A* 用一个优先队列，按

f(n) = g(n) + h(n)

从小到大取出节点处理。完整的骨架就这么长：

open = 最小堆，按 f 排序；g(start) = 0，压入 (h(start), start)
while open 非空:
    弹出 f 最小的节点 u                    ← 这一步称为"扩展 u"
    若 u 已定型则跳过                       ← 惰性删除：堆里可能有过时的旧条目
    把 u 定型（加入 closed 集合）
    若 u == goal: 返回 g(goal)             ← 只在弹出时判断目标，不在入堆时
    对 u 的每条出边 (u, v, cost):
        若 g(u) + cost < g(v):             ← 发现更短的到 v 的路
            g(v) = g(u) + cost
            压入 (g(v) + h(v), v)           ← 旧条目不删，弹出时跳过即可

两个术语后文会反复用：**扩展（expand）**指"弹出一个节点并处理它的所有出边"这一整步；弹出即定型指节点第一次被弹出时，它的 g 就是最终答案，此后不再更新。为什么目标判断和定型都必须放在弹出时而不是入堆时，第十一节有专门讨论。

当 h ≡ 0 时，f(n) = g(n)，这就是 Dijkstra。所以 A* 的全部额外内容，就是在排序键里加了一项 h。它比 Dijkstra 快的原因也很直接：Dijkstra 按到起点的距离一圈一圈向外扩展，是"无方向"的；h 提供了方向，让优先队列优先处理朝向目标的那一侧。

但这也说明了 A* 的性质：它不改变最坏情况复杂度。堆操作仍然是 O(E log V)（V、E 是节点数与边数），h 只是常数级剪枝。如果 h 给不出有效信息，A* 就退回 Dijkstra；如果 h 给出了错误信息，A* 会更快地给出错误答案。

二、“有一个距离估计"只是必要信号

和滑动窗口那篇里的讨论类似，可以把两个命题记为：

• A：这道题适合用 A*；
• B：题目里存在某种可以计算的"到目标的距离估计”。

通常有 A → B，但没有 B → A。网格题几乎总能写出曼哈顿距离，但这不意味着 A* 一定成立。

先看整个搜索算法族在同一个框架下的位置：

这张表比记忆模板更有用：它说明 A* 不是一个孤立技巧，而是 Dijkstra 上的一个连续旋钮。把 h 关掉是 Dijkstra，把 g 关掉是贪心最佳优先，把 h 放大是拿最优性换速度。

三、A* 成立的三个条件

1. 代价沿路径可加，且非负

f = g + h 这个式子本身就假定了路径代价是各边代价之和。如果题目的代价不是求和，加法结构立刻失效——第八节会用瓶颈路径的例子说明这一点。

同时边权必须非负。负权破坏的是 Dijkstra 的"弹出即定型"，A* 继承了这个前提，不但救不了，还会因为 h 的存在更难分析。

2. 目标集合已知，且能给出"到最近目标"的下界

h(n) 的定义依赖"到目标还有多远"，所以你必须先知道要去哪。

但这不要求目标唯一——这是一个流传很广的误解。目标是一个集合 T 时，取

h(n) = min over t in T  （n 到 t 的某个下界）

依然可采纳，通常也依然一致（各分量一致，取 min 后仍然一致），弹出 T 中任意一个目标就终止。这是完全合法的 A*，没有任何额外代价。

真正让 A* 失去意义的不是"目标多"，而是要的不是一次查询，而是全图的答案：

• 542. 01 矩阵：要每一个格子到最近 0 的距离，这是 n×m 个查询而不是一个。跑那么多次 A*，远不如一次多源 BFS 把整张图一次填满。
• 743. 网络延迟时间：要对所有节点取最大值，同样需要全部节点的结果。

所以准确的说法是：A* 是单次查询的加速。它用"我只关心从这个起点到这个目标集合"换取剪枝；一旦你需要的是全图答案，这个信息就没有可换的东西了。

3. 启发函数可采纳，并且最好一致

这是最关键、也最容易被忽略的条件。

可采纳（admissible）：对所有节点，h(n) ≤ h*(n)。也就是 h 从不高估剩余代价，它永远是一个乐观下界。

一致（consistent，也叫单调）：对任意一条边 (u, v)，

h(u) ≤ cost(u, v) + h(v)

并且 h(goal) = 0。这实际上是让 h 满足三角不等式。

它还有一个等价形式，比定义直观得多。设某条路径先到 u、再沿这条边走到 v，于是 g(v) = g(u) + cost(u, v)。把一致性不等式两边同时加上 g(u)：

g(u) + h(u) ≤ g(u) + cost(u, v) + h(v) = g(v) + h(v)
即  f(u) ≤ f(v)

也就是说，一致 ⟺ f 沿任意一条路径非递减。这正是"单调（monotone）“这个别名的来历，也是"弹出即定型"的直觉来源：既然 f 一路只增不减，那么当前弹出的最小 f 就再也不会被后面的节点压低。

两者的关系是：一致 ⇒ 可采纳（对可达节点沿其最优路径归纳，逐边累加即得；目标不可达时 h* 为无穷，可采纳自动成立），反过来不成立。

判断一致性时，可以问自己一句：

走一条代价为 c 的边之后，我的剩余代价估计最多能下降多少？如果下降幅度可能超过 c，这个 h 就不一致。

对单位权网格来说这句话尤其好用：一步的代价是 1，那么一步之内 h 的下降就不能超过 1。曼哈顿距离在四连通网格里一步至多变化 1，所以一致；但如果网格允许八个方向走且每步仍算 1，一步就能让曼哈顿距离下降 2，曼哈顿距离立刻变得不可采纳，必须换成切比雪夫距离。

四、为什么一致性正好是"重新加权后边权非负”

这是本文最想说清楚的一点。定义新的边权：

cost'(u, v) = cost(u, v) - h(u) + h(v)

这是把 h 当作一个"势函数"做的重新加权（图论里 Johnson 算法用的就是同一个变换）。“势"字类比物理里的势能：它只依赖你站在哪个节点，不依赖你怎么走过来，所以沿路径求和时能成对抵消。它有两个性质：

第一，它保持路径的相对优劣。 取任意一条从起点 s 经 n₁、n₂ 到 v 的路径，把每条边的新权重逐项加起来，记这个和为 g'(v)：

g'(v) = [c(s,n₁) − h(s) + h(n₁)] + [c(n₁,n₂) − h(n₁) + h(n₂)] + [c(n₂,v) − h(n₂) + h(v)]
      = c(s,n₁) + c(n₁,n₂) + c(n₂,v) − h(s) + h(v)        ← 中间的 h 全部成对相消
      = g(v) − h(s) + h(v)
      = f(v) − h(s)

h(s) 是常数。所以按 f 排序，就是按重新加权后的 g' 排序。A* 在原图上按 f 取节点，等价于在新图上按 g' 跑 Dijkstra。

第二，cost' ≥ 0 这个条件，展开就是 h(u) ≤ cost(u, v) + h(v)——正是一致性的定义。

于是整件事变得非常干净：

A* 的正确性不需要单独证明。一致的 h 把原图重新加权成一张非负权图，A* 就是这张新图上的 Dijkstra，Dijkstra 的正确性直接搬过来。

这也顺带解释了两个常被死记的结论：

• 为什么可以维护 closed 集合、节点弹出后就不再更新？ 因为这正是 Dijkstra 的"弹出即定型”，而定型的前提是新图边权非负，也就是 h 一致。
• 为什么可采纳但不一致时，带 closed 集合的 A* 可能出错？ 因为此时新图里存在负权边，Dijkstra 的前提被破坏了。

五、A* 到底快在哪：f < C* 的节点一个都跑不掉

前面说 h “提供方向”，这还是个比喻。用一致的 h 时，A* 会扩展哪些节点其实可以精确刻画。记最优解代价为 C*：

A* 必然扩展所有 f(n) < C* 的节点；可能额外扩展一部分 f(n) = C* 的节点；绝不扩展任何 f(n) > C* 的节点。

三句话各有各的道理：

• f(n) < C* 的必须扩展。 因为 h 不高估，f(n) = g(n) + h(n) 是"经过 n 的最优路径代价"的一个下界。这个下界都还没到 C*，算法就无法排除"更好的解藏在 n 后面"，只能去看一眼。
• f(n) > C* 的绝不扩展。 目标在 f = C* 时就已经出队了，f 更大的节点还排在它后面。
• f(n) = C* 的说不准。 这批节点和目标平局，扩不扩展取决于平局规则——第 3 点会用到这件事。

这条定理把"h 有多大用"变成了一个可以数出来的量：剪枝力度 = 有多少节点的 f 小于 C*。

1. 把动图里的格子数一遍

动图 1 那张网格，C* = 14：

70 和 35 不是碰巧跑成这样，是这条定理的直接结果。h ≡ 0 时 f = g，f < C* 就是"离起点比 14 近"的一整个圆盘，64 个格子；换上切比雪夫距离，同一道门槛只剩 26 个格子挤得进去。

2. 什么叫"更好的启发式"：支配关系

于是"h 更好"有了精确定义。设 h₁、h₂ 都可采纳，且处处有 h₂(n) ≥ h₁(n)：

f₂(n) = g(n) + h₂(n) ≥ g(n) + h₁(n) = f₁(n)

h₂ 把每个节点的 f 都抬高了，能挤进 f < C* 的节点只会更少。这时称 h₂ 支配（dominate）h₁。在同一张网格上把切比雪夫距离减半（仍然可采纳，只是更弱），三者的扩展集合恰好层层包含：

所以启发式设计的全部张力就一句话：可采纳性是天花板，支配关系说在天花板底下越高越好。 把 h 做大是唯一有意义的优化方向，但越过 h* 的那一刻最优性立刻失效——这才是第十一节"估计得更准和估计得更大是两回事"的完整含义。

两个极端可以印证：h ≡ 0 贴着地板，退化成 Dijkstra；h = h* 顶到天花板，此时最优路径以外的节点 f 全都大于 C*，配合"f 相同优先弹 h 小"的平局规则，A* 沿最优路径一步不拐地走到终点。所谓"旋钮"，旋的就是这条下界离天花板有多近。

滑动谜题的 linear conflict（同行或同列上两个方块互相挡路，至少要多绕两步）就是照这个思路做的：在曼哈顿距离上再加一项把 h 顶高，同时小心证明它仍然不越过 h*。

3. 平局怎么打破也值钱

f = C* 那批节点是唯一有回旋余地的地方。f 相同时优先弹出 h 更小的（等价于 g 更大的，也就是更靠近目标的那些），能少碰一批平局节点。同一张网格上只换平局规则：

默认（按入堆先后打破平局）  ：扩展 35 个
f 相同时优先弹 h 小的        ：扩展 30 个

代价当然仍是 14。这是个只改一行、不影响正确性的常数优化，面试里说得出来会加分。

六、把题目条件翻译成"乐观下界"

构造 h 不需要灵感。通用方法只有一条：

删掉原问题的一部分约束，得到一个更容易求解的松弛问题；松弛问题的最优代价，一定是原问题的一个可采纳下界。

因为原问题的任何合法解在松弛问题里也合法，所以松弛问题的最优值不可能更大。常见网格与状态图的 h 全都是这样来的：

表中 dx、dy 指当前位置与目标的行差与列差。最后两行值得单独说。滑动拼图里，“方块只能移到空格"是很强的约束；一旦允许每个方块自由移动，每个方块各走各的曼哈顿距离就是答案，这个值显然不超过真实步数。同理，单词接龙里每步只能改一个字母，那么与目标不同的字符位数就是步数的下界。

这种表达比记忆"网格题用曼哈顿距离"稳定得多，因为你是在推导一个下界，而不是套用一个印象。

七、典型题目逐题推导

例 1：1091. 二进制矩阵中的最短路径

八连通网格，每步代价 1，求左上角到右下角的最短步数。松弛掉障碍物后，(r, c) 到 (n-1, n-1) 的最少步数就是

h(r, c) = max(n-1-r, n-1-c)

一致性检查：一步至多让行差和列差各减少 1，所以 max 至多减少 1，等于这一步的代价 1，h(u) ≤ 1 + h(v) 成立。

注意这里不能用曼哈顿距离。斜着走一步同时减少行差和列差，曼哈顿距离一步下降 2，超过了这一步的代价，既不一致也不可采纳，会给出次优解。这就是第三节那句判断标准的直接应用。

同时要诚实地说：这道题 BFS 已经是 O(n²)，A* 不改善渐进复杂度，只在障碍稀疏、目标偏在一角时少扩展一批格子。**在 LeetCode 上 A* 几乎从来不是"必须”，它是常数级剪枝。**真正值得练的是能不能说清它为什么仍然正确。

例 2：752. 打开转盘锁

四个转轮，每步把某一位加一或减一。松弛掉死亡数字后，每一位独立地转到目标位，代价是环上的距离：

h(state) = Σ over i in [0,4)  min(|a_i - b_i|, 10 - |a_i - b_i|)

其中 a_i、b_i 分别是当前状态与目标密码的第 i 位，min 的两支对应正转和反转。一步只动一位、只动一格，因此 h 一步至多下降 1，与单步代价相等，一致。

这道题更常见的写法是双向 BFS，效果通常更好；把它放在这里，是因为它的 h 是"逐维度独立松弛"这一类构造的最清晰样本。

例 3：127. 单词接龙

每步只能改一个字母，因此

h(word) = word 与 endWord 不同的字符位数

一步至多修正一位，所以 h 一步至多下降 1，一致。注意题目返回的是序列长度而不是步数，最后要加一；h 定义在步数上，不要把这个偏移混进 h 里，否则 h(goal) = 0 会被破坏。

例 4：773. 滑动谜题

2×3 的板子，求还原所需最少移动。经典启发式是各方块到目标位置的曼哈顿距离之和：

h(board) = Σ over 每个非零方块  |目标行 - 当前行| + |目标列 - 当前列|

一次移动只挪动一个方块一格，所以这个和一步至多变化 1，一致。

这里有一个非常容易踩的坑：空格（数字 0）不能计入求和。理由和例 1 里"八连通网格不能用曼哈顿距离"是同一条判据：一次移动同时让一个方块和空格各挪一格，所以"含空格的曼哈顿和"一步可以下降 2，超过了单步代价 1，一致性当场破裂。

这不是"理论上可能出问题"。枚举全部 360 个可达状态可以直接验证：

含空格时最坏的一个状态是 [0,1,2,4,5,3]，估出 h = 6，而真实只需 3 步——整整高估一倍。顺带一提，2×3 的板子共有 6! = 720 种排列，但只有一半可达（另一半奇偶性不对，无论怎么滑都到不了），所以状态空间是 360 而不是 720。这个规模直接 BFS 完全够；它的价值在于展示"多算一项就从可采纳掉到不可采纳"有多容易发生。

例 5：787. K 站中转内最便宜的航班

这道题说明一个约束：h 必须是状态的函数，而不是到达该状态的路径的函数。

题目的状态不是"城市"，而是"城市 + 已用中转次数"。同一个城市在不同的剩余中转预算下，剩余最小花费是不同的。如果按城市定义 h，那么 h 就依赖于走到这里的路径，可采纳性的论证不再成立。正确做法是把中转次数并进状态，h 再定义在完整状态上。

实际上这道题按轮次跑 Bellman-Ford（至多 K+1 轮）更直接。顺带澄清一个撞名：Bellman-Ford 里的"松弛"（relax，用一条边更新距离估计）和第六节的"松弛问题"（放宽约束造下界）是两个无关的术语，撞在一起纯属翻译巧合。把这道题列在这里，是为了说明状态定义错了的话，启发式再精巧也无意义。

八、什么时候 f = g + h 这个式子本身就不适用

看 1631. 最小体力消耗路径 和 778. 水位上升的泳池中游泳。这两道题求的是瓶颈路径：一条路径的代价不是各边之和，而是各边的最大值。

普通最短路：cost(path) = Σ 边权
瓶颈路径：  cost(path) = max 边权

它们仍然可以用 Dijkstra 的框架，因为"路径代价随着延长只增不减"这条单调性依然成立——这才是 Dijkstra 真正依赖的性质。但是：

• g + h 的加法结构失效了。剩余瓶颈和已用瓶颈应该用 max 合并，即 f = max(g, h)；
• 第四节的重新加权论证也随之失效，因为 cost(u,v) - h(u) + h(v) 这个式子建立在可加性上。

所以正确的说法不是"这两道题不能用 A*"，而是：A* 的具体形式 f = g + h 绑定在可加代价上；换一种代价合成方式，就要重新推导相应的形式，而不是套用模板。

九、可采纳但不一致，究竟会出什么事

很多资料只写"要用可采纳的启发式"，但带 closed 集合的图搜索版 A* 真正需要的是一致性。下面是一个完整的反例。

四个节点，边权如下：

S → A  代价 3
S → B  代价 1
B → A  代价 1
A → G  代价 2

真实剩余代价：h*(A) = 2，h*(B) = 3，h*(S) = min(3+2, 1+1+2) = 4。最优解是 S → B → A → G，代价 4。

取一个可采纳但不一致的启发式：h(S) = 0、h(A) = 0、h(B) = 3、h(G) = 0。逐项检查都不超过 h*，确实可采纳。但看边 (B, A)：

h(B) ≤ cost(B, A) + h(A)  ⟹  3 ≤ 1 + 0 = 1   ✗

不一致。等价地说，重新加权后 cost'(B, A) = 1 - 3 + 0 = -2，是一条负权边。

现在跑带 closed 集合、弹出即定型的 A*：

弹出 S(f=0)：生成 A(g=3, f=3)、B(g=1, f=4)
弹出 A(f=3)：g(A) 定型为 3，加入 closed，生成 G(g=5, f=5)
弹出 B(f=4)：经 B 到 A 只要 g=2，但 A 已在 closed，被丢弃
弹出 G(f=5)：返回 5

答案 5，而最优是 4。A 第一次被弹出时 g 并不是最优的，closed 集合把这个次优值锁死了——这正是负权边下 Dijkstra 会犯的错误。

两种修法：

1. 换一个一致的 h（首选）；
2. 允许 reopening：发现更小的 g 时把已在 closed 的节点重新放回优先队列。上例中重新打开 A（g=2, f=2）就能得到正确答案 4。代价是可能反复扩展同一节点，最坏情况开销显著上升。

实践上的结论很简单：如果你的 h 是从松弛问题推出来的，它通常自动一致；如果你手工拼凑了一个"感觉挺准"的估计，先验证一致性，再决定要不要写 closed 集合。

十、其他"看起来能 A* 但不适合"的题

这些题说明，不能只凭"这是个求最短路的图"决定用 A*。真正要确认的是：代价能不能相加、要的是一次查询还是全图答案、以及有没有一个不高估的下界。

十一、最容易写错的八个细节

1. 在入堆时判断目标，而不是出堆时

错：push(next) 时如果 next == goal，直接返回 g(next)
对：pop 出来的节点等于 goal 时才返回

入堆时的 g 未必是最优的。只有弹出时，优先队列才保证没有更小的 f 还没处理。

2. 把 visited 标记打在入堆时

在单位权 BFS 里，入队即标记是正确且常用的写法。但在带权的 Dijkstra/A* 里，一个节点可能先以较大的 g 入堆、之后才发现更短的路。入堆即标记会直接丢掉更优路径。正确做法是弹出时判定，配合"当前 g 大于已记录的最优 g 就跳过"的惰性删除。

3. 忘记 h(goal) = 0

这不是形式要求。f(goal) = g(goal) + h(goal)，只有 h(goal) = 0 时终止条件返回的才是真实代价；否则算法可能提前或延后终止，一致性推导的链条也断了。

4. h 多算了一项

滑动谜题把空格计入曼哈顿距离，是这类错误最典型的样子。任何"多加一点让估计更准"的改动，都要重新验证它没有越过 h*。估计得更准和估计得更大是两回事，后者直接毁掉最优性。

5. 用了 Weighted A* 却宣称结果最优

把 h 乘上 w > 1 通常能大幅减少扩展节点数，但得到的解只保证不超过最优解的 w 倍。这是一个有意的取舍，写在代码里没问题，说成"最短路"就不对了。

6. 忽略题目对边权的限制

非负、单位权、网格四连通还是八连通、每步只改一位——这些条件往往正是某个 h 一致的前提。条件一变，原来的 h 可能立刻失效，例 1 里曼哈顿距离到切比雪夫距离的切换就是这样。

7. 只算时间，不算内存

这是 A* 在真实系统里最常见的死法，而讲解文章几乎都不提。A* 必须同时持有 open 表和 closed 表，空间是 O(扩展节点数)。在网格上这没什么，在状态图上就是灾难：滑动谜题从 2×3 换成 4×4，状态数从 360 涨到约 10¹³，时间还没超，内存先炸了。

这正是 IDA*（用迭代加深的 f 阈值换掉优先队列，空间降到 O(深度)）、beam search（每层只留 k 个）这些变体存在的全部理由。被追问"节点数上亿怎么办"时，答案是换搜索框架，不是把 h 调得更准。

8. h 本身算得太贵

第五节说"在可采纳的天花板下 h 越大越好"，但那只统计了扩展节点数。真实耗时是"扩展节点数 × 每个节点的开销"，而 h 是每扩展一个节点都要算一次的。

一个把扩展数砍掉 30%、但每次调用慢 5 倍的 h，是净亏损。所以强启发式要么本身是 O(1) 的闭式（曼哈顿、切比雪夫），要么可以增量维护（父节点的 h 加上一个修正量），而不是每次从头扫一遍状态。

十二、双向搜索：为什么双向 BFS 简单，双向 A* 难

第七节的例 2 提到 752 这类题实战里双向 BFS 通常更好。值得追问一句：既然单向 A* 和双向 BFS 各自都能加速，为什么很少见人把它们合起来？这个问题用第四节的势函数视角看，三行推导就能说清；用朴素视角看，只能背结论。

双向 BFS 的简单，来自 h ≡ 0

双向 BFS 的正确性只需一句话：两侧都按距离一层层推进，“已知区域"是规整的同心球，碰上就能对账。用重加权的语言说：两侧跑的是同一张未经重加权的图。一旦给两侧各装一个启发函数，这个前提就没了。

难点一：两侧其实在跑两张不同的图

前向用 h_f（到终点的下界），后向用 h_b（到起点的下界）。按第四节的等价，它们分别在这两张重加权图上跑 Dijkstra：

前向:  c_f(u,v) = c(u,v) − h_f(u) + h_f(v)
后向:  c_b(v,u) = c(u,v) − h_b(v) + h_b(u)      ← 同一条边，反向走

要让对账逻辑成立，两张图必须是同一张。令 c_f(u,v) = c_b(v,u)，两边的 c(u,v) 相消、移项，得到 h_f(u) + h_b(u) = h_f(v) + h_b(v)——沿每条边都相等，在连通图上就是处处相等：

h_f(n) + h_b(n) 必须在全图恒为常数。 这个条件叫平衡（balanced），它比"两侧各自一致"强得多，而且两侧各自一致完全推不出它。

动图 1 那张网格上实测：h_f、h_b 都取切比雪夫距离（各自都一致），h_f + h_b 的取值从 9 一路跑到 18，离常数差得远。几何上也直观：d(起点,n) + d(n,终点) 在起终点连线上最小，越偏离越大。

后果有多严重，第四节那个五点图上一算便知——同一条边，两侧眼中的权重对不上：

看最后一行：前向看是 2，后向看是 −2。后向搜索眼里这是一条负权边——和第九节的反例同一种病，只不过那次是单个 h 不一致造成的，这次是两个各自一致的 h 拼在一起造成的。

标准修法（Ikeda 势函数）是强行做成平衡的：

p_f(n) = (h_f(n) − h_b(n)) / 2
p_b(n) = −p_f(n)

p_f + p_b ≡ 0，常数条件自动满足；同一张五点图上实测，六条边两侧全部一致且全部非负。但代价明摆着：(h_f − h_b)/2 比 h_f 弱得多，按第五节的支配关系，h 变小意味着 f < C* 的节点变多——为了"能双向”，剪枝力度大约打了对折。

难点二：“相遇即停"是错的

这一条连普通的双向 Dijkstra 都躲不过。四条边就能构造反例（起点 0，终点 4）：

0 → 3  代价 4
3 → 4  代价 2
3 → 2  代价 2
2 → 4  代价 2

真实最短是 0→3→4 = 6。但"某节点被两侧都定型就返回"会返回 8：后向从 4 出发先定型的是 2（代价 2），前向经 3 到 2 是 6，于是 2 先被两侧共同定型，交出 6+2=8——而真正的最优交汇点 3 此刻还没被后向碰到。

两侧的搜索区域"碰上了”，不等于它们碰在最优路径上。

正确的终止判据是维护 μ = 目前找到的最好完整路径代价（每当一条边跨越两侧已访问集合时更新），直到 前向队首 f + 后向队首 f ≥ μ 才停。这也顺带暴露实现里最常见的 bug：最优交汇点可能直到结束都没被任何一侧正式定型，所以候选必须在"边跨越两侧"时就记，而不是等"节点被两侧定型"。

回到 LeetCode

752、127 这类单位权状态图，老实写双向 BFS，别碰双向 A*。账很好算：双向 BFS 把 b^d 变成 2·b^(d/2)，是指数级改善；A* 按第五节只是把 f < C* 的节点数压小，是常数级剪枝。指数打常数，而合并两者要同时处理上面全部难点——这个规模下不值。真实场景里双向 A* 活跃在路网导航（ALT：landmark 预处理出势函数 + 双向 + 精细终止），那里的势函数本身就是按"重加权后非负"设计的，依然是第四节那套东西。

十三、做题时的完整判断清单

面对一道新题，可以按以下顺序思考：

1. 路径代价是各边求和吗？如果是取 max、取乘积或别的合成方式，f = g + h 需要重新推导。
2. 边权非负吗？有负权先考虑 Bellman-Ford，A* 帮不上忙。
3. 要的是一次查询还是全图答案？目标是一个集合没关系（取 min 下界即可），但需要每个点的答案时 A* 换不到东西。
4. 状态定义完整吗？h 只能是状态的函数，不能依赖走到这里的路径。
5. 能不能删掉某个约束得到一个松弛问题？它的最优值就是一个可采纳的 h。
6. 走一条代价为 c 的边，h 的下降会超过 c 吗？会就是不一致，不能直接用 closed 集合。
7. h(goal) 等于 0 吗？
8. A* 在这道题上真的有收益吗？单位权图上 BFS 已经是线性的，加堆反而更慢。
9. 状态数会不会撑爆内存？A* 要同时存 open 和 closed；状态图一大就该考虑 IDA* 而不是继续调 h。
10. 想双向就先想清楚：单位权状态图直接双向 BFS（指数级收益）；双向 A* 需要 h_f + h_b 恒为常数和基于 μ 的终止判据，LeetCode 规模不值。

最后可以把最常见的结论压缩成四句话：

可加代价、单次查询、不高估的下界——三者齐备，A* 才成立。

可采纳保证"不高估"，一致性保证"弹出即定型"；后者才是带 closed 集合的图搜索真正需要的。

h ≡ 0 是 Dijkstra，丢掉 g 是贪心最佳优先，把 h 放大 w 倍是拿最优性换速度。

剪枝力度 = f < C* 的节点有多少；在可采纳这个天花板下，h 越大越好。

但口诀只能帮助回忆，不能替代证明。真正可靠的切入点始终是第四节那个变换：把 h 看成势函数，检查重新加权后的边权是否仍然非负。只要这件事能说清楚，A* 的正确性就不需要猜——它就是 Dijkstra。