← Back

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）：

树中位置	含义
根结点	初始状态，尚未做任何选择
第 $i+1$ 层	已经确定前 $i$ 个分量
一条根到叶子的路径	一个完整候选解
一个中间结点	一个部分解

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

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

变量含义：

符号	含义
t	当前正在决定第 t 个分量
x[0..t]	当前路径，即当前部分解
CANDIDATES(t)	第 t 个分量的候选取值
CONSTRAINT(t)	当前部分解是否仍可行
BOUND(t)	当前部分解是否仍可能导向更优解

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})$$

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

例如：

问题	解向量含义
装载问题	$x_i=1$ 表示第 $i$ 个集装箱装入第一艘船
n 后问题	$x_i$ 表示第 $i$ 行皇后所在列
0-1 背包	$x_i=1$ 表示选择第 $i$ 个物品

3.2 每一步候选集合有限

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

常见形式：

类型	候选集合
二选一决策	$\{0,1\}$
n 后问题	$\{0,1,\dots,n-1\}$
图的 $m$ 着色	$\{1,2,\dots,m\}$
排列问题	尚未使用的元素集合

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 装载问题

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

维度	内容
解向量	$x_i\in\{0,1\}$，表示第 $i$ 个集装箱是否装入第一艘船
解空间	子集树
约束函数	当前装载重量不能超过第一艘船容量
上界函数	当前载重量加剩余集装箱总重量若仍不优于 bestw，则剪枝
典型意义	展示“选择 / 不选择”型问题如何用子集树表示

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

4.2 5.5 n 后问题

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

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

维度	内容
解向量	$x_i$ 表示第 $i$ 行皇后所在列
解空间	每行选择一列，可看作 $n$ 叉搜索树；若利用列不重复约束，也可视作排列型搜索
约束函数	不同列、不同对角线
上界函数	通常不需要目标函数上界，因为问题主要是求可行解或解的个数
典型意义	展示强约束如何在较高层剪掉大量无效分支

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

4.3 5.6 0-1 背包问题

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

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

维度	内容
解向量	$x_i\in\{0,1\}$，表示第 $i$ 个物品是否放入背包
解空间	子集树
约束函数	当前重量不超过背包容量
上界函数	常用分数背包松弛估计当前子树可能达到的最大价值
典型意义	展示优化问题中 constraint + bound 的组合剪枝

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

4.4 其他例题一笔带过

小节	问题	解空间类型	关键词
5.3	批处理作业调度	排列树	作业顺序、最小完成时间和
5.4	符号三角形问题	二叉树	符号数量约束
5.7	最大团问题	子集树	顶点选择、团约束、剩余顶点上界
5.8	图的 $m$ 着色问题	完全 $m$ 叉树	相邻顶点不能同色

5. 5.13 回溯法效率分析

5.1 影响效率的因素

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

因素	含义	对效率的影响
产生 $x[k]$ 的时间	生成当前层候选值的代价	候选生成越慢，单结点代价越高
满足显约束的 $x[k]$ 值的个数	当前层可继续尝试的候选数量	候选越少，分支因子越小
计算 constraint 的时间	判断部分解可行性的代价	判断越贵，剪枝收益可能被抵消
计算 bound 的时间	判断是否可能优于当前最优的代价	上界越精确通常越贵
同时满足 constraint 和 bound 的结点数	实际进入下一层的结点数量	这是决定搜索规模的核心因素

核心折衷

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

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

$$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。