第 III 篇 · 搜索（第 3–5 章）

搜索是"想清楚再行动"的算法化：状态空间里找一条到目标的路径。从盲目搜索到启发式 A*，再到对抗博弈与 CSP——这一篇是符号 AI 的发动机，也是路径规划、解谜、排程的直系工具。

无信息搜索：盲人的走法

状态空间（初始态、动作、转移、目标测试、代价）+ 前沿（frontier）数据结构 = 通用搜索骨架。策略对比的核心指标：完备性、最优性、时间/空间复杂度（分支因子 $b$、深度 $d$）：

图搜索的重复状态检测是效率的分水岭（树搜索会指数重复）。

• BFS：完备最优（等代价）、空间 $O(b^d)$ 爆炸；
• 深度优先：空间省（$O(bd)$）但不完备不最优；迭代加深 DFS（IDDFS）取两者之长：DFS 的空间 + BFS 的最优性；
• 代价一致搜索（UCS）：按路径代价 $g(n)$ 展开——最优但慢。

有信息搜索：A* 与启发式

$h$ 可采纳（不高估 $h \le h^*$）⟹ **A\* 树搜索最优；一致性（$h(n) \le c(n, n') + h(n')$）⟹ 图搜索也最优。启发式的来源：松弛问题（八数码的错位数、曼哈顿距离都是"允许更多动作的松弛"的精确解）；支配关系**（$h_2 \ge h_1$ 处处成立则 $h_2$ 更强）与可采纳启发式的取 max 组合。IDA*、递归最优搜索处理内存瓶颈。

对抗搜索与 CSP

• 极小极大搜索：双方完美博弈的 minimax 值；$\alpha$-$\beta$ 剪枝（同 root 结果，节点数从 $O(b^m)$ 降到 $O(b^{m/2})$——搜索深度翻倍）；启发式评估函数 + 截断搜索（象棋/围棋引擎的骨架）；蒙特卡洛树搜索（UCB 选择 + 随机模拟 + 反向传播）让围棋级搜索成为可能（AlphaGo 的核心部件）；
• 约束满足问题（CSP）：变量 + 值域 + 约束。回溯搜索的加速三件套：MRV（最少候选优先）、度启发式、前向检查与弧一致性（AC-3）传播——CSP 是排班、排课、数独的通用语言。

老师的提醒

• 选搜索算法的决策树：要最优路径？状态可枚举？有像样的启发式（可采纳）？内存多大？——四个答案直接定位 UCS/A*/IDA*/局部搜索。
• A* 的工程直觉：$h$ 越接近 $h^*$ 越少展开节点；完美启发式（$h = h^*$）则直奔目标——启发式设计就是在逼近 $h^*$。

自检

• BFS/DFS/IDDFS/UCS 的完备性、最优性、复杂度对比表。
• 可采纳与一致性的定义及各自保证的最优性范围？
• $\alpha$-$\beta$ 剪枝的最好情形复杂度与 CSP 弧一致性的作用？

更深一层：搜索是"想清楚再行动"的算法化

无信息搜索（BFS/DFS/IDDFS/UCS）的对比表格值得作为"算法选型卡"记住：BFS 完备最优但空间爆炸、DFS 空间省但不完备不最优、IDDFS 取两者之长（DFS 空间 + BFS 最优性）、UCS 按路径代价展开（最优但慢）。**启发式搜索（A\*）**的可采纳性（$h \le h^*$ 不高估）是一切保证的前提——松弛问题（八数码的曼哈顿距离 = "允许穿墙"的松弛）是启发式的设计方法。

$\alpha$-$\beta$ 剪枝把 minimax 从 $O(b^m)$ 压到 $O(b^{m/2})$——搜索深度翻倍是博弈 AI 的发动机；蒙特卡洛树搜索（MCTS：UCB 选择 + 随机模拟 + 反向传播）让围棋级搜索成为可能（AlphaGo 的核心部件）。CSP（约束满足问题）的回溯加速三件套（MRV/度启发式/前向检查）是排班排课的通用语言。

推导细读：A* 的"$h$ 越准越省"经济学

A* 的效率公式值得量化：展开节点数由 $h$ 的准确度决定——完美启发式（$h = h^*$）直奔目标零浪费，$h = 0$（Dijkstra）盲目全展开。**启发式设计 = 在逼近 $h^*$——模式数据库（Pattern Database，预存子问题的精确解）是"自动造好启发式"的方法；支配关系（$h_2 \ge h_1$ 处处成立则 $h_2$ 更强）与可采纳启发式的取 max 组合是组合多个弱启发式成强启发式的技巧。搜索问题的建模质量优先于搜索算法**——状态表示的粒度直接决定搜索空间大小。

在真实世界里：搜索的"现代变身"

搜索的现代变身清单：路径规划（A* 是自动驾驶与机器人的默认规划器）、自动定理证明（归结 = 搜索 + 逻辑）、程序合成（搜索 + 约束求解）、AlphaGo（MCTS + 深度网络评估）。搜索从未过时，它只是学会了与机器学习搭档——神经符号系统（Neuro-symbolic）正是"学习给启发式、搜索做推理"的合体。

专题深入：博弈搜索的"双树剪枝"完整版

AIMA 第五-六章对抗搜索的完整装备：minimax（双人零和完全信息：MAX 与 MIN 层交替、递归求值——完备搜索复杂度 $O(b^m)$ 与单智能体相同但无法用"最优解"绕过：对手也在选择）；α-β 剪枝（$\alpha$ 是 MAX 已保证下界、$\beta$ 是 MIN 已允许上界，$\alpha \ge \beta$ 剪断——最好情况复杂度 $O(b^{m/2})$ ⟹ 同样时间看深一倍；剪枝效率取决于节点访问顺序（最好着法优先——移动排序是 α-β 的效率发动机）；迭代加深 + 置换表（transposition table 记录已算局面）是实战三件套）；不完美实时决策（评估函数替代终局值 + 截断深度——评估函数的质量决定棋力：国际象棋的材料子力 + 棋型特征加权）；蒙特卡洛树搜索（选择-扩展-模拟-回传四步、UCT 公式 $\arg\max\left[\frac{w_i}{n_i} + c\sqrt{\frac{\ln t}{n_i}}\right]$——"UCB1 的树版本"：无需评估函数、用随机模拟统计胜率——围棋与不完全信息游戏的现代引擎核心）。

推导细读：约束满足问题的"传播引擎"完整版

第六章 CSP 的完整引擎：问题形式（变量 + 值域 + 约束——地图染色、课程表、数独）；回溯搜索（DFS + 一致性剪枝：前向检查（赋值后立刻删除邻居的失效值）、弧一致性 AC-3（$X \to Y$ 弧一致：X 的每个值都有 Y 的支持；维护队列传播——传播失败提前回溯，剪枝发生在搜索树深处之前）；变量与值排序启发式（MRV 最剩余值（失败优先）、度启发式、LCV 最少约束值——"最不确定的先决定、最少伤害的方式决定"）；结构分解（树状 CSP 线性可解、割集调节）；局部搜索（最小冲突启发式——随机重启动 + 最小冲突解数百万皇后级问题）。"约束传播 + 智能排序"让指数问题常在多项式时间可解——这是 CSP 对 AI 方法论的最大贡献：把约束当一等公民而非事后检查。

工程案例细节：博弈与 CSP 的产业出口工程版

五-六章的工程出口：游戏引擎的搜索层（国际象棋 Stockfish 的 α-β + NNUE 评估（"经典搜索 + 神经评估"的混合流派——AlphaZero 的纯 MCTS 流派的对手）、围棋 KataGo 的 MCTS + 残差网络开源引擎）；排班与调度（护士排班、机组排班的 CSP/CP-SAT 求解器（Google OR-Tools 的 CP-SAT 是工业标准——"约束建模 + SAT 引擎"的航班机组排班每年省数亿美元）；硬件验证与数独（SAT 求解器的 CDCL（冲突驱动子句学习——"冲突分析 + 回跳"是现代 SAT 的灵魂，芯片形式验证与网络配置的底座）；MCTS 的泛化应用（内容规划、分子合成的逆合成分析（AiZynthFinder——"化学家的博弈树"）、程序合成的搜索层）；实时决策（MOBA/FPS 游戏机器人的分层搜索 + 评估网络）。"搜索无处不在"的证明：从棋盘到晶圆厂排产，同一套剪枝与传播在跑。