回溯剪枝

回溯法

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

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

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

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

解空间树

首先,我们先给出问题的解向量的定义:$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$ 叉树即可找到所有解。

算法代码

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$ 到某个目标节点的优化路径代价。

Previous