06 · 无信息搜索

⏱ 44 分钟 ｜ ⭐ 迭代加深看起来在做无用功，账一算却只贵 11%

🎯 一句话

「无信息」不是笨，是它只能分辨「这是不是目标」，除此之外对状态一无所知。 五种策略——BFS、DFS、深度受限、迭代加深、一致代价——在上一章的框架里全都只是换了一行 pick。

🔁 一、真的只换一行

接着上一章的 search(graph, start, goal, pick) 用，ROMANIA 那个字典也照抄：

# 接 05 章的 search.py，直接加在文件末尾
BFS = lambda f: 0                                        # 队列：取最早进来的
DFS = lambda f: len(f) - 1                               # 栈：取最晚进来的
UCS = lambda f: min(range(len(f)), key=lambda i: f[i][2])  # ⭐ 取 g 最小的

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

# uninformed.py —— 第 5 章的框架 + 本章的三种取法，可独立运行
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

BFS = lambda f: 0
DFS = lambda f: len(f) - 1
UCS = lambda f: min(range(len(f)), key=lambda i: f[i][2])

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

跑出来：

⭐ 一张表把这一章讲完了一半：BFS 找到的是「最少步数」的路（3 步）却不是最短的路（450 ≠ 418）；DFS 展开得最少却给出一条绕了 733 公里的烂路；UCS 展开最多但拿到了唯一正确答案。

🌊 二、广度优先 BFS

规则：先展开最浅的节点。队列先进先出。

在地图上的展开顺序（第 8 步取出 Bucharest，结束）：

Arad(0) → Zerind(75) → Sibiu(140) → Timisoara(118)
        → Oradea(146) → Fagaras(239) → RimnicuVilcea(220) → Lugoj(229)

注意展开顺序里的 g 不是递增的（140 之后是 118）——BFS 按层走，根本不看代价。

💀 空间才是 BFS 的死因。 $b=10$、$d=12$ 时是 $10^{12}$ 个节点。 就算一个节点只占 100 字节，也是 100 TB 内存。 时间上你还能等，内存上你直接崩。

⛏️ 三、深度优先 DFS

规则：先展开最深的节点。栈后进先出。

⚠️ DFS 不完备的具体样子：地图上 Iasi 和 Neamt 互为邻居。不做重复检测的 DFS 会 Iasi → Neamt → Iasi → Neamt … 永远出不来。加上「同一条路径上不许重复状态」就能在有限空间里恢复完备性（上一章 search 里的 explored 干的就是这件事，所以它跑出来了）。

⭐ DFS 的价值全在那个 $O(bm)$。 它是唯一一个内存不随深度指数爆炸的基础算法， 后面迭代加深和 IDA* 都是靠「借 DFS 的内存 + 补上它缺的完备性和最优性」活着的。

✂️ 四、深度受限搜索

DFS 加一个深度上限 $k$，到了就不再往下。

问题就一个：$k$ 取多少？ 取小了找不到解，取大了退化成 DFS。

罗马尼亚地图上其实有答案：这张图的直径是 9（最远的一对是 Neamt 和 Lugoj），所以 $k=9$ 一定够。但这个数字是你看着地图算出来的，不是搜索算法自己知道的——大多数真实问题里你根本没有这个先验。

⭐⭐ 五、迭代加深 IDS：这一章最反直觉的一点

规则：跑深度受限搜索，$k=0$；找不到就 $k=1$；再找不到 $k=2$……直到找到。

第一反应一定是：这不是在疯狂做无用功吗？ 每加深一层，前面所有层都要重新展开一遍。

把账算出来就知道不是了。 关键在于：节点数随深度指数增长，最后一层占了绝大多数。

在 IDS 里，深度 $i$ 的节点会被展开 $(d+1-i)$ 次——越浅的重复越多，但浅层节点本来就少：

$$\text{IDS} = (d{+}1)b^0 + d\,b^1 + (d{-}1)b^2 + \dots + 2b^{d-1} + 1\cdot b^d$$

拿 $b=10,\ d=5$ 算一次（讲义原样的例子）：

只多 11%。

为什么？因为 $100{,}000 / 111{,}111 = 90\%$ ——最后一层本身就占了九成，而最后一层只被展开一次。重复的全是那些便宜的浅层。

⚠️ 但这个 11% 是有前提的，$b$ 小的时候就不成立了。 同样 $d=5$，$b=2$ 时是 63 → 120，多 90%。 分支因子越大，IDS 越划算；$b=2$ 这种细长的树上，重复代价接近翻倍。

⭐⭐ IDS = BFS 的完备性和最优性 + DFS 的线性内存 + 11% 的时间罚款。 这就是为什么在「不知道解有多深、状态空间又大」的时候，IDS 是无信息搜索的默认选择。 第 7 章末尾的 IDA* 是同一个把戏用在 A* 上。

💰 六、一致代价搜索 UCS

BFS 按步数走，UCS 按已花代价 $g$ 走：每次取出 $g$ 最小的节点。每步代价都相同时，它退化成 BFS。

在地图上的完整展开顺序（12 个，$g$ 严格递增）：

Arad(0) → Zerind(75) → Timisoara(118) → Sibiu(140) → Oradea(146)
→ RimnicuVilcea(220) → Lugoj(229) → Fagaras(239) → Mehadia(299)
→ Pitesti(317) → Craiova(366) → Dobreta(374) → 取出 Bucharest(418) ✅

⚠️ 看第 12 个：Dobreta。 它在地图的西南角，和 Bucharest 完全反方向。UCS 还是展开了它，因为 $374 < 418$。

⭐ 这就是 UCS 的代价：它保证最优，做法是把「比目标更便宜的节点」全部展开一遍。 它对 Dobreta 有多远、方向对不对一无所知——地图上明明写着直线距离，它就是不看。 下一章要做的事，就是让算法开始看那一列数字。

⚠️ 那个 $\epsilon > 0$ 不是形式主义：存在零代价的边时，UCS 可能在一堆零代价动作里绕圈绕到死。

↔️ 七、双向搜索：把指数砍一半

从起点正向搜、从目标反向搜，两边在中间碰头。

两边各走 $d/2$ 层，总共 $2b^{d/2}$ 个节点，而不是 $b^d$。$b=10,\ d=6$ 时：$1{,}000{,}000$ → $2{,}000$，快 500 倍。

⚠️ 三个前提，缺一个就用不了：

1. 要能反向生成前驱——「哪些状态一步能到这里」。开车可以（路是双向的），但很多问题不行。
2. 目标可能有很多个——国际象棋的「将死」有无数种局面，从哪个开始倒着搜？
3. 空间还是 $O(b^{d/2})$——至少有一半得整个留在内存里做碰头检测（讲义假设用哈希表做 $O(1)$ 查重）。

📊 八、复杂度对照表（背这一张）

$b$ = 分支因子，$d$ = 最浅解深度，$m$ = 搜索树最大深度，$k$ = 深度上限，$C^*$ = 最优解代价。 ¹ $b$ 有限时完备。² $b$ 有限且每步代价 $\ge \epsilon > 0$ 时完备。³ 所有动作代价相同时才最优。

⭐ 读这张表的方式：空间那一行加粗的三个（DFS、深度受限、IDS）是唯一不会 OOM 的； 最优那一行只有 UCS 无条件成立。两者都要，就是迭代加深；再想要快，就得进下一章。

🔗 这一章连到哪里

✅ 检查点

1. 「无信息搜索」的「无信息」具体指什么？
2. BFS、DFS、UCS 在通用框架里的差别是什么？各自一行代码怎么写？
3. 在罗马尼亚地图上，BFS 和 UCS 找到的路分别多少公里？为什么不一样？
4. BFS 的空间复杂度是多少？$b=10, d=12$ 时大概要多少内存？
5. DFS 的空间复杂度为什么是线性的？它牺牲了什么换来这个？
6. DFS 不完备的具体样子是什么？怎么补救？
7. $b=10,\ d=5$ 时，迭代加深比只跑一次深度受限多花多少节点？多百分之几？为什么这么便宜？
8. IDS 的 11% 什么时候不成立？$b=2$ 时是多少？
9. UCS 为什么会展开 Dobreta 那种完全反方向的城市？
10. 双向搜索能把复杂度降到多少？它的三个前提是什么？
11. 对照表里，哪几个算法的空间是线性的？哪个算法无条件最优？

🛑 可以停在这里

⚡ 走神救援

无信息搜索 = 只能分辨目标和非目标，地图上写着的直线距离它一眼都不看。五种策略在上一章的框架里只换 pick 那一行：BFS 取最早进队的、DFS 取最晚进队的、UCS 取 $g$ 最小的。在罗马尼亚地图上跑出来的三行结果值得记住：BFS 450 公里 / 展开 8 个，DFS 733 公里 / 展开 7 个，UCS 418 公里 / 展开 12 个——BFS 找到的是最少步数（3 步）不是最短距离；DFS 展开最少但绕了 733 公里；UCS 展开最多但唯一正确。BFS：完备、每步代价相同时最优，时间空间都 $O(b^d)$；💀 空间是死因，$b{=}10,d{=}12$ 就是 $10^{12}$ 个节点、约 100 TB。DFS：不完备（Iasi↔Neamt 无限弹，靠 explored 补救）、不最优，但空间 $O(bm)$ 线性——它的全部价值就在这一条。深度受限加上限 $k$，问题是 $k$ 没法先验地知道（这张图直径是 9，但那是你看地图算的）。⭐⭐ 迭代加深 IDS 是本章最反直觉的：反复重来看着是无用功，但节点数随深度指数增长、最后一层占九成，$b{=}10,d{=}5$ 时 111,111 → 123,456，只多 11%；⚠️ 前提是 $b$ 大，$b{=}2$ 时 63 → 120 要多 90%。IDS = BFS 的完备最优 + DFS 的线性内存 + 11% 罚款。UCS 无条件最优（不要求每步等代价），代价是把所有比目标便宜的节点全展开——所以它连西南角的 Dobreta（$g=374 < 418$）都展开了。双向搜索 $b^d \to 2b^{d/2}$（$b{=}10,d{=}6$：一百万 → 两千，快 500 倍），但要能反向生成前驱、目标不能太多、空间仍是 $O(b^{d/2})$。对照表里线性空间的只有 DFS / 深度受限 / IDS，无条件最优的只有 UCS。

下一节 👉 07-启发式与A星.md ⭐⭐