回溯法的思想、设计与分析

摘要: 回溯法基本思想

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

回溯法思想

回溯法是一种在解空间中搜索可行解或最优解的方法。该方法通常将解空间看做树形结构，称为状态空间树。

• 搜索过程以 DFS 对状态空间树进行遍历，以避免遗漏可行解。
• 不满足约束条件的节点的子树可以被剪枝，此时搜索过程回溯至该节点的父节点，继续 DFS。

回溯法的处理过程是一个逐步建立并修正子集树或排列树的过程，适用于求解搜索问题、组合优化问题：

• 对于搜索问题，就是在搜索空间中找到一个或全部可行解。例如n皇后问题、图的m着色问题、装载问题等
• 对于组合优化问题，就是找到问题的一个或全部最优解。例如背包问题、旅行商问题等。

在文章 组合搜索、隐式图搜索 中整理了一些常见场景和题目。

回溯法基本概念

解空间

使用回溯法解决问题，首先需要明确问题的解空间，构成解空间的解向量可以表示为 n-元组 $(x_{0}, x_{1}, \cdots, x_{n-1})$。

状态空间树

解空间通常会被描述为树状结构，即状态空间树（通常有子集树和排列树两种形式）。树中每个结点称为一个问题状态。根结点位于第 1 层，表示搜索的初始状态，第二层的结点表示对解向量的第一个分量做出选择后到达的状态，第 1 层到第 2 层的边上标出对解向量第一个分量选择的结果，以此类推。

• 1、2、3 的全排列，状态空间树如下：

• 1、2、3 的子集，状态空间树如下：

从根结点到叶结点的每条路径对应于一个候选解的 n-元组，叶节点也称为解状态。

解状态中至少应包含问题的一个可行解（最优解），可行解处的叶结点被称为答案状态，最优解处的叶结点被称为最优答案状态。

显式约束

显式约束规定了待求解问题的所有可能的候选解，这些候选解组成了问题实例的解空间。也就是说，显式约束决定了状态空间树的规模。

显式约束通常可从问题描述中直接获得，其规定了解向量中每个分量 $x_{i}$ 的取值 $S_{i}$，即 $x_{i} \in S_{i}$。

隐式约束与判定函数

隐式约束用于判定一个候选解是否为可行解。通常从问题描述中的隐式约束出发，设计一个判定函数 $p(x_{0},x_{1},\cdots,x_{n-1})$，若该函数为真，则称候选解 $(x_{0},x_{1},\cdots,x_{n-1})$ 是问题的可行解。

最优解与目标函数

目标函数也称代价函数，用来衡量每个可行解的优劣。组合优化问题的最优解是使目标函数取极值的一个或多个可行解。

部分向量和约束函数

设结点 Y 是状态空间树中的一个问题状态，从根结点到Y的一条路径代表正在构造中的k元组 $(x_{0},x_{1},\cdots,x_{k-1})$，其为n元组解向量的一部分，称之为部分向量。

约束函数是关于部分向量的函数 $B_{k}(x_{0},x_{1},\cdots,x_{k-1})$，其定义为：如果可以判断 Y 的子树上不含任何答案状态，则 $B_{k}(x_{0},x_{1},\cdots,x_{k-1})$ 为 false，否则为 true。

搜索策略和剪枝函数

在状态空间树上执行搜索过程时，为了避免漏掉某些结点，需要遵照某种搜索策略。常见的搜索策略有：

（1）深度优先搜索（Depth First Search，DFS）；
（2）广度优先搜索（Breadth-First-Search，BFS）；
（3）宽深结合。

单纯使用 DFS、BFS 这两种策略进行搜索的方法属于暴力法，搜索效率较为低下。

为了提高搜索效率，回溯算法中使用剪枝函数剪去不必要搜索的子树以进行跳跃式搜索。通常，剪枝函数有两类：

（1）约束函数（Constraint Function）：在搜索过程中使用约束函数可以避免搜索那些不包含答案状态的子树；
（2）限界函数（Bound Function）：在最优化问题中，使用限界函数可以避免搜索那些不可能包含最优答案结点的子树。

隐式图

状态空间树无需事先生成再进行遍历，可以理解为一种隐式图。在状态空间树的生成过程中通常伴随某种遍历策略和剪枝过程。例如，

隐式图是仅给出初始结点、目标结点以及生成子结点的约束条件，要求按扩展规则应用于扩展结点的过程，找出其他结点，使得隐式图的足够大的一部分变成显式，直到包含目标结点为止。

回溯法与分支限界法

• 使用剪枝函数的深度优先生成状态空间树的求解方法称为回溯算法；
• 广度优先生成结点并使用剪枝函数的方法称为分支限界算法。

---

回溯法的设计过程

问题抽象

可以用回溯法解决的问题 P 通常可以表达为：

由 n-元组 $(x_{0}, x_{1}, \cdots, x_{n-1})$ 组成的状态空间如下：

$$V=\{(x_{0}, x_{1}, \cdots, x_{n-1})|x_{i}\in S_{i}, i=0,1,\cdots,n-1\}$$

给定关于 n-元组 中的分量的一个约束集 $D$，求满足 $D$ 的全部约束条件的所有 n-元组。

$S_{i}$ 是 $x_{i}$ 的定义域且 $S_{i}$ 是有穷集，称 $V$ 中满足 $D$ 的全部约束条件的子集为问题 P 的一个或多个解。

回溯法将 n-元组 $(x_{0}, x_{1}, \cdots, x_{n-1})$ 的状态空间 $V$ 表示为一个高度为 $n$ 的带权有序树 $T$，即状态空间树。

有序树：规定了每一层上节点的次序的有向树

基于回溯法隐含的状态空间树，在 $V$ 中求 $P$ 的所有解的过程转化为：在 $T$ 中搜索一条或多条从根节点到叶节点的路径。

回溯法的基本步骤

（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构（找出适当的剪枝函数）；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯法的实现

根据对解空间的搜索方式，回溯算法在实现时主要分为递归回溯和迭代回溯。

回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。

回溯法求问题的任一解时，只要搜索到问题的一个解就可以结束。

递归回溯

一般情况下，当回溯算法对状态空间树做 DFS 时用递归方法实现。

void RBacktrack(int k)
{
    //应以RBacktrack(0)调用本函数
    for (每个x[k],使得x[k]∈T(x[0],…,x[k-1])&&(Bk(x[0],…,x[k])))
    {
        if((x[0], x[1],…,x[k])是一个可行解)   //判定是否为可行解
            输出(x[0], x[1],…,x[k])；        //输出可行解
        RBacktrack(k+1)；                   //深度优先进入下一层
    }
}

迭代回溯

迭代回溯对状态空间树同样做 DFS，但是用非递归方法实现。

void IBacktrack(int k)
{
    int k=0;
    while (k>=0){
        if(还剩下尚未检测的x[k],使得x[k]∈T(x[0],…,x[k-1])&&(Bk(x[0],…,x[k])
        {
            if((x[0], x[1],…,x[k])是一个可行解)  //考虑 x[k]的下一个可取值
                输出(x[0], x[1],…,x[k])；
            k++；                              //考虑下一层分量
        }
        else
            k--;                               //回溯到上一层
    }
}

适用条件

使用回溯法需要注意一下适用条件，也就是问题是否满足多米诺性质：

$$P(x_{0}, x_{1}, \cdots, x_{k-1}) \rightarrow P(x_{0}, x_{1}, \cdots, x_{k-2}), 1 \leq k \leq n$$

其中 $P(x_{0}, x_{1}, \cdots, x_{k})$ 为真则表示向量 $(x_{0}, x_{1}, \cdots, x_{k})$ 满足约束条件，比如：

• 01背包中 k 件物品的总重量小于 M
• n皇后问题中，k皇后放置在彼此不能攻击的位置
• TSP问题中，k 个城市均被走过一次

例子：背包问题

给定 $n$ 种物品和一个背包，物品 $i$ 的重量是 $w_{i}$，价值为 $p_{i}$，背包容量为 $M$。问：如何选择装入背包的物品，使得装入背包中的物品总价值最大？

解空间与显式约束

该问题的候选解集为长为 $n$ 的 0/1 向量 $(x_{0}, x_{1}, \cdots, x_{n-1})$ 组成。

其中 $x_{i} \in S_{i} = \{0, 1\}$ 为显式约束。

状态空间树

以 $n=3$ 为例，解空间 $V$ 是由8个候选解构成：

$$\{(0,0,0)，(0,0,1)，(0,1,0)，(1,0,0)(0,1,1)，(1,0,1)，(1,1,0)，(1,1,1)\}$$

用于表示该解空间的状态空间树为子集树，其形式下图：

该树是一个高度为 $n$ 的完全二叉树，共有 $2n$ 片树叶。从根节点到叶子结点的任意一条路径即为该问题的一个候选解，该路径中第 $j$ 层结点到第 $j+1$ 层 $(1\leq j\leq 3)$ 结点之间的边上给出了对结点 $x_{i}$ 的取值，

隐式约束

隐式约束判定候选解是否为可行解，01 背包问题的隐式约束为不超过背包载重能力：

$$\sum\limits_{i=0}\limits^{n-1}w_{i}x_{i} \leq M \quad w_{i} \geq 0, x_{i} \in \{0, 1\}$$

目标函数

目标函数衡量一个可行解是否为最优解。

$$\max \sum\limits_{i=0}\limits^{n-1}p_{i}x_{i} \quad p_{i} > 0, x_{i} \in \{0, 1\}$$

剪枝函数

01 背包问题中，隐式约束条件可以作为剪枝函数来用。

例子：不等式的整数解

求不等式 $5x_{0} + 4x_{1} - x_{2} \leq 10$ 的整数解。其中 $x_{i} \in \{0, 1, 2\}$。

多米诺条件

由于 P(1, 2, 3) 为真时，P(1, 2) 为假，不满足多米诺条件，不能用回溯法。

代数变换

令 $x_{2} = 3 - x_{2}^{‘}$，于是不等式改为 $5x_{0} + 4x_{1} + x_{2}^{‘} \leq 13$。然后就满足多米诺性质了。

---

组合问题举例

装载问题

$n$ 个集装箱装到两艘载重分别为 $c_{1}$ 和 $c_{2}$ 的轮船，$w_{i}$ 为集装箱 $i$ 的重量，且 $\sum\limits_{i=i}\limits^{n}w_{i}\leq c_{1} + c_{2}$。问：是否存在一种装载方案将 $n$ 个集装箱装到轮船上。

n 皇后问题

要求在 $n \times n$ 格的棋盘上放置彼此不受攻击的 $n$ 个皇后。

图的 m 着色

给定无向连通图 $G$ 和 $m>0$ 种颜色，用这些颜色为 $G$ 的顶点着色，每个顶点一种颜色。问：是否有一种着色方法使得图 $G$ 中每条边的 2 个顶点着不同颜色。（若一个图最少需要 m 种颜色才能使得图中每条边的 2 个顶点着不同颜色，称 m 为图的色数）

子集和问题

有 n 个元素的正整数集 $w=\{w_{0}, w_{1}, \cdots, w_{n-1}\}$ 和一个正整数 $M$，要求从集合 $W$ 中找出所有满足元素的累加和等于 $M$ 的子集。

图搜索问题举例

图的遍历

图的遍历是指从图中某个顶点出发，沿着图中的边按照某种策略进行搜索，访问图中所有顶点一次且仅访问一次。

图的遍历策略主要有两种：深度优先搜索遍历(DFS)和广度优先搜索遍历(BFS)。DFS 是回溯思想的代表。

旅行商问题

某推销员要到若干城市去推销商品，已知各城市之间的路线（或旅费）。他要选定一条从驻地（不妨设为第一个城市）出发，经过每个城市一次，最后回到驻地的路线，使总路程最短（或总旅费最小）。

最大团问题

给定无向图 $G=(V, E)$，对于图 $G’ = (V’, E’)$，若 $V’ \subseteq V$ 且 $E’ \subseteq E$，称 $G’$ 为 $G$ 的子图。记为 $G’ \subseteq G$。

下面是团的相关概念：

• 若 $V’ = V$，则 $G’$ 是 G 的生成子图(支撑子图)。
• 若对任意 $u,v \in V’$，只要 $uv \in E$，就有 $uv \in E’$，则 $G’$ 为 G 的导出子图，记为$G’ \lhd G$, 此时 $G’$ 也记为 $G[V’]$
• 若 $G’$ 是 $G$ 的导出子图，且对任意 $u,v \in V’$，都有 $uv \in E$，称 $G’$ 为 $G$ 的完全子图。此时称 $V’$ 为 $G$ 的团。$G$ 中顶点数最多的团称为最大团。

下面是独立集的相关概念：

• 若对任意 $u,v \in V’$，都有 $uv \notin E$，称 $G’$ 为 $G$ 的空子图。$G$ 的空子图不包含在 $G$ 的更大的空子图中时，$V’$ 称为 $G$ 的独立集。$G$ 的顶点数最多的独立集称为最大独立集。

图 $G = (V, E)$ 的补图为 $\overline{G} = (V, \overline{E})$。其中 $\overline{E} = \dbinom{V}{2} \setminus E$，则 $G$ 的完全子图就是 $\overline{G}$ 的空子图，也就是 $G$ 的团与 $\overline{G}$ 的独立集之间存在一一对应关系。$V’$ 是 $G$ 的最大团当且仅当 $V’$ 是 $\overline{G}$ 的最大独立集。

图G的最大团和最大独立集问题都可以看作是图G的顶点集V的子集选取问题。因此可以用子集树来表示问题的解空间。

哈密顿环问题

已知图 $G = (V, E)$ 是一个 n 节点的连通图，$G$ 的哈密顿环是一条经过 $G$ 的 n 个节点的路径，它访问每个节点一次且返回开始位置。

---

回溯法的分析

回溯法在很多情况下属于暴力法，因此最坏情况下的时间复杂度会比较差。

回溯法的平均情况下的时间复杂度通常取决于状态空间树上实际生成的那部分问题状态的数目。由于回溯法往往会在搜索过程中对问题的解空间进行大量剪枝，实际生成的节点可能就不是特别多了，但实际生成多少节点事先很难估计。

---

回溯法的改进

状态空间树的结构可以影响回溯算法的效率，体现在：

（1）分支情况：分支是否均匀；
（2）树的深度：深度越深，通常效率越低下；
（3）对称程度：具有高对称性的状态空间树适合裁剪，即状态空间树越对称，则算法效率越高。比如n皇后问题。

解的分布明显影响算法的最终效率。所以在评估算法效率时，需要考虑到解在不同子树中分布的数量和深度，以及分布是否均匀。

针对回溯算法的改进，有以下途径：

（1）根据树分支设计改进策略，结点少的分支优先，解多的分支优先；
（2）利用状态空间树的对称性裁剪子树；
（3）分解为子问题。

---

回溯、DFS与递归

可以简单理解为 回溯 = DFS + 剪枝。一般在用 DFS 时，一般都会或多或少地剪枝，因此 DFS 几乎可以等同于回溯。

DFS 是一种搜索策略（DFS/BFS），递归是一种实现方式（递归/递推），DFS 一般会用递归来实现，因此 DFS 与递归常常一起出现。

• 算法和数据结构则通过划分、归纳、提取、抽象来帮助提高程序遍历状态空间的效率。递推和递归就是程序遍历状态空间的两种基本方式。
• 递归在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。
• 如果待解决的问题呈现出问题的解依赖于同一个问题的更小实例的解这样的特性，则与递归吻合，在算法设计时可以考虑分治、减治、回溯等算法思想，它们隐含了递归。

---