06 回溯法与分支限界法

本章对应考试中的：B1 三子句 SAT（样题2/试卷2）、B2 四子句 SAT（2011期末 等，高频，要画搜索树）、BB1 中转贸易（2011影印/2020/merged，高频）、BB2 通信网络（2012影印/2013）、BB3 优先队列式最短路径（试卷5）、BB4 队列式电路布线（试卷5）、选择题第 1～5、11、12 题、作业 O4 整数规划。

核心考点

回溯法和分支限界法都建立在解空间树上（这个概念在 00_算法策略总论与通用解题法.md 第 0.4 节已总览，这里深入）。

回溯法（backtracking）：在解空间树上做深度优先搜索，遇到违反约束的分支就剪掉、退回。用于找出满足约束的解。考试主要考 SAT 求解 + 画搜索树。
分支限界法（branch and bound）：也在解空间树上搜，但用界函数估算前景，按优先级搜并剪掉没希望的分支。用于求最优解。考试主要考四问框架（构造二叉搜索树 / 遍历原则 / 界 / 伪代码）。

从零开始的前置知识

解空间树、子集树、排列树

解空间树（state-space tree）：把一个问题所有"可能的解"按"一步步做决策"的过程画成一棵树。树根是"什么都还没决定"，每往下一层多决定一个变量，叶子是一个完整的候选解。

子集树（subset tree）：每个元素只有"选/不选"两种决策时形成的树。 $n$ 个元素时，叶子有 $2^{n}$ 个。（选择题第 11 题：含 $n$ 个元素的子集树问题，最坏情况叶结点数目为 $2^{n}$ ，答案 B。）
排列树（permutation tree）：要确定 $n$ 个元素的排列顺序时形成的树，叶子有 $n!$ 个。（选择题第 12 题：含 $n$ 个元素的排列树问题，最坏情况计算时间复杂性为 $n!$ ，答案 C。）

活结点、扩展结点、死结点

搜索解空间树时：

活结点（live node）：已经生成、但它的孩子还没全部生成完的结点。
扩展结点（E-node）：当前正在生成孩子的那个结点。
死结点（dead node）：不再需要扩展的结点（已被剪枝或孩子已全部处理）。

回溯法用深度优先：一个结点在搜索往返过程中可能多次成为扩展结点。分支限界法：一个活结点一旦成为扩展结点，就一次性生成它的全部孩子，之后不再成为扩展结点，所以"一个活结点最多有一次机会成为扩展结点"（选择题第 4 题答案 B）。

回溯法的工作方式

回溯法 = 深度优先搜索（DFS）+ 剪枝：

从根出发，沿一条分支一直往下走（不断给变量赋值）。
每走一步检查约束条件：若当前部分解已经违反约束、不可能再扩展成合法解，就剪枝——不再往下，退回上一个分叉点，换另一条分支。这个"退回"就是"回溯"。
走到叶子且满足全部约束，就得到一个解。

分支限界法的工作方式

分支限界法也在解空间树上搜，但多了一个界（bound）：估计"从当前结点往下，最好/最差能得到多优的解"。靠这个界：① 优先扩展最有希望的结点（按优先级，而非死板地深度优先）；② 把"界已经比当前找到的最优解还差"的整个分支剪掉。

它有两种常见方式（由"从活结点表里怎么选下一个扩展结点"决定）：

队列式（FIFO）分支限界：活结点表是队列（先进先出），等价于广度优先搜索（一层一层地搜）。
优先队列式分支限界：活结点表是优先队列，每次取出"界值最优"（如耗费最小）的结点先扩展。

选择题第 5 题：从活结点表选下一扩展结点的方式中，栈式分支限界法不是常见方式（答案 C）——栈是后进先出、对应深度优先，那是回溯法的搜索方式。常见的是队列式、优先队列式、FIFO 式。

回溯法 vs 分支限界法（选择题对比）

选择题	答案与要点
第 1 题：二者关系	C：求解目标相同（都在解空间树上搜解），搜索方式不同
第 2 题：回溯的搜索方式	A：深度优先
第 3 题：解空间树不会是	D：无序树（解空间树是有序树/子集树/排列树）
第 4 题：活结点最多一次机会成为扩展结点的是	B：分支限界法
第 5 题：不是常见分支限界方式的是	C：栈式分支限界法

答题模板

模板 D：回溯法解 SAT（画搜索树）

【分支策略】按变量顺序 p,q,r,s 依次取值，左枝=1(真)、右枝=0(假)。
【化简规则】每代入一个变量，对每个子句（OR 连接的一组文字）化简：
   - 子句里有文字为真 → 整个子句被满足 → 删去该子句；
   - 子句里某文字为假 → 从子句中划掉该文字；
   - 子句变成空（所有文字都为假）→ 矛盾 → 剪枝、回溯；
   - 所有子句都被删光 → 找到一组可满足赋值。
【画树】每个结点写出"化简后的 CNF"，标注在哪剪枝。
【结论】给出一组可满足赋值（或说明无解）。

模板 E：分支限界法四问

① 构造搜索树（二叉）：每个对象/边一层，左枝=选/经过，右枝=不选/不经过；
   结点状态 = (已选集合 S, 已弃集合 V)。
② 遍历原则：不满足剪枝条件且有子树就前进；多选择处先左(选)后右(不选)分支；
   左子树搜完或被剪则回溯到父结点。剪枝条件 = 界比当前最优差 或 违反约束。
③ 界：下界 = 已付出的代价 + 由当前点到终点的"最小剩余代价"
   （把约束放宽后求得，所以是合法下界，正确且有效）；
   上界 = 迄今搜索到的最优解。当 下界 ≥ 上界 时剪枝。
④ 伪代码：递归 search(S, V)，到终点更新最优；否则若不满足剪枝条件，
   先递归左子树(选)、再递归右子树(不选)。

逐题精解

B1 三子句 SAT（`样题2`/`试卷2`）

原题：用回溯法求解 SAT： $(p \lor q) \land (\neg q \lor r) \land (\neg p \lor r)$ ，画出搜索树，标明分支策略和各结点状态（化简的 CNF）。

前置：CNF 与 SAT。 合取范式（CNF） 是若干子句用 $\land$ （与）连接，每个子句是若干文字用 $\lor$ （或）连接；文字是一个变量（如 $p$ ）或它的否定（如 $\neg p$ ）。SAT（可满足性问题） 就是问：能否给每个变量赋真（1）或假（0），使整个公式为真（即每个子句都至少有一个文字为真）。

求解（按 $p \to q \to r$ ，左 1 右 0）：

取 $p = 1$ ： $(p \lor q)$ 中 $p = 1$ 为真 → 删； $(\neg p \lor r)$ 中 $\neg p = 0$ → 划掉，剩 $(r)$ 。化简为 $(\neg q \lor r) \land (r)$ 。
- 取 $q = 1$ ： $(\neg q \lor r)$ 中 $\neg q = 0$ → 剩 $(r)$ ；还有 $(r)$ 。化简为 $(r) \land (r)$ ，需 $r = 1$ 。
  - 取 $r = 1$ ：两个 $(r)$ 都为真 → 全部删光 → 找到解。

一组可满足赋值： $p = 1, q = 1, r = 1$ （代入原式，三个子句都为真）。

B2 四子句 SAT（`2011期末` 等，高频，画树）

原题：用回溯法求解 SAT： $(p \lor q \lor s) \land (\neg q \lor r) \land (\neg p \lor r) \land (\neg r \lor s)$ ，画出搜索树并标明各结点状态。

搜索树（按 $p \to q \to r \to s$ ，左枝=1、右枝=0）：

                  (p∨q∨s)(¬q∨r)(¬p∨r)(¬r∨s)
               p=1 /                          \ p=0
         (¬q∨r)(r)(¬r∨s)                 (q∨s)(¬q∨r)(¬r∨s)
        q=1 /         \ q=0              q=1 /            \ q=0
    (r)(r)(¬r∨s)    (r)(¬r∨s)       (r)(¬r∨s)         (s)(¬r∨s)
      r=1 ↓            r=1 ↓            r=1 ↓             s=1 ↓
       (s)              (s)              (s)              (满足)
      s=1 ↓
     全部满足 √

沿最左路径 $p = 1, q = 1, r = 1, s = 1$ ：

$p = 1$ → 删 $(p \lor q \lor s)$ ， $(\neg p \lor r)$ 剩 $(r)$ → 状态 $(\neg q \lor r) (r) (\neg r \lor s)$ ；
$q = 1$ → $(\neg q \lor r)$ 剩 $(r)$ → 状态 $(r) (r) (\neg r \lor s)$ ；
$r = 1$ → 两个 $(r)$ 删， $(\neg r \lor s)$ 中 $\neg r = 0$ 剩 $(s)$ → 状态 $(s)$ ；
$s = 1$ → $(s)$ 满足 → 全部子句满足。

一个解： $p = q = r = s = 1$ 。 剪枝说明：分支过程中凡某个子句被化简成空（所有文字为假），就剪枝回溯；本题里 $(\neg r \lor s)$ 在 $r = 1$ 时会强制要求 $s = 1$ 。（此公式还有其它解，如 $p = 0, q = 0, s = 1$ 。）

BB1 中转贸易（`2011影印`/`2020`/`merged`，高频）

原题：A、B 两国未直接通商。与 A 直接通商的有 20 国（ $C_{1} \dots C_{20}$ ），与 B 直接通商的有另外 30 国（ $C_{21} \dots C_{50}$ ）。50 国之间不是两两通商，税率由对称矩阵 $R$ 给出（ $\infty$ 表示不能直接通商），各国通关时间由向量 $T$ 给出。安排一个经过若干中转国的贸易计划，使缴纳的税费最低，且整个交易在时间 $t$ 内完成。要求回答四问：① 如何构造搜索树（二叉）；② 遍历原则；③ 界是什么、为何正确有效；④ 写伪代码。

① 构造二叉搜索树：每个国家对应树的一层。结点状态记为 $(S, V)$ ， $S$ = 已经决定途经的国家序列， $V$ = 已经决定舍弃的国家集合。考察国家 $c$ 时：左子树表示"途经 $c$ "，状态变为 $(S \cup {c}, V)$ ；右子树表示"不途经 $c$ "，状态变为 $(S, V \cup {c})$ 。每个国家"选或不选"两枝，构成二叉搜索树。

② 遍历原则：当前结点不满足剪枝条件且还有子树时前进；在有选择的地方分支（先走左枝 = 途经，再走右枝 = 不途经）；左子树走不通（被剪或搜完）就转右子树；某结点的子树全部遍历完或被剪掉，就向父结点回溯。

剪枝条件（满足任一就剪）：

已花税费 + 当前点到 B 国的最小剩余税费 ≥ 当前已知最优（最低）税费和（不可能更优）；
已花时间 + 当前点到 B 国的最小剩余时间 > t（违反时间约束）。

③ 界：

下界 = 已花税费 + 从当前点到终点 B 的最小剩余税费。这个"最小剩余税费"是把其它约束放宽后、预先用 Dijkstra 算法在税费矩阵 $R$ 上求出的"当前点到 B 的最短（最低税费）路径"。因为它放宽了约束，所以是真实最优代价的一个合法下界（真实代价只会更高，不会更低），因此用它来剪枝是正确的；又因为它能尽早砍掉没希望的分支，所以是有效的。
同理，用时间矩阵预先求出"到 B 的最小剩余时间"，做时间可行性剪枝。
上界 = 迄今搜索到的最优（最低）税费和。

④ 伪代码：

text

输入：税率矩阵 R，时间矩阵 T，限定时间 t，起点 i（A），终点 j（B）
预处理：用 Dijkstra 求每个点到 j 的【最小剩余税费】和【最小剩余时间】
最优解 P ← 空; 最优税费 V ← ∞
search(S, Vset):                          // S=已途经序列, Vset=已舍弃集
    if 当前点到达 j:
        更新最优解 P 与最优税费 V
    else if 不满足剪枝条件:                 // 下界 < V 且 时间可行
        对下一个待决策国家 c:
            search(S ∪ {c}, Vset)         // 左：途经 c
            search(S, Vset ∪ {c})         // 右：不途经 c
return P, V

BB2 通信网络（`2012影印`/`2013`）

原题：建立连通五个区共 50 个站点的有线通信网络，敷设费用由对称矩阵 $C$ 给出，每两站点间需建地井数由对称矩阵 $U$ 给出。设计总费用最小的无环网络，使总地井数不超过 $U_{M A X}$ 、跨区线路总数不超过 $D_{M A X}$ （各站点所属区由向量 $D$ 给出）。同样回答四问。

解答框架（与 BB1 同构，只是把"选国家"换成"选边"）：

① 二叉搜索树：每条边对应一层，左枝 = 选这条边，右枝 = 不选这条边。
② 遍历原则：同 BB1，先左（选边）后右（不选边），不满足剪枝且有子树就前进，否则回溯。
③ 界：下界 = 已选边的费用 + 把当前已选边扩成一棵生成树所需的最小剩余费用（可用 Kruskal/最小生成树在剩余边上松弛求得，是合法下界）；上界 = 迄今最优（最低）总费用。
剪枝：地井总数 $> U_{M A X}$ 、跨区线路数 $> D_{M A X}$ 、或加入某边会形成环，都剪枝。
④ 伪代码：结构与 BB1 相同，递归对每条边做"选/不选"两枝，到选够连通生成树时更新最优。

BB3 优先队列式分支限界——单源最短路径（`试卷5`）

原题：用优先队列式分支限界法求图中从 $s$ 到 $t$ 的单源最短路径，画出求得最优解的解空间树。被舍弃的结点用 ✕ 标记，中间解结点用单圆圈 ○ 框，最优解用双圆圈 ◎ 框。

要点：用优先队列（以"从 $s$ 到当前结点的已走路径长度"作为优先级）来管理活结点，每次取出路径长度最小的结点扩展。某个结点一旦被取出（出队），它的最短距离就定型（这与 Dijkstra 算法一致）。对那些"当前路径长度已经不可能比已知最优更短"的分支，用 ✕ 剪除。一直扩展到 $t$ 出队，即得最短路径。

BB4 队列式分支限界——电路板布线（`试卷5`）

原题：电路板中阴影方格是封锁格，按队列式分支限界法确定 $a$ 到 $b$ 的最短布线方案（只能沿直线或直角走），标出求最优解时各方格情况。

要点：用队列（FIFO），等价于广度优先的波前扩散——从起点 $a$ 出发，把距离为 1 的相邻格、距离为 2 的格……一圈一圈向外标记距离，遇到封锁格就跳过不标。当到达终点 $b$ 时，它的距离标号就是最短布线长度；再从 $b$ 沿"距离逐格减 1"的方向回溯，得到一条最短布线路径。

作业 O4：整数规划（电脑组装，`试卷6`，20 分）

原题：一周 150 小时内组装个人电脑和笔记本，个人电脑每台挣 50 元、笔记本每台挣 40 元；组装个人电脑需 3 小时、占 8 平米，笔记本需 5 小时、占 5 平米；因缺 CPU 最多组装 20 台笔记本；现有 300 平米场所。求利润最大的组装方案。

建模：设个人电脑 $x$ 台、笔记本 $y$ 台，

max 50 x + 40 y s.t. 3 x + 5 y \leq 150, 8 x + 5 y \leq 300, 0 \leq y \leq 20, x, y \geq 0 且为整数 .

逐项解释： $3 x + 5 y \leq 150$ 是工时约束； $8 x + 5 y \leq 300$ 是场地约束； $y \leq 20$ 是笔记本上限； $x, y$ 取非负整数。这是一个整数规划问题，可用分支限界（先解放松整数限制的线性规划，再对小数变量分支取整）或动态规划求解。

高频陷阱 / 易错点小结

回溯 = 深度优先 + 剪枝；分支限界 = 界函数 + 队列/优先队列，求最优。别把两者搞反（选择题年年考）。
SAT 化简规则：子句里有真文字就删整句；某文字为假就划掉该文字；子句变空就剪枝。画树时每个结点要写出化简后的 CNF。
分支限界四问是固定采分点，即使树画不全，把"二叉树构造 / 遍历原则 / 界 / 伪代码"四块的通用描述写上也有分。
界要说清"为什么正确、为什么有效"：放宽约束求得 → 合法下界（正确）；能尽早剪枝（有效）。
队列式 = BFS、优先队列式 = 最小耗费优先、栈式 = 回溯（不是分支限界）。
子集树叶子 $2^{n}$ 、排列树叶子 $n!$ ，别记反（选择 11、12）。

自测清单

[ ] 说清回溯法与分支限界法的相同点（解空间树搜索）和不同点（DFS vs BFS/优先队列）。
[ ] 默写 SAT 的三条化简规则，并对 B2 画出搜索树、给出解 $p = q = r = s = 1$ 。
[ ] 默写分支限界"四问"模板。
[ ] 说出中转贸易的下界怎么定（已花税费 + Dijkstra 求的最小剩余税费）及为何正确有效。
[ ] 区分队列式（BFS 波前）与优先队列式（类 Dijkstra）分支限界。
[ ] 答出子集树叶子 $2^{n}$ 、排列树叶子 $n!$ ，以及选择题 1～5 的答案。

06 回溯法与分支限界法 ​

核心考点 ​

从零开始的前置知识 ​

解空间树、子集树、排列树 ​

活结点、扩展结点、死结点 ​

回溯法的工作方式 ​

分支限界法的工作方式 ​

回溯法 vs 分支限界法（选择题对比） ​

答题模板 ​

模板 D：回溯法解 SAT（画搜索树） ​

模板 E：分支限界法四问 ​

逐题精解 ​

B1 三子句 SAT（样题2/试卷2） ​

B2 四子句 SAT（2011期末 等，高频，画树） ​

BB1 中转贸易（2011影印/2020/merged，高频） ​

BB2 通信网络（2012影印/2013） ​

BB3 优先队列式分支限界——单源最短路径（试卷5） ​

BB4 队列式分支限界——电路板布线（试卷5） ​

作业 O4：整数规划（电脑组装，试卷6，20 分） ​

高频陷阱 / 易错点小结 ​

自测清单 ​