07 · 启发式与 A*

⏱ 48 分钟 ｜ ⭐⭐ 全板块最重要的一章：手机导航跑的就是它

🎯 一句话

$f(n) = g(n) + h(n)$：已经花掉的 + 还要花的估计。只要估计从不高估，按 $f$ 最小展开就一定拿到最优解。

一致代价搜索只看 $g$（最优但慢，展开 12 个），贪婪只看 $h$（快但绕远，展开 3 个、多走 32 公里）。A* 把两个加起来：418 公里的最优解，只展开 5 个。

🧭 一、启发式函数 h 是什么

$h(n)$ = 从节点 $n$ 到目标的「最便宜路径」的估计代价。罗马尼亚地图上现成就有一个：每个城市到 Bucharest 的直线距离 $h_{SLD}$。

# 接 05 章的 search.py，加在文件末尾
H = {"Arad": 366, "Bucharest": 0, "Craiova": 160, "Dobreta": 242, "Eforie": 161,
     "Fagaras": 178, "Giurgiu": 77, "Hirsova": 151, "Iasi": 226, "Lugoj": 244,
     "Mehadia": 241, "Neamt": 234, "Oradea": 380, "Pitesti": 98,
     "RimnicuVilcea": 193, "Sibiu": 253, "Timisoara": 329, "Urziceni": 80,
     "Vaslui": 199, "Zerind": 374}

GREEDY = lambda f: min(range(len(f)), key=lambda i: H[f[i][0]])            # 只看 h
ASTAR  = lambda f: min(range(len(f)), key=lambda i: f[i][2] + H[f[i][0]])  # ⭐ g + h

print(search(ROMANIA, "Arad", "Bucharest", ASTAR))   # 把 ASTAR 换成 GREEDY 再跑一次

# astar.py —— 第 5 章的框架 + 本章的贪婪与 A*，可独立运行
ROMANIA = {
    "Arad": [("Zerind", 75), ("Sibiu", 140), ("Timisoara", 118)],
    "Zerind": [("Arad", 75), ("Oradea", 71)],
    "Oradea": [("Zerind", 71), ("Sibiu", 151)],
    "Sibiu": [("Arad", 140), ("Oradea", 151), ("Fagaras", 99), ("RimnicuVilcea", 80)],
    "Timisoara": [("Arad", 118), ("Lugoj", 111)],
    "Lugoj": [("Timisoara", 111), ("Mehadia", 70)],
    "Mehadia": [("Lugoj", 70), ("Dobreta", 75)],
    "Dobreta": [("Mehadia", 75), ("Craiova", 120)],
    "Craiova": [("Dobreta", 120), ("RimnicuVilcea", 146), ("Pitesti", 138)],
    "RimnicuVilcea": [("Sibiu", 80), ("Craiova", 146), ("Pitesti", 97)],
    "Fagaras": [("Sibiu", 99), ("Bucharest", 211)],
    "Pitesti": [("RimnicuVilcea", 97), ("Craiova", 138), ("Bucharest", 101)],
    "Bucharest": [("Fagaras", 211), ("Pitesti", 101), ("Giurgiu", 90), ("Urziceni", 85)],
    "Giurgiu": [("Bucharest", 90)],
    "Urziceni": [("Bucharest", 85), ("Hirsova", 98), ("Vaslui", 142)],
    "Hirsova": [("Urziceni", 98), ("Eforie", 86)],
    "Eforie": [("Hirsova", 86)],
    "Vaslui": [("Urziceni", 142), ("Iasi", 92)],
    "Iasi": [("Vaslui", 92), ("Neamt", 87)],
    "Neamt": [("Iasi", 87)],
}

def search(graph, start, goal, pick):
    """返回 (路径, 总代价, 展开过的节点数)"""
    frontier = [(start, [start], 0)]
    explored, expanded = set(), 0
    while frontier:
        i = pick(frontier)                    # ⭐ 全部差异只在这一行
        state, path, g = frontier.pop(i)
        if state == goal:
            return path, g, expanded
        if state in explored:
            continue
        explored.add(state)
        expanded += 1
        for nxt, cost in graph[state]:
            if nxt not in explored:
                frontier.append((nxt, path + [nxt], g + cost))
    return None, None, expanded

H = {"Arad": 366, "Bucharest": 0, "Craiova": 160, "Dobreta": 242, "Eforie": 161,
     "Fagaras": 178, "Giurgiu": 77, "Hirsova": 151, "Iasi": 226, "Lugoj": 244,
     "Mehadia": 241, "Neamt": 234, "Oradea": 380, "Pitesti": 98,
     "RimnicuVilcea": 193, "Sibiu": 253, "Timisoara": 329, "Urziceni": 80,
     "Vaslui": 199, "Zerind": 374}

GREEDY = lambda f: min(range(len(f)), key=lambda i: H[f[i][0]])            # 只看 h
ASTAR  = lambda f: min(range(len(f)), key=lambda i: f[i][2] + H[f[i][0]])  # ⭐ f = g + h

for name, pick in [("贪婪", GREEDY), ("A*", ASTAR)]:
    path, cost, expanded = search(ROMANIA, "Arad", "Bucharest", pick)
    print(f"{name:4s} 代价={cost:4d} 展开={expanded:2d}  {' -> '.join(path)}")

⭐ 注意这两行有多短。 上一章的 UCS 是 f[i][2]，贪婪是 H[f[i][0]]，A* 就是把它俩加起来。整个框架一个字没动。

🍰 二、贪婪最佳优先：快，但会把你带沟里

规则：$f(n) = h(n)$，谁看起来离目标最近就展开谁。跑出来是 Arad → Sibiu → Fagaras → Bucharest，只展开 3 个节点（UCS 是 12 个），但这条路 450 公里，比最优的 418 多绕 32 公里。四个维度：完备性 ❌（会陷进循环）· 最优性 ❌（差 32 公里）· 时间空间都是 $O(b^m)$。

⚠️ 不完备的样子（讲义原例）：起点 Iasi、目标 Fagaras。Neamt 的直线距离看起来更近，贪婪就先去 Neamt——而 Neamt 只连回 Iasi，是个死胡同。树搜索版本会 Iasi → Neamt → Iasi → Neamt … 无限循环。

⭐ 贪婪的毛病和深度优先一模一样：一头扎进去、不回头、不算账。 它唯一的问题是完全不看已经花了多少——Fagaras 那条路 $h$ 小，但 $g$ 大得多。

⭐⭐ 三、A*：在地图上完整手算一遍

$g(n)$ 是起点到 $n$ 实际花掉的，$h(n)$ 是 $n$ 到目标的估计。$f(n)$ 的含义很实在：「经过 $n$ 的那条解，总代价大概是多少」。

从 Arad 出发，每一步取 $f$ 最小的展开：

结果：A* 代价=418 展开=5 Arad -> Sibiu -> RimnicuVilcea -> Pitesti -> Bucharest。 和 UCS 一样最优，展开数从 12 降到 5。

这张表里藏着三件必须看懂的事：

⭐ ① 第 4 步之后，Bucharest 已经躺在队列里了（$f=418$），A* 却没有停。 因为 Fagaras 的 $f=417$ 更小——还存在一条更短的解的可能性。 这就是上一章说「目标测试必须放在取出时」的具体理由。

⭐ ② 第 5 步生成了第二个 Bucharest 节点，$f=450$。 两个不同的节点、装着同一个状态 Bucharest，一个 $g=418$、一个 $g=450$。 这正是第 5 章那句「同一个状态可以对应树上很多个节点」。$f=450$ 那个永远不会被展开。

⭐ ③ 贪婪走的正是 Fagaras 那条路，A* 也只差 2 就上当了（417 vs 415）。 救它的是那个 $g$：Pitesti 抢先生出 $f=418$ 的 Bucharest，把 450 那条挡掉了。

✅ 四、可容许性：从不高估

可容许（admissible）：对所有节点 $n$，$h(n) \le h^*(n)$，其中 $h^*(n)$ 是 $n$ 到目标的真实最小代价。

人话：估计可以偏乐观，绝不能偏悲观。

$h_{SLD}$ 为什么可容许？因为两点之间直线最短——公路再怎么修也不可能比直线更近。查一下：$h(\text{Fagaras})=178$ 而真实的 Fagaras → Bucharest 是 211 公里，$h(\text{Pitesti})=98$ 而真实是 101，都没高估。

⚠️ 高估会怎样：把 $h(\text{Pitesti})$ 拍脑袋改成 150，那 $f(\text{Pitesti})=467 > 417$，A* 会先展开 Fagaras、返回 450 那条路，而且它自己不知道错了。

📐 五、A* 为什么最优（这个论证很短，但看懂了会改变理解）

设 $G_2$ 是一个次优的目标节点，已经被生成、躺在队列里。设 $G$ 是最优目标。

关键一步：最优路径从起点通到 $G$，起点已经展开了、$G$ 还没展开，所以这条路径上一定存在一个还没被展开、正躺在队列里的节点 $n$。

然后四行：

所以 $f(G_2) > f(n)$：队列里永远有一个比 $G_2$ 更值得先展开的 $n$。 $G_2$ 会一直排在后面，直到最优的 $G$ 被取出、搜索结束。

⭐⭐ 这个论证给出的结论比「A* 最优」更精确： 次优的目标节点可以被生成，只是永远不会被展开。 上面第 5 步那个 $f=450$ 的 Bucharest 就是活的 $G_2$。 也就是说——A* 在看到目标之后还会继续搜，直到确信没有更短的路为止。

🔺 六、一致性：比可容许更强的那个条件

一致（consistent，也叫单调）：对每条边 $n \to n'$，$h(n) \le c(n, n') + h(n')$。

这就是三角不等式：从 $n$ 直接估到目标，不该比「先花 $c$ 走到 $n'$、再从 $n'$ 估到目标」更贵。$h_{SLD}$ 是一致的——直线距离在平面上天然满足三角不等式（自己验一条：$h(\text{RimnicuVilcea})=193 \le 97 + 98 = 195$）。

一致 ⟹ 可容许，反过来不成立。 一致性还带来一个副作用：沿任何一条路径 $f$ 单调不减，所以第一次取出某个状态时它的 $g$ 就已经是最优的了。

⚠️ 可容许但不一致，会真的出错

四个节点的反例：

$h$ 全部不高估 → 可容许。但边 A → B 上：$h(A)=5 > c(A,B) + h(B) = 1 + 1 = 2$ → 不一致。

带 explored 集合的 A*（也就是图搜索）跑一遍：① 展开 S，生成 A（$g{=}2,f{=}7$）和 B（$g{=}4,f{=}5$）。② B 的 $f$ 最小 → 展开 B，它带着 $g=4$ 被写进 explored，生成 G（$f{=}8$）。③ 展开 A，它想把 B 更新成 $g=3$——但 B 已在 explored，这条更新被直接丢掉 💀。④ 展开 G，返回代价 8。

真正的最优是 S → A → B → G = 2 + 1 + 4 = 7。A* 给出了 8。

💀 这个错为什么阴险：不报错、不崩溃，返回一条看起来完全合法的路径，只是贵了 14%。这类 bug 在真实系统里能活很久——规划器每次都给「能走通但绕远」的方案，没人会怀疑是启发式的性质搞错了。

两个修法：要求 $h$ 一致，或者允许重开节点（发现更便宜的 $g$ 时把状态从 explored 拿回 frontier）。

⭐ 一句话记住这条分界：树搜索（不查重复）要 $h$ 可容许就够；图搜索（查重复）需要 $h$ 一致。

📊 七、A* 的性质，和它唯一的死穴

💀 A* 是被内存杀死的，不是被时间。 它跑到一半 OOM，而不是跑得慢。

IDA*（迭代加深 A*）是标准解法：把第 6 章的迭代加深搬过来，门槛不再是深度而是 $f$ 值——跑一轮深度优先，$f$ 超门槛就砍掉；找不到解就把门槛提到「这轮被砍掉的最小 $f$」再来一轮。内存降到线性，在状态数指数增长的问题上和 A* 渐近一样快。

🔗 这一章连到哪里

✅ 检查点

1. 贪婪的 $f(n)$ 是什么？它展开几个节点、路径多长、比最优多几公里？为什么不完备？
2. A* 的 $f(n)$ 是什么？含义一句话怎么说？它展开几个，UCS 几个？
3. 第 4 步 Bucharest 已在队列里（418），为什么还要展开 417 的 Fagaras？第 5 步那个 $f=450$ 的 Bucharest 印证了第 5 章的哪句话？
4. 什么叫可容许？$h_{SLD}$ 为什么可容许？$h(\text{Pitesti})$ 被高估成 150 会怎样？
5. 最优性论证里的 $n$ 是什么节点？哪一步用到了可容许？比「A* 最优」更精确的结论是什么？
6. 什么叫一致性？和可容许什么关系？反例里图搜索返回多少、最优是多少、错在哪步？
7. 树搜索和图搜索对 $h$ 的要求分别是什么？A* 的死穴是什么，IDA* 怎么解决的？

🛑 可以停在这里

⚡ 走神救援

$f(n) = g(n) + h(n)$：已经花掉的 + 还要花的估计。 同一个框架只差一行：UCS 只看 $g$，贪婪只看 $h$，A* 把两个加起来。三个数字要记住：UCS 418 公里 / 展开 12 个，贪婪 450 公里 / 展开 3 个（多绕 32 公里），A* 418 公里 / 展开 5 个。贪婪不完备（Iasi→Neamt→Iasi 无限循环，Neamt 是死胡同）也不最优，毛病和 DFS 一样：不看已经花了多少。⭐⭐ A* 的手算轨迹：Arad(366) → Sibiu(393) → RimnicuVilcea(413) → Pitesti(415) → Fagaras(417) → 取出 Bucharest(418)。两个必看的点：① 第 4 步 Bucharest 已以 $f{=}418$ 躺在队列里，A* 仍先展开 $f{=}417$ 的 Fagaras——这就是目标测试必须放在取出时的理由；② 第 5 步生成了第二个 Bucharest 节点（$f{=}450$），同一状态两个节点，永远不会被展开。可容许 = $h(n) \le h^*(n)$，从不高估；$h_{SLD}$ 可容许因为两点之间直线最短（178 vs 真实 211、98 vs 真实 101）。⭐ 最优性论证：最优路径上必有一个未展开的 $n$ 在队列里，则 $f(G_2)=g(G_2) > g(G) = g(n)+h^*(n) \ge f(n)$，次优目标 $G_2$ 永远排在它后面——次优目标可以被生成，只是永远不会被展开。一致 = $h(n) \le c(n,n')+h(n')$（三角不等式），一致 ⟹ 可容许但反之不然。 💀 反例（S→A 2、S→B 4、A→B 1、B→G 4，$h$ = 0/5/1/0）：A→B 上 $5 > 1+1$ 不一致，图搜索返回 8 而最优是 7——B 带 $g{=}4$ 先进 explored，A 想改成 $g{=}3$ 时被丢掉。树搜索要可容许，图搜索要一致。 A* 死于空间，IDA* 把门槛从深度换成 $f$ 值，内存降到线性。

下一节 👉 08-启发式怎么设计.md