算法设计与分析 第7讲 — 回溯法

算法设计与分析 第7讲 — 回溯法（Backtrack）

来源：北京大学 屈婉玲《算法设计与分析》课程 原始文件：/田浩然上传的资料/0A002算法分析与设计/lecture7.pdf 关联：算法设计与分析 第1讲 - 基础知识, 算法设计与分析 第2讲 - 数学基础, 算法设计与分析 第3讲 - 分治策略, 算法设计与分析 第4-5讲 - 动态规划, 算法设计与分析 第6讲 - 贪心法

---

一、回溯算法基本思想

1. 适用问题

求解搜索问题，搜索空间是一棵树。

• 每个结点对应部分解向量
• 树叶对应可行解
• 搜索过程：系统地隐含遍历搜索树

2. 搜索策略

深度优先、宽度优先、函数优先、宽深结合等。

3. 结点分支判定

• 满足约束条件 → 分支扩张解向量
• 不满足约束条件 → 回溯到父结点

4. 结点状态（白/灰/黑）

• 白结点：尚未访问
• 灰结点：正在访问该结点为根的子树
• 黑结点：该结点为根的子树遍历完成

存储内容：当前路径。

5. 必要条件——多米诺性质

设 P(x₁, x₂, …, x_k) 为部分向量满足约束的判定条件，则：

P(x₁, x₂, …, x_{k+1}) → P(x₁, x₂, …, x_k)   （0 < k < n）

即：更长的向量满足约束 → 更短的前缀也一定满足约束。

反例：不等式 5x₁ + 4x₂ − x₃ ≤ 10，1 ≤ x_i ≤ 3

• 不满足多米诺性质（x₃ 系数为负，增大 x₃ 反而让左边减小）
• 变换方法：令 x₃ = 3 − x₃’，则 5x₁ + 4x₂ + x₃’ ≤ 13，满足多米诺性质

---

二、回溯算法设计步骤

1. 设计要素

1. 定义解向量 <x₁, x₂, …, x_n> 和每个分量的取值集合 X_i
2. 确定结点儿子的排列规则
3. 判断是否满足多米诺性质
4. 搜索策略：深度优先
5. 确定每个结点能够分支的约束条件
6. 确定存储搜索路径的数据结构

2. 递归回溯算法

算法 ReBack(k)
1. if k > n then <x₁, x₂, …, x_n> 是解
2. else while S_k ≠ ∅ do
3.     x_k ← S_k 中最小值
4.     S_k ← S_k − {x_k}
5.     计算 S_{k+1}
6.     ReBack(k+1)

算法 ReBacktrack(n)
1. for k ← 1 to n 计算 X_k
2. ReBack(1)

3. 迭代回溯算法

算法 Backtrack
1. 对于 i = 1, 2, …, n 确定 X_i
2. k ← 1
3. 计算 S_k
4. while S_k ≠ ∅ do
5.     x_k ← S_k 中最小值; S_k ← S_k − {x_k}
6.     if k < n then
7.         k ← k+1; 计算 S_k
8.     else <x₁, x₂, …, x_n> 是解
9. if k > 1 then k ← k−1; goto 4

---

三、典型搜索空间类型

问题类型	解向量	搜索空间	叶子数
四后问题	列号向量	4叉树	4^n
0-1背包问题	0/1子集向量	子集树	2^n
巡回售货员问题	排列向量	排列树	n!
图的m着色	颜色向量	m叉完全树	m^n

---

四、应用实例

实例1：装载问题（两艘船）

问题：n 个集装箱装上 2 艘载重分别为 c₁ 和 c₂ 的轮船，w_i 为集装箱 i 的重量，且总重量 ≤ c₁ + c₂。是否存在合理装载方案？

求解思路：

1. 确定使第一船装载量 W₁ 与 c₁ 差最小的装载方案（等价于 0-1 背包，v_i = w_i）
2. 若总重 − W₁ ≤ c₂，则回答 yes，否则 no

算法设计：

• 将 w₁ … w_n 递降排序
• 解向量 <x₁, …, x_n>，x_i ∈ {0, 1}
• 满足多米诺条件（前缀和超过 c₁ 则更长的也一定超过）
• 约束条件：∑w_i x_i ≤ c₁（前 k 个）
• 时间复杂度：W(n) = O(2

实例2：0-1背包问题（分支估界）

问题：max ∑v_i x_i, s.t. ∑w_i x_i ≤ B, x_i ∈ {0,1}

代价函数（上界）： 对 <x₁, …, x_k>，用单位价值最高的方式填满剩余容量：

代价 = ∑(前k个v_i x_i) + (B − ∑w_i x_i) × (v_{k+1} / w_{k+1})

其中物品按单位重量价值递降排序。

分支策略：深度优先。

实例3：最大团问题

问题：给定无向图 G = <V, E>，求 G 中的最大团。

相关概念：

• 团：完全子图（任意两顶点间有边）
• 最大团：顶点数最多的团
• 点独立集：顶点子集，任意两顶点间无边
• 命题：U 是 G 的最大团 ⇔ U 是 G 补图的最大点独立集

算法设计：

• 结点 <x₁, …, x_k>：已检索 k 个顶点，x_i = 1 表示顶点 i 在团内
• 搜索空间：子集树
• 约束条件：该顶点与当前团内每个顶点都有边相连
• 界：当前已找到的极大团顶点数
• 代价函数：F = C_n + n − k（当前团顶点数 + 剩余顶点数）
• 时间：O(n · 2

实例4：图的 m 着色

问题：给定无向连通图 G 和 m 种颜色，给顶点着色，相邻顶点不同色，求所有方案。

• 搜索空间：m 叉完全树
• 约束条件：该顶点邻接表中已着色顶点没有同色
• 代价函数：无（不是优化问题）
• 时间：O(n · m

对称性优化：根据颜色对称性，只需搜索 1/m 的解空间。

实例5：巡回售货员问题

问题：n 个城市，求最短哈密顿回路。

• 解向量：从城市1出发，<i₁, i₂, …, i_{n-1}> 为 {2…n} 的排列
• 搜索空间：排列树
• 约束条件：i_{k+1} ∉ 已选集合 B
• 界：当前最短巡回路线长度
• 代价函数（下界）：

  L = ∑(已选d_j) + ∑(剩余顶点的最短出边 l_i)
  

  即已走路程 + 每个未走城市的最短出边之和
• 时间：O(n!)，代价函数计算 O(n)

实例6：圆排列问题

问题：给定 n 个圆的半径序列，放到矩形框中各圆与底边相切，求最小排列长度。

• 解空间：排列树
• 圆心距公式：d_k = 2·√(r_{k-1} · r_k)
• 排列长度：l_k = x_k + r_k + r₁（x₁ = 0）
• 代价函数下界：L_k ≥ x_k + (2n − 2k + 1)·r_min + r₁
• 时间：O(n · n!) = O((n+1)!)

实例7：电路板排列问题

问题：n 块电路板，m 个连接块（每块包含若干电路板，用一根导线连接），求排列使相邻插槽间跨越的最大连线数最小。

• 解空间：排列树
• 代价函数：d_{i+1} = max(d_i, |S_{i+1}|)
  • S_{i+1}：跨越电路板 i 和 i+1 的连线集合
  • 条件：连接块 j 部分已排、部分未排 → 连线跨越
• 时间：O(m · n!)

实例8：连续邮资问题

问题：n 种面值邮票，每个信封至多贴 m 张，设计面值使从 1 开始的连续邮资区间最大。

• 解空间：既非排列树也非子集树（x₁=1，且 x₁ < x₂ < … < x_n）
• 关键约束：若当前最大连续区间为 1..r_i，则 x_{i+1} ∈ {x_i+1, …, r_i+1}
  • 若 x_{i+1} > r_i + 1，则 r_i + 1 无法表示，破坏连续性
• 动态规划计算 y_i(j)：用不超过 m 张前 i 种邮票贴 j 邮资的最少邮票数
  • y_i(j) = min_{1≤t≤m} { t + y_{i-1}(j − t·x_i) }
  • r_i = min{ j | y_i(j) ≤ m, y_i(j+1) > m }

---

五、回溯算法效率分析

1. 最坏时间复杂度

W(n) = p(n) · f(n)

其中 p(n) 为每个结点时间，f(n) 为结点个数。

2. Monte Carlo 估计平均效率

算法思想：

1. 从根随机选择一条路径，直到不能分支为止
2. 假设搜索树其他 |S_i|−1 个分支与此随机路径相似，估算结点总数
3. 重复 t 次，取概率平均

Estimate 算法：

m ← 1; r2 ← 1; k ← 1
while k ≤ n do
    if S_k = ∅ then return m
    r1 ← |S_k| * r2       // 本层扩张后结点总数
    m ← m + r1             // 累计结点总数
    x_k ← 随机选择 S_k 的元素
    r2 ← r1
    k ← k + 1

示例（四后问题）：

• case <1,4,2>：1 + 4 + 4×2 + 4×2 = 21 个结点
• case <2,4,1,3>：4 + 4×3 + 1 = 17
• 解空间实际结点数为 17

3. 影响效率的因素

因素	说明
搜索树结构	分支均匀度、树的深度、对称程度（对称适合裁减）
解的分布	在不同子树中分布是否均匀、分布深度
约束条件判断	计算复杂度

4. 改进途径

1. 优先策略：结点少的分支优先、解多的分支优先
2. 对称性剪裁：利用搜索树对称性裁减子树
3. 分解为子问题：f(n) = c·2^n，分解为 k 个子问题，求解时间 k·c·2^{n/k} + T
4. 分支估界：对组合优化问题，用代价函数提前剪枝

---

六、分支估界（Branch and Bound）

1. 核心要素

要素	说明
代价函数	以该结点为根的子树中所有可行解目标函数的上界（极大化问题）。父结点代价 ≥ 子结点代价
界	已找到的最优可行解的目标函数值
剪枝依据	不满足约束条件 或 代价函数 ≤ 当前界
界的更新	找到更优可行解时更新界

2. 适用问题

组合优化问题：目标函数 + 约束条件 + 可行解 + 最优解。

---

七、三种算法设计技术比较

比较维度	动态规划	分支估界（回溯）	贪心法
使用条件	优化原则 + 多步判断	多米诺性质 + 多步判断	贪心选择 + 优化原则 + 多步判断
选择依据	子问题结果	约束条件和界	局部最优性质
计算过程	看子问题结果选择，自底向上	选择后生成子问题，自顶向下	选择后生成子问题，自顶向下
数据结构	二维表	树、队列	线性表
解	一个最优解	一个或多个最优解	一个最优或近似解
关键问题	递推方程、空间复杂性高	设定代价函数、时间复杂性高	贪心选择性质证明、近似解误差估计

---

八、回溯算法小结

• 适用范围：组合搜索问题（含组合优化问题）
• 求解条件：满足多米诺性质
• 解的表示：解向量，不断扩充的过程
• 回溯条件：
  • 搜索问题 → 约束条件
  • 优化问题 → 约束条件 + 代价函数
• 复杂性：最坏指数级，空间代价小
• 平均时间估计：Monte Carlo 方法
• 降复杂度途径：
  1. 利用对称性裁减子树
  2. 划分成子问题
  3. 分支策略（深度优先/宽度优先/宽深结合/优先函数）