第五章 组合搜索——如何系统地探索解空间
开篇：为什么需要组合搜索？
三个看似简单的问题
问题 1：八皇后 在 8×8 棋盘上放置 8 个皇后，使其互不攻击。
- 看起来简单："放 8 个棋子而已"
- 实际困难：前 7 步都对，第 8 步无路可走
- 困惑：问题出在哪里？
问题 2：Sudoku 填满部分填充的棋盘，满足规则。
- 看起来简单："填数字而已"
- 实际困难：朴素方法需要百万步
- 困惑：为什么差距这么大？
问题 3：TSP 找一条访问所有城市的最短回路。
- 看起来简单："选路线而已"
- 实际困难：城市数增加，时间爆炸
- 困惑：如何高效求解？
这三个问题的共同特征：解空间巨大，但合法解稀疏。
学习目标
完成本章学习后，你将能够：
- 实现回溯框架：系统枚举解空间，保证不遗漏合法解
- 设计剪枝策略：将百万步优化到几十步，理解约束的作用
- 应用 A 算法*：用启发函数指导搜索，保证最优性
- 理解启发式搜索：在最优性和效率之间权衡
- 连接 LLM 推理：理解搜索策略与推理策略的同构性
关键洞察：组合搜索的核心问题是"如何高效地探索巨大空间"——算法的效率取决于约束强度和启发质量。
核心叙事：搜索策略与 LLM 推理的同构性
一个令人惊讶的发现
2023 年，研究者发现：大语言模型（LLM）在推理时遇到的困难，与经典搜索算法的局限性惊人地相似。
| 搜索策略 | LLM 推理对应 | 局限性转移 |
|---|---|---|
| 贪心解码 | 每步最高概率 | 重复陷阱 |
| 思维链（CoT） | 线性推理 | 一步错全错 |
| 思维树（ToT） | 多候选探索 | 评估依赖 |
| 思维图（GoT） | 思想聚合 | 启发依赖 |
这不是类比，而是同构——同一计算思想的不同实例化。
为什么这个对应关系重要？
- 诊断 LLM 失败：看到重复输出 → 知道是贪心陷阱 → 用 sampling 解决
- 设计改进策略：搜索策略的改进技术 → 直接迁移到 LLM
- 评估复杂度：ToT 的计算成本 = 回溯的搜索树规模
章节结构
本章遵循标准认知规律：
问题情境 → 直观思路 → 规范定义 → 算法实现 → 正确性分析 → 复杂度分析 → 变式练习各节要点
5.1 回溯框架（~450 行）
- 问题情境：八皇后的困境——前 7 步都对，第 8 步无路可走
- 直观思路：从暴力枚举 → DFS → 回溯的演化
- 核心内容：五子程序框架、正确性保证、复杂度分析
- 关键代码：八皇后求解器
- 思考题：为什么回溯保证正确但不保证效率？
5.2 剪枝策略（~500 行）
- 问题情境：Sudoku 的速度差距——百万步 vs 48 步
- 直观思路：提前发现死胡同、先填候选最少的位置
- 核心内容：前瞻剪枝、最受约束优先、约束传播
- 关键代码：完整剪枝 Sudoku 求解器
- 思考题：剪枝会不会删掉合法解？
5.3 A 搜索*（~450 行）
- 问题情境：同样的最优解，效率差距百倍
- 直观思路：用松弛问题求下界
- 核心内容：可容许性、启发函数设计、IDA*
- 关键代码：TSP 的 A* 求解器
- 思考题：为什么启发函数质量这么关键？
5.4 启发式搜索（~350 行）
- 问题情境：复杂启发反而更差（顶点覆盖）
- 直观思路：允许"错误"转移，跳出局部最优
- 核心内容：爬山法、模拟退火、代价函数设计
- 关键代码：TSP 的 SA 求解器
- 思考题：为什么模拟退火需要温度调度？
5.5 LLM 推理同构性（~400 行）
- 问题情境：LLM 卡在重复输出
- 直观思路：搜索策略 → LLM 推理的映射
- 核心内容：四对策略映射、ToT/GoT 框架、局限性转移
- 思考题：理解搜索策略能帮助理解 LLM 推理吗？
综合练习（~350 行）
- 问题情境与直觉建立（5 题）
- 方法应用与实现（5 题）
- 错误诊断与反例（5 题）
- 方案比较与权衡（5 题）
- 变式与边界条件（5 题）
- 开放设计（5 题）
- 综合应用（5 题）
- 思考题（5 题）
- LLM 协同实验（5 题）
阅读路径建议
路径一：循序渐进（推荐）
5.1 → 5.2 → 5.3 → 5.4 → 5.5 → 练习适合：希望系统掌握组合搜索的读者
路径二：LLM 导向
5.5 → 遇到概念回查前置章节 → 练习适合：主要关注 LLM 推理应用的读者
路径三：快速入门
5.1（回溯框架） → 5.5（LLM 连接） → 练习适合：希望快速建立核心概念的读者
关键概念预告
三个"为什么"
为什么回溯保证正确但不保证效率？
- 正确性：系统枚举保证不遗漏
- 效率：解空间可能巨大（取决于约束强度）
为什么剪枝不会删掉合法解？
- 剪枝条件基于"必然无解"的逻辑
- 删掉的是无效分支，不是"可能无解"的分支
为什么 LLM 会"卡住"？
- 贪心解码困在局部最优（重复模式）
- 类似爬山法困在局部山峰
三个"如何"
如何将百万步优化到几十步？
- 前瞻剪枝：提前发现死胡同
- 约束传播：实时更新候选集
如何保证 A 的最优性？*
- 可容许启发函数（不高估）
- 下界紧度影响效率
如何设计好的 LLM 推理策略？
- 从搜索策略迁移经验
- 引入外部验证（类似剪枝的规则检查）
写作风格说明
本章遵循教材设计哲学的七大特征：
- 问题驱动：先让学生感受到"为什么需要"，再给出定义
- 展示推理过程：从朴素方案到优化方案的演化
- 直觉先于形式：先描述直觉图景，再形式化
- 解释难点：回答"为什么这样定义""这个方法是怎么想到的"
- 例子多样化：最简单的例子、反例、变式、综合应用
- 练习多样化：不只是三层，包括错误诊断、方案比较、开放设计
- 终极目标：让读者面对新题时知道从哪里开始想
写在前面：本章的每一节都以"问题情境"开场——先感受到困难，再理解解决思路。因为理解"为什么需要"，比理解"怎么做"更重要。
参考文献：
- Skiena S S. The Algorithm Design Manual[M]. 3rd ed. Springer, 2020.
- Yao S, Yu D, Zhao J, et al. Tree of Thoughts[C]//NeurIPS. 2023.
- Besta M, et al. Graph of Thoughts[C]//AAAI. 2024.
- Huang J, et al. LLMs Cannot Self-Correct Reasoning[C]//ICLR. 2024.
- Snell C, et al. Scaling LLM Test-Time Compute[J]. 2024.