模块 3 · 回溯法 与 分支限界法

自学导航 · 回溯与分支限界：真正理解剪枝

① 前置知识与记号

前置复习：递归调用栈、解空间树、组合与排列。约束剪枝拒绝不可行解；限界剪枝拒绝不可能改善当前最优值的分支。每次剪枝必须能解释其安全性。

② 完整例题

四皇后从第 0 行开始，每行放一个；记录已使用列、主对角线 r−c、副对角线 r+c。合法列序列 [1,3,0,2] 可作为手算答案。写清递归入口、冲突检测、撤销选择三步。

本栏是补充学习材料，考试范围以本学期教师正式通知为准。

0 · 回溯思想与三结点CH05 S4–11, 36–48

1 · 通用框架与两类解空间树 ★★（算法填空必考）CH05 S11–19; Review S110–111

void backtrack(int t) {          // t: 当前扩展结点深度
    if (t > n) output(x);        // 到叶结点，得到一个可行解
    else
        for (int i = f(n,t); i <= g(n,t); i++) {   // 候选取值
            x[t] = h(i);
            if (constraint(t) && bound(t))   // 剪枝：约束 && 限界
                backtrack(t + 1);
        }
}

void backtrack(int t) {
    if (t > n) output(x);
    else
        for (int i = t; i <= n; i++) {   // ①②
            swap(x[t], x[i]);            // ③
            if (constraint(t) && bound(t)) backtrack(t + 1);
            swap(x[t], x[i]);            // 恢复现场
        }
}

2 · TSP / 0-1背包 / 装载（回溯版）

2.1 旅行商问题 TSP（排列树）CH05 S55–65

周游回路 = 固定起点 1，对 \(x[2..n]\) 全排列，末尾加回 \(x[1]\)。剪枝：当前部分和 \(cc\) ≥ 已知最优 bestf 即剪；再加上“图中有边”的可行性检查。n=4 时解空间 4!=24 个叶。

2.2 0-1 背包（子集树 + 双剪枝）★CH05 S66–70; Review S116–118

2.3 装载问题（两艘船）CH05 S71–77

n 个集装箱装两艘载重 \(c_1,c_2\) 的船。有解时最优策略：① 第一艘尽量装满（等价于特殊的 0-1 背包：子集和最接近 \(c_1\)）→ 回溯子集树；② 剩余装第二艘。剪枝：约束 \(cw+w_i\le c_1\)；限界 \(cw+r>wm\) 才展开右子树（r=剩余箱总重）。例：n=4, c₁=12, w={8,6,2,3} → 第一船装 {8,2}？不，可装 {8,3}=11 或 {6,2,3}=11 或 {8,2}=10… 目标是尽量靠近 12 而非一定装满 12：{6,2,3}+8=19>12；{8,3}=11、{6,2,3}=11 → 装满 12 需 {8,2}=10 +3=13 超；实际第一船最优 wm=11（{8,3} 或 {6,2,3}）。能否将剩余箱全装到第二船，仍须检查第二船载重 c₂：总重量为 19，故此例要求 c₂≥8。

3 · n 皇后 / 最大团 / 批处理 / m 着色

3.1 n 皇后（排列树 + 隐约束）★CH05 S78–87

bool place(int k) { for (int i = 1; i < k; i++)
    if (x[i]==x[k] || abs(k-i)==abs(x[i]-x[k])) return false;
    return true; }

3.2 最大团 / 最大独立集CH05 S88–98

团 = 两两有边的完全子图（极大、最大）；独立集 = 两两无边。G 的最大团 = 补图 G′ 的最大独立集（等价，判断题）。回溯：子集树；约束=新顶点与团内每个顶点都有边；限界=cn+(n−i)≤bestn 剪右子树。O(n2ⁿ)。

3.3 批处理作业调度（排列树）CH05 S99–104

n 个作业各两道工序，先机器 1 后机器 2，求调度使完成时间和最小。例 n=3：6 种调度完成时间和 19,18,20,21,19,19 → 最优 (1,3,2)=18。排列树 + 剪枝：当前完成时间和 ≥ 最优值即剪。机器 2 有空闲与积压两种情况要分别累计。

3.4 图的 m 着色CH05 S105–126

给定无向图 G 与 m 色，相邻顶点异色。解空间：高 n 的完全 m 叉树。剪枝：与已着色邻居不同色（Bound 检查）。应用：考试排期（课程=顶点、学生重叠=边、颜色=时段）；地图着色经对偶图转化为顶点着色（四色定理：平面图 4 色足够，1976 年机器证明）。问“存在性”（能否 m 着色）与“最少色数”两种问法。

3.5 回溯效率分析CH05 S127–129

效率取决于：解空间结构（重排原理：取值少的分量优先）、产生 x[k] 的时间、满足剪枝的结点数、约束/限界函数本身的计算代价——剪枝函数不宜太贵。

def n_queens(n):
    """每种方案为逐行皇后列号，最坏指数搜索。"""
    if n < 0:
        raise ValueError('n 不得为负')
    ans, path = [], []
    cols, d1, d2 = set(), set(), set()

    def search(row):
        if row == n:
            ans.append(path[:])
            return
        for col in range(n):
            a, b = row - col, row + col
            if col in cols or a in d1 or b in d2:
                continue
            cols.add(col)
            d1.add(a)
            d2.add(b)
            path.append(col)
            search(row + 1)
            path.pop()
            d2.remove(b)
            d1.remove(a)
            cols.remove(col)

    search(0)
    return ans

4 · NP 完全性入门 ★CH05 S21–33; 什么是P/NP/NPC.ppt

（本节是模块 4 的预告与浓缩；完整展开——含归约链、证明模板、网络流、近似算法——见模块 4。）

经典 NPC 问题清单（判断题常客）：SAT / 3-SAT、0-1 背包（判定版）/ 子集和、TSP、Hamilton 回路、顶点覆盖、团、独立集、图的 m 着色（m≥3）。

5 · 分支限界：思想与回溯的三大区别 ★★CH06 S3–24; Review S80–82

6 · 队列式 / 优先队列式

7 · 六大经典问题（分支限界版）

另有：批处理作业调度（3 机器版：下界 sum3db=机器 1、2 无空闲且最后是机 3 时间最短作业时的理想值；例 4 作业下界 36）；电路板排列（排列树，最小化连接块密度，优先队列式）。

def knapsack_branch_and_bound(weights, values, capacity):
    """优先队列式分支限界求解 0-1 背包最优值（按单位价值线性松弛上界剪枝）。"""
    items = sorted(zip(weights, values), key=lambda x: x[1] / x[0], reverse=True)
    n = len(items)

    def bound(idx, cur_w, cur_v):
        rem = capacity - cur_w
        b = float(cur_v)
        while idx < n and items[idx][0] <= rem:
            rem -= items[idx][0]
            b += items[idx][1]
            idx += 1
        if idx < n and rem > 0:
            b += rem * (items[idx][1] / items[idx][0])
        return b

    best = 0
    pq = [(-bound(0, 0, 0), 0, 0, 0)]  # (-ub, idx, cur_w, cur_v)
    while pq:
        neg_ub, idx, cur_w, cur_v = heappop(pq)
        if -neg_ub <= best or idx == n:
            continue
        w, v = items[idx]
        if cur_w + w <= capacity:
            nv = cur_v + v
            if nv > best:
                best = nv
            ub_left = bound(idx + 1, cur_w + w, nv)
            if ub_left > best:
                heappush(pq, (-ub_left, idx + 1, cur_w + w, nv))
        ub_right = bound(idx + 1, cur_w, cur_v)
        if ub_right > best:
            heappush(pq, (-ub_right, idx + 1, cur_w, cur_v))
    return best

8 · 公式速查（一页纸素材）

9 · 自测（含算法填空真题）