算法设计第 5 章：回溯法——解空间树、剪枝函数与六道经典题
回溯法是"聪明的穷举"。它把解空间组织成一棵树，用深度优先遍历枚举候选解，一旦发现当前部分解不可能补全成合法解（或不可能更优），立刻回退整棵子树。回溯的效率完全取决于剪枝函数的质量——不加剪枝它就是纯穷举，加了好的剪枝常常能把指数级问题做到实际可跑。这一章学完，应当能对一个问题画出解空间树、写出约束函数与限界函数，并估出剪枝后的实际搜索量。
一、解空间：子集树与排列树
解空间是问题所有可行解的集合，通常组织成一棵树，从根到叶的一条路径对应一个候选解。
| 树型 | 每层分支 | 叶子数 | 适用问题 |
|---|---|---|---|
| 子集树 | 2（选/不选） | 2ⁿ | 装载、0-1 背包、最大团、符号三角形 |
| 排列树 | n−i+1（剩余可选） | n! | 批处理调度、旅行商、n 后（按行放列） |
| m 叉树 | m（颜色/位置） | mⁿ | 图的 m 着色 |
子集树的结点总数是 2^(n+1) − 1，排列树是 1 + n + n(n−1) + … ≈ e·n!。这两个数字决定了回溯的理论下界：不剪枝时子集树问题至少 Ω(2ⁿ)，排列树至少 Ω(n!)，所以任何回溯算法的价值都在剪枝上。
二、深度优先搜索与剪枝框架
回溯 = DFS + 剪枝 + 现场恢复。三个动作缺一不可，其中"恢复现场"最容易被漏：进入分支前修改状态，回溯时必须改回去，否则兄弟分支会看到脏数据。
递归框架（以子集树为例）：
void backtrack(int i) {
if (i > n) { output(x); return; } /* 到达叶子，得到一个解 */
for (int j = 0; j <= 1; j++) {
x[i] = j;
if (constraint(i) && bound(i)) { /* 约束 + 限界 */
/* 更新状态 */
backtrack(i + 1);
/* 恢复状态 */
}
}
}
两个剪枝函数分工明确：
- 约束函数 constraint：判断部分解是否违反问题的硬性条件（如 n 后同列同对角线冲突），违反则整棵子树无解。
- 限界函数 bound：判断部分解是否还有可能优于当前最优（如背包的上界小于 bestp），不可能则剪掉，只影响最优性搜索，不影响可行性。
约束剪的是"非法"，限界剪的是"不划算"。 求所有解时只能靠约束，求最优解时两者都用。
三、装载问题与 0-1 背包
装载问题：n 个集装箱装上两艘船，载重 c₁、c₂，要求第一艘尽量装满（剩余全部装第二艘）。这是子集树：xᵢ = 1 表示装第一艘。
- 约束：当前重量 cw + wᵢ ≤ c₁。
- 限界：设剩余未处理重量为 r，若 cw + r ≤ bestw 则即便全装也不如当前最优，剪枝。
- 复杂度最坏 O(2ⁿ)，剪枝后通常远小。
0-1 背包回溯：同样是子集树。限界函数用贪心上界——把剩余物品按单位价值降序，能整取就整取，第一个装不下的取一部分填满，得到的价值是当前分支可达的上界 ub；若 ub ≤ bestp 则剪枝。这个"松弛成小数背包"的上界很紧，是背包回溯能实用的关键。
注意：上界必须可采纳（admissible），即不能低估，否则会剪掉真正的最优解。宁可松一点，不可错一点。
四、n 后问题与图的 m 着色
n 后问题：n×n 棋盘放 n 个皇后，互不同行、同列、同对角线。按行放置后，每行恰好一个，解空间退化为列号的排列树，规模 n!。
约束函数检查三条：同列 x[j] == x[i]；主对角线 x[j] - x[i] == j - i；副对角线 x[j] - x[i] == i - j。位置 i 的皇后只与已放的 1..i−1 比较，代价 O(i)。总复杂度上界 O(n!)，实际因剪枝极小：n = 8 时只有 92 个解，搜索结点约 2000 个。
图的 m 着色：给无向图 G 的 n 个顶点染 m 种颜色，相邻顶点不同色。解空间是 m 叉树（mⁿ 个叶子），约束只需检查已着色邻居的颜色是否冲突。判断 m 着色是否有解是 NP 完全的（m ≥ 3），回溯是标准解法；实际优化是按度数降序选择下一个顶点，先处理约束最强的点，剪枝效果显著。
五、批处理调度与符号三角形
批处理作业调度：n 个作业在两台机器上按相同次序加工，求完成时间之和最小的调度。解空间是排列树（n!），每个叶子是一种加工顺序。限界函数：当前已完成作业的时间之和 + 剩余作业的最短可能完成时间下界，超过 best 即剪。
符号三角形：第一行 n 个 +/-，下一行由上方两个符号决定（同号为 +，异号为 -），共 n(n+1)/2 个符号，要求 + 与 - 个数相等。
- 必要条件：n(n+1)/2 为偶数，否则直接无解（这是 O(1) 的前置判断，能砍掉一半输入）。
- 解空间是子集树（第一行确定全部），2ⁿ。
- 剪枝：若当前
+的个数已超过总数一半，或-的个数已超过一半，立即剪——因为后续只会增加，不可能再平衡。
六、效率分析与优化策略
回溯的最坏复杂度等于解空间大小（2ⁿ、n!、mⁿ），剪枝只降低常数与平均规模，除非剪枝强到能把分支数压成多项式，否则量级不变。这是理论分析与实际表现的落差所在：n 后理论 O(n!)，实际 n = 20 也能秒出。
四条实用优化：
- 择优搜索顺序：先试约束最强、最可能失败的分支（如着色按度数降序、背包按单位价值降序），让剪枝尽早发生。
- 对称性消除：n 后第一行只需试前 n/2 列（镜像对称），直接砍半；圆排列问题固定第一个元素。
- 可行性预判：进入递归前用 O(1) 的必要条件排除整片区域（符号三角形的奇偶判断）。
- 迭代加深 / 限深搜索：解可能很浅时避免深陷无效分支。
还有一条实现经验：剪枝函数必须足够便宜。若判一次界要 O(n²)，而它只剪掉常数个分支，得不偿失。剪枝的收益 ≈ 剪掉的子树规模 × 其占比，成本 = 每结点判界开销 × 结点数，只有当收益远大于成本时才值得加。这也是为什么背包的上界用"贪心填满"（O(n log n) 预处理后 O(1) 摊还）而不是"再解一次背包"。
易错点
- 回溯后忘记恢复状态，兄弟分支读到脏数据。
- 限界函数低估上界，剪掉了最优解。
- 求所有解时误用限界函数，导致只输出一个解。
- n 后判对角线时只用
|i−j|判一条，漏掉另一条。 - 认为剪枝改变了最坏复杂度，答题时写"优化后为多项式"。
这一章在整门课里的位置
回溯是第 2 章 DFS 思想的系统化，也是第 6 章分支限界的对照物：同一棵解空间树，回溯用栈做深度优先，分支限界用队列/堆做广度或最佳优先。它同时是第 8 章 NP 完全问题的"标准暴力解法"——NPC 问题没有多项式算法，回溯加剪枝就是工程上的现实答案。
本文是《算法设计与分析（89 讲）》第 5 章的知识点摘要。完整板书与代码见 课程页；上一章 贪心算法，下一章 分支限界法。
相关课程
这篇笔记涉及的主题，我录过对应的视频课程：
- 算法设计与分析（89讲） 89 讲