05 · 状态空间与搜索框架

⏱ 33 分钟 ｜ ⭐ 后面四章的所有算法，差别只有一行代码

🎯 一句话

把问题写成「初始状态 + 动作 + 转移 + 目标测试 + 路径代价」这五件套，剩下的搜索算法全都只是在换同一个问题：下一个该展开谁。

BFS、DFS、迭代加深、一致代价、贪婪、A*——它们共用一个框架，只在「从待办队列里挑哪一个」这件事上不同。这一章把框架讲清楚，后面三章就只是往里填规则。

🧩 一、五件套：怎么把一个问题写成搜索问题

课程从头到尾用同一个例子：你在罗马尼亚的 Arad 旅行，明天从 Bucharest 起飞，机票不退。

换个问题，同一套：

⭐ 动作定义成「移空格」而不是「移某块」，是这一步里最实用的技巧： 空格只有一个，动作最多 4 个；如果定义成「移某块」，就得先判断哪些块挨着空格。 同一个问题，状态和动作怎么定，直接决定分支因子有多大。

⚠️ 二、抽象：真实世界先要被砍掉 99%

Arad → Zerind 这一个动作，在真实世界里代表无数条路线——走哪条车道、中途加不加油、堵不堵车。搜索算法根本没法处理这些。

所以形式化的第一步永远是抽象：一个抽象状态代表一堆真实状态，一个抽象动作代表一堆真实动作。

抽象只有一个硬要求，叫可实现性：任何真的「在 Arad」的状态，都必须真的能到达某个「在 Zerind」的状态。做到这一点，抽象解才能被展开成真实世界里可执行的方案。

💀 抽象砍错了会怎样：如果你把「有没有油」抽象掉了，算出来的最优路线可能中途没油——算法本身没错，是状态里少了决定性的信息。这和强化学习里状态设计漏信息是同一类错误。

🌲 三、状态空间 ≠ 搜索树（这一章最容易搞混的一点）

罗马尼亚地图上只有 20 个城市，也就是 20 个状态。

但搜索树上有无穷多条路径——Arad → Sibiu → Arad → Sibiu → … 想绕几圈绕几圈。

⚠️⚠️ 同一个状态可以对应树上很多个节点。 「Arad」这个状态在搜索树里会反复出现：根是它，Sibiu 的孩子里有它，Zerind 的孩子里也有它——这三个是三个不同的节点，深度不同、g 不同，但装的是同一个状态。

这句话是后面所有「重复状态」麻烦的根源：不管重复，DFS 会在两个城市之间来回弹到死；管重复，就得多维护一个 explored 集合，而且第 7 章会看到——管得不对，A* 会给出次优解。

⭐ 四、通用搜索框架

写成能跑的代码，就是下面这三十几行。后面三章不会再重写它，只会往 pick 里塞新规则。

# search.py —— 通用搜索框架：换一个 pick 就换一种算法
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)]          # 节点 = (状态, 路径, 已花代价 g)
    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

if __name__ == "__main__":
    BFS = lambda f: 0                         # 队列：取最早进来的
    print(search(ROMANIA, "Arad", "Bucharest", BFS))

跑出来是 (['Arad', 'Sibiu', 'Fagaras', 'Bucharest'], 450, 8)：路径 3 步、450 公里、展开了 8 个节点。

⚠️ if state == goal 那一行的位置，是初学者最常写错的地方。 很多人图省事，在生成孩子的时候就检查「是不是目标，是就返回」。 BFS 这样写没事，但一致代价搜索和 A* 这样写就不再最优了—— 目标刚被生成时，它可能只是「某条路走到的目标」，而不是「最便宜的那条」。 第 7 章会看到一个具体例子：Bucharest 以 f=418 躺在队列里，A* 却先展开了 f=417 的另一个节点。

📏 五、拿什么衡量一个搜索算法

四个维度，后面三章每讲一个算法就填一遍这四格：

时间和空间都用三个字母表示：

⭐ 空间才是真正杀死算法的那一个。 $b^d$ 个节点在时间上是「跑得慢」，在空间上是「直接 OOM 崩掉」。 第 6 章的迭代加深、第 7 章末尾的 IDA*，存在的唯一理由就是这一条。

🚧 六、这里和强化学习的分界线在哪

这一整个板块的方法有一个共同前提，必须说清楚，否则很容易和强化学习混起来：

⭐⭐ 一句话记住：搜索是「地图已经在手上，只是路太多」；强化学习是「地图得自己走出来」。

所以「模型已知的 MDP」其实就是搜索问题——第 4 章的动态规划和一致代价搜索干的是同一件事。 而 AlphaGo 那类系统两边都要：用学到的模型做搜索。

🔗 这一章连到哪里

✅ 检查点

1. 把一个问题形式化成搜索问题，需要写清哪五件事？
2. 8-数码的动作为什么定义成「移空格」而不是「移某个数字块」？
3. 什么叫抽象的可实现性？举个抽象砍错了的例子。
4. 罗马尼亚地图有 20 个状态，搜索树有多少个节点？为什么？
5. 「状态」和「节点」的区别是什么？节点比状态多带了哪几样东西？
6. 为什么说「同一个状态可以对应很多个节点」是重复状态问题的根源？
7. 通用搜索框架的循环有哪四步？六种算法的差别体现在第几步？
8. 目标测试为什么要放在「从队列取出时」而不是「生成孩子时」？
9. 评价搜索算法的四个维度是什么？$b$、$d$、$m$ 各指什么？
10. 搜索和强化学习的分界线是什么？

🛑 可以停在这里

⚡ 走神救援

这一章把「找路」变成了可计算的问题。五件套：初始状态、动作、转移模型、目标测试、路径代价。罗马尼亚地图（20 个城市，Arad 出发去 Bucharest）和 8-数码是全课程的两个标准例子；8-数码的动作定成「移空格」而不是「移某块」，因为空格只有一个、动作最多 4 个——状态和动作怎么定，直接决定分支因子。形式化前必须先抽象：Arad → Zerind 代表无数条真实路线，唯一硬要求是可实现性（真在 Arad 就必须真能到 Zerind）；砍错了会出现「算出的路线中途没油」这种事。⚠️⚠️ 本章最容易混的一点：状态空间 ≠ 搜索树。地图上只有 20 个状态，但搜索树有无穷多个节点，因为路径能绕圈。状态只有局面本身；节点还带着父节点、动作、深度、路径代价 g——所以同一个状态可以对应树上很多个节点，这是后面所有重复状态麻烦的根源。⭐ 通用搜索框架四步：① 按策略从 frontier 取一个 ② 目标测试 ③ 记进 explored ④ 展开生成孩子放回队列。六种算法的全部差别只在第 ① 步，代码里就是 pick(frontier) 那一行；BFS 版跑出 Arad→Sibiu→Fagaras→Bucharest，450 公里、展开 8 个节点。⚠️ 目标测试必须放在取出时而不是生成时，否则 UCS 和 A* 会丢掉最优性。评价四维：完备性、最优性、时间、空间，用 $b$（分支因子，这张图约 3）、$d$（最浅解深度，这里是 3）、$m$（最大深度，能绕圈就是 $\infty$）表示；空间才是真正杀死算法的那一个。⭐⭐ 最后一条分界：搜索假设模型已知（转移和代价都印在地图上），强化学习假设不知道、要试出来。

下一节 👉 06-无信息搜索.md