Backtracking 回溯法

核心结论

回溯法是在问题的解空间树上做 深度优先搜索，并用剪枝函数提前丢弃不可能得到可行解或最优解的子树。

它的本质不是“递归”，而是：

$$\text{解空间树} + \text{DFS} + \text{剪枝函数}$$

1. 基本定位

回溯法适合处理组合搜索问题。复杂问题往往有大量候选解，这些候选解构成解空间。回溯法按照深度优先顺序系统考察解空间中的候选解，但不会无条件展开所有分支；每到一个结点，就判断该结点对应的部分解是否还有继续扩展的价值。

若当前部分解已经不可能导向合法解或更优解，就剪掉以该结点为根的整棵子树。

和暴力枚举的区别

暴力枚举是完整遍历候选空间；回溯法仍属于穷举搜索，但利用约束与界限提前停止无效搜索，因此实际访问的搜索空间可能远小于完整解空间树。

2. 5.1 回溯法的算法框架

2.1 问题的解空间

设问题有 $n$ 个决策分量，通常把一个候选解表示为等长向量：

$$X=(x_0,x_1,\dots,x_{n-1})$$

其中第 $i$ 个分量来自有限集合：

$$x_i\in S_i$$

所有候选向量构成笛卡尔积：

$$S_0\times S_1\times\cdots\times S_{n-1}$$

这个集合就是问题的解空间。

解空间要先定义正确

解空间过小会漏掉正确答案；解空间过大则会引入重复解或无效候选解。回溯法开始前，首先要明确“一个候选解到底如何表示”。

2.2 解空间树

解空间通常组织成解空间树（Solution Space Tree / State Space Tree）：

运行时通常不需要真的构造整棵树，只需要维护从根结点到当前结点的一条路径。

2.3 回溯法的基本思想

搜索到任意结点时，做三类判断：

1. 当前部分解是否已经构成完整解；
2. 当前部分解是否仍满足显式约束；
3. 当前部分解是否仍可能导向比当前答案更好的解。

若第 2 或第 3 点失败，则剪枝。

剪枝函数

回溯法通常使用两类剪枝：

• 约束函数 constraint：剪去不可能得到可行解的子树；
• 上界函数 / 限界函数 bound：剪去不可能得到更优解的子树。

对于最大化问题，若某分支的理论上界不超过当前最优值，则该分支可以剪掉。对于最小化问题，若某分支的理论下界不小于当前最优值，则该分支可以剪掉。

2.4 回溯过程的三种状态

设当前已经构造出部分解：

$$(x_0,x_1,\dots,x_i)$$

继续扩展下一个分量后，通常有三种情况：

2.5 递归回溯模板

下标说明

PPT 使用 1-based 下标；本笔记统一改写为 0-based 下标。

BACKTRACK(t)
    if t == n
        OUTPUT_OR_UPDATE_ANSWER(x)
        return

    for value in CANDIDATES(t)
        x[t] <- value
        if CONSTRAINT(t) and BOUND(t)
            BACKTRACK(t + 1)
        RESTORE_STATE_IF_NEEDED

变量含义：

2.6 迭代回溯模板

递归形式依赖系统递归栈。若显式维护层数、当前候选位置和路径数组，也可以写成非递归形式。

ITERATIVE-BACKTRACK()
    t <- 0
    initialize x and candidate state

    while t >= 0
        value <- NEXT-CANDIDATE(t)

        if value does not exist
            RESET_LEVEL(t)
            t <- t - 1
        else
            x[t] <- value
            if CONSTRAINT(t) and BOUND(t)
                if t == n - 1
                    OUTPUT_OR_UPDATE_ANSWER(x)
                else
                    t <- t + 1
                    INITIALIZE_LEVEL(t)

迭代回溯的核心是用显式变量模拟树的深度优先遍历。它不是新的算法范式，只是回溯法的另一种实现方式。

2.7 子集树算法框架

当每个元素只有“选 / 不选”两种状态时，解空间是子集树。

SUBSET-BACKTRACK(t)
    if t == n
        OUTPUT_OR_UPDATE_ANSWER(x)
        return

    for value in {0, 1}
        x[t] <- value
        if CONSTRAINT(t) and BOUND(t)
            SUBSET-BACKTRACK(t + 1)

完整遍历子集树的规模为：

$$O(2^n)$$

典型问题：

• Loading Problem 装载问题
• 0-1 Knapsack Problem 0-1背包 Backtracking
• Maximum Clique Problem 最大团问题
• 子集和问题

2.8 排列树算法框架

当解是 $n$ 个元素的一种排列时，解空间是排列树。

PERMUTATION-BACKTRACK(t)
    if t == n
        OUTPUT_OR_UPDATE_ANSWER(x)
        return

    for i <- t to n - 1
        swap(x[t], x[i])
        if CONSTRAINT(t) and BOUND(t)
            PERMUTATION-BACKTRACK(t + 1)
        swap(x[t], x[i])

完整遍历排列树的规模为：

$$O(n!)$$

典型问题：

• 批处理作业调度
• TSP
• 任务分配问题

3. 需要问题具有的性质

回溯法不是只能用于某一类具体题目，而是一种通用搜索策略。一个问题适合用回溯法，通常需要具备以下性质。

3.1 候选解可以分步构造

候选解应能写成一个分量序列：

$$X=(x_0,x_1,\dots,x_{n-1})$$

或者可以表示为从根结点到当前结点的一条路径。每次搜索只新增一个决策分量。

例如：

3.2 每一步候选集合有限

每个分量 $x_i$ 的候选值集合 $S_i$ 必须是有限的，否则无法形成有限分支的解空间树。

常见形式：

3.3 部分解可以判断可行性

回溯法依赖“提前判断”。如果只有完整解才能判断是否合法，而中间状态完全无法剪枝，则回溯会退化为纯暴力枚举。

需要能设计约束函数：

$$\operatorname{constraint}(x_0,\dots,x_t)$$

它判断当前部分解是否仍可能扩展为可行解。

3.4 优化问题最好能设计界函数

若问题要求最优解，还应尽量设计上界或下界函数。

最大化问题常用上界：

$$\operatorname{bound}(x_0,\dots,x_t)\le best \Rightarrow \text{剪枝}$$

最小化问题常用下界：

$$\operatorname{bound}(x_0,\dots,x_t)\ge best \Rightarrow \text{剪枝}$$

没有界函数时也能回溯，但剪枝能力通常明显下降。

3.5 状态能够恢复

深度优先搜索会不断进入子树、返回父结点、再进入兄弟子树。因此每次递归后必须能恢复现场。

常见需要恢复的状态：

• 当前重量 cw；
• 当前价值 cp；
• 当前路径 x[t]；
• 已使用元素集合；
• 当前约束统计量。

常见错误

修改全局状态后递归进入下一层，但返回时忘记撤销，会污染兄弟分支，导致答案错误。

4. 典型例子

本文件只做总纲

5.2、5.5、5.6 在本文件中只作为典型例子简介，不展开具体伪代码、剪枝推导与复杂度细节。后续分别整理到独立笔记。

4.1 5.2 装载问题

主文件：Loading Problem 装载问题

装载问题是典型的子集树回溯。

它说明：如果问题可以转化为“从若干元素中选择一个子集”，通常可以先考虑子集树回溯。

4.2 5.5 n 后问题

主文件：N-Queens Problem n后问题

n 后问题是典型的约束满足型回溯。

它说明：对可行性问题，核心往往不是 bound，而是高效的 constraint。

4.3 5.6 0-1 背包问题

主文件：0-1 Knapsack Problem 0-1背包 Backtracking

0-1 背包是典型的优化型子集树回溯。

它说明：优化型回溯通常不仅要判断“还能不能可行”，还要判断“有没有可能超过当前最优”。

4.4 其他例题一笔带过

5. 5.13 回溯法效率分析

5.1 影响效率的因素

PPT 总结：回溯算法的效率很大程度上依赖以下因素。

核心折衷

更强的剪枝函数通常能减少结点数，但它本身的计算量可能更大。因此设计回溯算法时，不能只追求剪枝强，还要看剪枝函数的计算代价。

总运行时间可以粗略理解为：

$$T \approx \sum_{v\in \text{visited nodes}} \operatorname{cost}(v)$$

其中每个结点的代价包括候选生成、约束判断、界函数计算和状态维护。

5.2 重排原理

很多回溯问题中，变量或候选值的搜索顺序并不唯一。PPT 给出的原则可以概括为：

在其他条件相当时，让可取值最少、最容易触发剪枝的分量优先搜索。

原因：越靠近根部的剪枝，删除的子树越大。

假设在第 1 层剪掉一个分支，可能一次删除大量完整候选解；如果同样的剪枝发生在较深层，能删除的候选解就少得多。因此，好的搜索顺序可以显著影响实际效率。

这可以理解为约束满足问题中的启发式思想：

• 优先处理候选值少的变量；
• 优先处理约束强的变量；
• 优先尝试更可能导致好解的候选值，以便尽早更新 best，增强后续剪枝。

5.3 用随机路径估算搜索结点数

PPT 给出一种估算回溯实际搜索规模的方法。

前提假设：约束函数是静态的，即约束函数不随搜索过程中获得的信息动态改变。

基本过程：

1. 在解空间树上随机生成一条路径；
2. 设路径上的某个结点位于第 $i$ 层；
3. 统计该结点所有孩子中满足约束条件的孩子数 $m_i$；
4. 从这 $m_i$ 个可行孩子中随机选一个作为路径下一结点；
5. 重复直到到达叶子结点，或所有孩子都不满足约束条件。

若随机路径上各层满足约束的孩子数为：

$$m_0,m_1,\dots,m_{n-1}$$

则可估算搜索结点数为：

$$m_0 + m_0m_1 + m_0m_1m_2 + \cdots + m_0m_1m_2\cdots m_{n-1}$$

为了更稳定，可以选取若干条随机路径，分别估算结点数，再取平均值。PPT 中建议通常不超过 20 条随机路径。

4 后问题估算

PPT 中对 4 后问题取 4 条随机路径，估算搜索空间结点数平均为 14；完整解空间树结点数为 65，因此实际搜索比例约为：

$$\frac{14}{65}\approx 21.5\%$$

这说明回溯法产生的搜索空间可以明显小于完整解空间树。

5.4 效率分析的正确姿势

分析回溯法时，应分清两类复杂度：

通常理论上只能给出最坏情况指数级上界，例如：

$$O(2^n),\quad O(n!),\quad O(m^n)$$

但实际运行效率取决于剪枝函数和搜索顺序。考试或写算法分析时，应至少说明：

1. 解空间树类型；
2. 完整解空间规模；
3. 每个结点的剪枝判断代价；
4. 最坏情况下剪枝是否可能完全失效；
5. 若有启发式排序，它如何影响实际搜索但不改变最坏上界。

6. 回溯法设计清单

设计算法时按以下顺序检查：

1. 定义解向量：$X=(x_0,x_1,\dots,x_{n-1})$ 表示什么？
2. 确定候选集合：每个 $x_i$ 的取值范围是什么？
3. 确定解空间树类型：子集树、排列树、$m$ 叉树，还是其他状态树？
4. 设计约束函数：什么情况下当前部分解已经不可能可行？
5. 设计界函数：若是优化问题，什么情况下当前部分解已经不可能优于当前最优？
6. 确定搜索顺序：能否让更容易剪枝的变量或候选值更早出现？
7. 维护当前状态：递归进入和退出时，哪些变量需要更新和恢复？
8. 记录答案：题目只要求最优值，还是还要求完整方案？
9. 分析复杂度：完整解空间规模是多少？每个结点的判断代价是多少？

7. 常见错误

错误 1：只写 DFS，不写剪枝函数

没有 constraint 和 bound，通常只是暴力枚举，不是一个完整的回溯法设计。

错误 2：最大化 / 最小化剪枝方向写反

最大化问题中，若上界 <= best，剪枝；最小化问题中，若下界 >= best，剪枝。

错误 3：忘记恢复现场

递归返回前必须撤销对当前状态的修改，否则兄弟分支会受到污染。

错误 4：只保存最优值，不保存最优解

如果题目要求输出方案，需要维护 bestx，或保存父指针 / 路径信息。

错误 5：把解空间树真的建出来

回溯法一般不需要显式构造整棵树，只需要维护当前路径和必要状态。

8. 与相关方法的区别

最短记忆

回溯法：沿一条路径向下试，失败就退。

分支限界法：维护一批活结点，优先扩展最有希望的结点。

9. 一句话总结

回溯法的关键不是递归语法，而是把问题写成解空间树，并在深度优先搜索中不断回答两个问题：

1. 当前部分解还能不能变成可行解？
2. 当前部分解还有没有可能变得比当前答案更好？

只要这两个问题能被有效回答，回溯法就能把盲目穷举变成有方向的系统搜索。

10. 相关笔记

• Algorithm Design and Analysis 算法设计与分析
• Depth-First Search 深度优先搜索
• Loading Problem 装载问题
• N-Queens Problem n后问题
• 0-1 Knapsack Problem 0-1背包 Backtracking
• Maximum Clique Problem 最大团问题
• Traveling Salesman Problem 旅行商问题
• Branch and Bound 分支限界法
• Dynamic Programming 动态规划
• Greedy Algorithm 贪心算法

11. 参考资料

• 课程资料：第5章 回溯法.pdf。