Chapter 2 搜索
一、搜索问题的数学建模
疾旋鼬在一个迷宫中寻找出口。它站在起点，面前有好几条路，每条路通向不同的房间，有些房间还有更多岔路。它需要找到一条通往出口的路径。
这就是搜索问题的核心：在一组可能的状态中，找到从初始状态到目标状态的路径。
状态空间图
搜索问题可以用状态空间图 (state space graph) 来建模：
- 结点 (node)：对应一个状态 (state)
- 边 (edge)：对应一个动作 (action)
- 初始状态 (initial state)：搜索的起点
- 目标状态 (goal state)：搜索的终点
- 路径代价 (path cost)：从初始状态到当前状态的累积代价
评估标准
| 标准 | 含义 |
|---|---|
| 完备性 (completeness) | 解存在时，算法能否保证找到 |
| 代价最优性 (cost optimality) | 能否找到代价最小的解 |
| 时间复杂度 | 找到解所需的时间或操作数 |
| 空间复杂度 | 执行算法所需的内存 |
二、无信息搜索
算法不利用目标状态的任何领域知识，仅根据既定策略探索状态空间。
广度优先搜索 (BFS)
像水一样在迷宫中蔓延。
逐层扩展节点：先扩展根节点，再扩展其所有子节点，依此类推。
性质： - 完备性：分支因子有限时，完备（若解存在则一定能找到） - 最优性：所有动作代价相同时，最优（动作步数最少） - 复杂度：时间 \(O(b^d)\)，空间 \(O(b^d)\)
其中 \(b\) 是分支因子，\(d\) 是最浅解的深度。
最优性证明（反证法）：假设存在一个更优解在更浅的层，但 BFS 按层扩展，会先访问到该节点，矛盾。\(\square\)
深度优先搜索 (DFS)
走入迷宫，不断尝试。
优先深入探索一条路径，直到无法继续（叶子节点或达到深度限制），然后回溯。
性质： - 完备性：在无限状态空间或存在环的情况下，不完备（可能陷入无限分支） - 最优性：非最优，可能找到非代价最小的解 - 复杂度：时间 \(O(b^m)\)，空间 \(O(bm)\)
\(m\) 是状态空间的最大深度。空间复杂度低是 DFS 的主要优势——只需存储当前路径和待探索的兄弟节点。
一致代价搜索 (Uniform Cost Search)
扩展当前路径累积代价最小的节点。可视为动作代价不均为 1 的图上的 Dijkstra 算法。
性质： - 完备且代价最优 - 时间复杂度：\(O(b^{C^*/\epsilon})\)，其中 \(C^*\) 是最优解代价，\(\epsilon\) 是最小步长
指数爆炸问题
搜索算法的时间/空间复杂度通常是指数级的 \(O(b^d)\)。这限制了其在大型问题上的直接应用。
围棋的状态空间约有 \(10^{170}\) 个状态，比宇宙中的原子还多。直接搜索不可行。
三、启发式搜索
现在，疾旋鼬有了一些信息——它知道出口大致在北方。这个"大致方向"就是启发式 (heuristic)。
算法利用启发式函数 \(h(n)\) 来估计从当前状态 \(n\) 到目标状态的最低代价，以指导搜索方向。
贪心最佳优先搜索
总是扩展 \(h(n)\) 值最小的节点，即估计最接近目标的节点。
- 完备性：不完备（可能陷入死循环）
- 最优性：非最优
- 效率：通常很快找到解，但不一定是最优解
A* 搜索
结合一致代价搜索和贪心搜索，评估函数为：
其中： - \(g(n)\)：从起点到 \(n\) 的实际代价 - \(h(n)\)：从 \(n\) 到目标的估计代价
总是扩展 \(f(n)\) 最小的节点。
可容许启发式 (Admissible Heuristic)
对所有节点 \(n\)，满足 \(0 \leq h(n) \leq h^*(n)\)，其中 \(h^*(n)\) 是从 \(n\) 到目标的真实最低代价。即不高估。
定理：若启发式函数是可容许的，则 A* 算法是代价最优的。
证明：假设 A* 返回了一个非最优解节点 \(n\)（\(g(n) > C^*\)），而最优解路径上的某个节点 \(n'\) 还在 open list 中。
由于 \(h\) 可容许：\(f(n') = g(n') + h(n') \leq g(n') + h^*(n') = C^*\)
而 \(f(n) = g(n) + h(n) \geq g(n) > C^*\)
因此 \(f(n') < f(n)\)，A* 应该先扩展 \(n'\) 而非 \(n\)，矛盾。\(\square\)
一致性启发式 (Consistent Heuristic)
对任意节点 \(n\) 及其后继 \(n'\)（通过动作 \(a\)），满足：
即满足三角不等式。
一致性蕴含可容许性（可自行证明：对最优路径上的节点递推）。
在一致性启发式下，A 效率更高——每个节点最多被扩展一次*。
启发式函数的设计
| 问题 | 启发式函数 | 可容许？ |
|---|---|---|
| 8-数码问题 | 错位棋子数 | 是（不高估） |
| 8-数码问题 | 曼哈顿距离之和 | 是（更紧） |
| 旅行商问题 | 最小生成树 | 是 |
支配关系：\(h_1\) 比 \(h_2\) 更"准确"（\(h_1(n) \geq h_2(n)\) 且均为可容许），则 \(h_1\) 支配 \(h_2\)，A* 用 \(h_1\) 扩展的节点数更少（或相等）。
搜索算法对比
| 算法 | 完备 | 最优 | 时间 | 空间 |
|---|---|---|---|---|
| BFS | 是 | 是（等代价） | \(O(b^d)\) | \(O(b^d)\) |
| DFS | 否 | 否 | \(O(b^m)\) | \(O(bm)\) |
| UCS | 是 | 是 | \(O(b^{C^*/\epsilon})\) | \(O(b^{C^*/\epsilon})\) |
| Greedy | 否 | 否 | \(O(b^m)\) | \(O(b^m)\) |
| A* | 是 | 是（可容许 \(h\)） | 取决于 \(h\) | 指数级 |
2026.06