回溯剪枝 | Bowen's Academic Home

回溯法

回顾动态规划和贪心算法中的剪枝策略：

动态规划：考虑搜索空间中子问题的重叠性。
贪心算法：以贪心选择策略为依据，遍历搜索空间的部分分支。

回溯法是一种相较于动态规划、贪心算法更一般的通用的解法：

将问题建模为解空间树
深度优先搜索
搜索过程中剪枝
适合解组合数相当大的问题

解空间树

首先，我们先给出问题的解向量的定义：$n$ 元式 $(x_1, x_2, \cdots, x_n)$ 的形式。其中包含如下的一些概念：

显约束：对分量 $x_i$ 的取值限定
隐约束：为满足问题的解而对不同分量之间施加的约束
解空间：满足显式约束条件的所有 $n$ 元组

针对回溯问题，我们有解空间树的概念：

问题的解空间的表示方式
第 $0$ 层为初始状态
第 $k$ 层为第 $k$ 个分量做出选择后到达的状态
从树的根结点到叶子结点的路径

例如在 0-1 背包问题中，有如下解空间树：

树中第 $i$ 层与第 $i+1$ 层结点之间的边上给出了对物品 $i$ 的选择结果，$8$ 个叶子代表 $8$ 个可能解。

解空间树可以通过 DFS 和 BFS 的方法生成。

回溯法的基本思想

问题的求解方式：

定义整个解空间完成（应注意解空间应当包括所有可能解）
确定易于搜索的解空间结构
深度优先方式遍历解空间并剪枝

回溯法是具有剪枝函数的深度优先生成法。

剪枝的基本思想

在搜索至树上任意一点时判断：

是否满足约束条件
是否包含问题的（最优）解
- 不包含：跳过对以该结点为根的子树的搜索——剪枝 pruning
- 包含：进入以该结点为根的子树，继续按深度优先搜索

两种用于剪枝的函数：

约束函数：用约束条件剪去得不到可行解的子树。例如在 0-1 背包问题中，约束条件“商品体积不能超过背包容量”就可以用约束函数来刻画。
限界函数：用目标函数减去得不到最优解的子树。例如在 0-1 背包问题中，目标“购买商品的价格尽可能高”就可以用限界函数来刻画。

利用剪枝函数可避免无效搜索，使算法无需搜索整个搜索树。

算法框架

递归回溯

int[] backtrack(int t) {
    if (t > n) {
        // 到达叶子结点，返回结果
        return x;
    }
    else {
        for (int i = f(n, t); i <= g(n, t); ++i) {
            // f(n, t): 第 t 层未搜索过子树的起始编号
            // g(n, t): 第 t 层未搜索过子树的终止编号
            x[t] = h(i);
            if (constraint(x, t) && bound(x, t)) {
                // constraint: 约束函数，bound: 限界函数
                backtrack(t + 1);
            }
        }
    }
}

迭代回溯

void iterativeBacktrack() {
    int t = 1;
    while (t > 0) {
        if (f(n, t) <= g(n, t)) {
            for (int i = f(n, t); i <= g(n, t); ++i) {
                x[t] = h(i);
                if (constraint(x, t) && bound(x, t)) {
                    if (solution(t)) {
                        return x;
                    }
                    else {
                        ++i;
                        break;
                    }
                }
            }
        }
        else {
            --t;
        }
    }
}

算法分析

空间复杂度

回溯法的存储特点：

动态产生问题的解空间
只保存从根结点到当前扩展结点的路径

空间复杂度：

根到叶子的最长路径的长度为 $h(n)$
空间复杂度通常为 $O(h(n))$
显式地存储整个解空间则需要 $O(2h(n))$ 或 $O(h(n)!)$

时间复杂度

在讨论回溯法的时间复杂度之前，我们首先要给出两个概念：

子集树：从 $n$ 个元素中找出满足某种性质的子集，相应的解空间为子集树。例如 0-1 背包问题的解空间树就是子集树。
排列树：当所给问题是确定的 $n$ 个元素满足某种性质的排列时，相应的解空间为排序树。例如 TSP 问题的解空间树就是排列树。

回溯法的最坏时间复杂度取决于解空间树的类型：

子集树：$O(2^n)$
排列树：$O(n!)$

如果采用蛮力穷举法进行回溯，回溯法的时间复杂度必然是最坏情况。因此，需要设计较好的剪枝函数以降低时间复杂度。

回溯法同其他算法比较

动态规划：避免计算重叠子问题
贪心算法：只考虑局部最优解
回溯法：利用剪枝函数

回溯剪枝的应用

TSP：旅行商问题

一个旅行商需要在 $n$ 个城市销售商品，已知任两个城市之间的距离，求一条每个城市恰好经过一次的回路，使得总长度最小。

问题建模

输入：

城市集 $C = \{ c_1, c_2, \cdots, c_n \}$
距离 $d(c_i, c_j) = d(c_j, c_i)$

输出：

城市 $c_1, c_2, \cdots c_n$ 的排列 $c_{k_1}, c_{k_2}, c_{k_n}$

约束条件：

$$ \begin{align*} \min \left \{ \sum_{i=1}^{n-1} {d(c_{k_i}, c_{k_{i+1}}) + d(c_{k_n}, c_{k_1})} \right \} \end{align*} $$

问题分析

旅行商问题是典型的以排序树为解空间树结构的回溯法问题。

$n$ 皇后问题

在一个 $n \times n$ 的方格内放置 $n$ 个皇后，使得没有两个皇后互相“攻击”（在同一行、同一列、也不在同一条斜线上）。问有多少种可能的布局？

计算机体系结构的很多问题和 $n$ 皇后问题很相似。例如并行内存系统的存储模式，超大规模集成电路设计，检测程序中的死锁问题。

问题分析

$n$ 皇后问题的解空间树是 $n$ 叉树，按深度优先次序遍历 $n$ 叉树即可找到所有解。

算法代码

LeetCode Link

class Solution
{
public:
    vector<bool> columns;          // 当前纵向是否不被攻击
    map<int, bool> mains, seconds; // 当前斜线方向是否不被攻击

    vector<vector<string>> solveNQueens(int n)
    {
        columns = vector<bool>(n, true);
        for (int i = 0; i < n; ++i) {
            mains[i] = mains[-i] = true;        // 计算方法：行号-列号
            seconds[i] = seconds[i + n] = true; // 计算方法：行号+列号
        }
        vector<vector<string>> ans;
        vector<string> temp;
        backtrack(0, n, ans, temp);
        return ans;
    }

    void backtrack(int row, const int n, vector<vector<string>> &ans, vector<string> &temp)
    {
        if (row == n) {
            // 搜到底，要回溯
            ans.push_back(temp);
            return;
        }
        for (int j = 0; j < n; ++j) {
            // 根据行、列、主对角线、次对角线的下标特点，构造了标志位的索引器方便判断
            if (columns[j] && mains[row - j] && seconds[row + j]) {
                // 表示当前行皇后摆放位置
                string line(n, '.');
                line[j] = 'Q';
                // 递归深入之前修改相应标志位，使得棋盘某些位置不能放（被攻击）
                columns[j] = mains[row - j] = seconds[row + j] = false;
                // 当前行的摆放结果压栈
                temp.push_back(line);
                // 开始递归下一层
                backtrack(row + 1, n, ans, temp);
                // 回溯，当前行之前的结果退栈（前面几行结果仍保留）
                temp.pop_back();
                // 相应标志位复位，表示这些位置又可以继续摆放皇后
                columns[j] = mains[row - j] = seconds[row + j] = true;
            } // if语句结束后，当前行可能有多解，这就是回溯再递归
        }
    }
};

剪枝函数的设计

可行性约束函数

图着色问题

给定无向连通图 $G = (V, E)$，是否可以使用 $k$ 种颜色对 $G$ 中顶点着色，使得任意两个相邻顶点之间的着色都不同。

是与否的判定问题
解向量 $(x_1, x_2, \cdots, x_n)$（$x_i$ 表示顶点 $i$ 所着颜色）

图着色问题中的描述“任意两个相邻顶点之间的着色都不同”即可视为一种可行性约束函数。$k$ 着色问题对应的解空间为 $k$ 叉树。

限界函数

组合优化问题

目标函数（极大化或极小化）
约束条件
可行解：搜索空间满足约束条件的解
最优解：使目标函数达到极大

例如我们熟知的 0-1 背包问题就是一个组合优化问题。

代价函数

在搜索树的每个结点都有定义代价函数。对于极大化问题，代价函数的值为以该点为根的子树所有可行解的值的上界，并且父结点的代价不小于子结点的代价。（极小化问题则相反）

这里还有一个界的概念，即当前得到可行解的目标函数的最大值。界的初值为 $0$，每当得到更好的可行解时，界值更新。

分支限界法

非对称旅行商问题

现实场景：在城市双向道路两侧车道拥堵状况不一的情况下，如何选择道路行驶能最快到达目的地？

非对称旅行商问题和旅行商问题的区别：距离不对称，即

$$ \begin{align*} d(c_i, c_j) \ne d(c_j, c_i)$ \end{align*} $$

使用普通的回溯法当然没有问题，那么在使用回溯法的时候是否可以知道应该优先遍历哪些子树？

为了尽快能够访问到最优解，我们可以尝试：

不用深度优先搜索
优先访问更靠近最优解的节点
设置代价函数计算优先级
利用优先级队列管理节点

什么是优先级函数呢？可以令优先级函数等于代价函数。

分支限界法的基本思想

分支限界法是一种与回溯法类似的算法：

将问题建模为解空间树
通常用代价函数估算每个分支的最优值
优先选择当前看来最好的分支
通常用广度优先搜索
搜索过程中剪枝

算法代码

void branchBound(int x) {
    queue<int> Q;
    Q.push(x);
    int bestX = 0;

    while (!Q.empty()) {
        s = Q.front();
        Q.pop();
        if (constraint(s) && bound(s, bestX)) {
            vector<int> S = partition(s);
            for (int s : S) {
                if (isLeaf(s)) {
                    update(bestX);
                }
                else {
                    Q.push(s);
                }
            }
        }
    }
}

分支限界法与回溯法的对比

	回溯法	分支限界法
搜索方式	DFS	BFS、优先级队列
搜索目标	所有解、可行解、最优解	最优解
函数	约束函数、限界函数	约束函数、限界函数、优先级函数
空间	树的高度	队列的长度

$A^*$ 算法

Best-first 策略：

$$ \begin{align*} f(n) = g(n) + h(n) \end{align*} $$

其中，$g(n)$ 是从根到 $n$ 的路径代价，$h(n)$ 是从 $n$ 到某个目标节点的优化路径代价。