回溯法（Backtracking）

1. 核心思想

回溯法是一种系统地搜索问题解空间的方法，本质是带剪枝的深度优先搜索。它从根结点出发，按深度优先策略搜索解空间树；搜索到某个结点时，先判断该结点是否可能包含问题的解：

  • 可能包含 → 进入该子树继续搜索；
  • 一定不包含 → 跳过该子树（剪枝），回退到最近的活结点继续搜索。

若用回溯法求问题的所有解，要回溯到根，且根结点的所有可行子树都要被搜索到；若只求任一解，只要搜索到问题的一个解就可以结束。

2. 三个关键概念

概念含义
解空间树问题的所有可能解构成的树形结构，常见子集树与排列树
约束函数（constraint）剪掉不满足约束条件（不可行）的子树
限界函数（bound）剪掉虽可行但不可能优于当前最优解的子树

两类典型解空间树：

  • 子集树：每个元素只有「选 / 不选」两种状态，共 $2^n$ 个叶子结点。典型问题：0-1 背包、装载问题、图着色。
  • 排列树：确定 $n$ 个元素的排列顺序，共 $n!$ 个叶子结点。典型问题：旅行商问题（TSP）、批处理作业调度、n 皇后。

3. 算法框架

递归回溯（子集树）

void backtrack(int t) {
    if (t > n) {          // 到达叶子结点，得到一个可行解
        output(x);
    } else {
        for (int i = 0; i <= 1; i++) {   // 每个结点的分支数
            x[t] = i;
            if (constraint(t) && bound(t)) {  // 剪枝
                backtrack(t + 1);
            }
        }
    }
}

迭代回溯（非递归）

void iterativeBacktrack() {
    int t = 1;
    while (t > 0) {
        if (t > n) {
            output(x);
            t--;                       // 回溯
        } else {
            x[t]++;                    // 进入下一个分支
            if (x[t] <= m && constraint(t) && bound(t)) {
                t++;                   // 深入下一层
            } else {
                t--;                   // 本层分支枚举完，回溯
            }
        }
    }
}

4. 复杂度

回溯法的时间复杂度取决于解空间树的大小与剪枝效果：

  • 子集树：最坏 $O(2^n)$，每结点耗时 $O(1)$，故为 $O(n \cdot 2^n)$；
  • 排列树：最坏 $O(n!)$，每结点耗时 $O(1)$，故为 $O(n \cdot n!)$。

剪枝函数写得越好，实际搜索的结点数越少，但最坏情况下的界不变。

5. 典型问题

问题解空间树约束 / 限界函数
n 皇后排列树约束：不在同一列、同一对角线
0-1 背包子集树约束：不超重；限界：上界函数（当前价值 + 剩余物品价值上界）
图着色子集树约束：相邻顶点颜色不同
旅行商问题排列树约束：路径存在；限界：已走路径长度 < 当前最优
装载问题子集树约束：不超过载重量
符号三角形子集树约束：+ 与 - 的个数不超过总数一半

6. 回溯法 vs 分支限界法

对比项回溯法分支限界法
搜索方式深度优先广度优先 / 优先队列（最小耗费优先）
存储结构栈（或递归栈）队列 / 优先队列
目标找出所有（或任一）可行解尽快找出最优解
剪枝方式约束函数 + 限界函数限界函数（上界/下界比较）