回溯法三种常见的状态空间树：子集树、排列树、满m叉树

摘要: 三种常见的状态空间树

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

---

回溯法

在文章 回溯法的思想、设计与分析 中，我们系统地了解了回溯法的思想。

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

状态空间树无需事先生成再进行遍历，因此可以理解为一种隐式图。回溯法就相当于在隐式图上的 DFS 搜索，并且过程中通常伴随剪枝过程：

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

回溯法的处理过程是一个逐步建立并修正状态空间树的过程，步骤如下：

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

在用回溯法解决的问题中，有三类非常典型的状态空间树：

• 子集树
• 排列树
• 满m叉树

回溯法的子集树、排列树、满m叉树这三种状态空间树分别对应了带有约束函数、限界函数等条件下的指数型枚举、排列型枚举、多项式型枚举。遍历这三棵树，也就分别实现了相应的满足条件的子集枚举、排列枚举、多项式枚举。

在文章 常见的枚举方式 中，我们以模板题了解了不带约束的子集、排列、组合这三种类型的枚举过程，并且给出了代码模板。这里可以作为对比。

本文我们分别看一下这三类状态空间树，以及对应的带约束函数、限界函数等条件的指数型枚举、排列型枚举、多项式型枚举的过程。

---

子集树

当问题是从 n 个元素组成的集合 S 中找出满足某种性质的一个子集时，回溯法相应的状态空间树称为子集树。

这类问题的解的形式是 n 元组 $(x_{0}, x_{1}, \cdots, x_{n-1})$，$x_{i}$ 表示第 i 个元素是否在子集中。

下图是回溯法枚举 1、2、3 的子集，对应的子集树：

子集树通常有 $2^{n}$ 个叶结点，其结点总个数为 $2^{n+1}-1$。遍历子集树的时间复杂度为 $O(2^{n})$。

代码模板

用回溯法搜索子集树的代码模板大致如下：

/*
 * output(x): 输出可行解 x
 * constraint(t) 当前节点的约束函数
 * bound(t) 当前节点的限界函数
 * t: 当前解空间的层数
 */
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);
        }
    }
}

经典问题

• 01背包问题
• 子集和问题
• 装载问题
• 最大团问题

---

排列树

当问题是从 n 个元素的排列中找出满足某种性质的一个排列时，相应的状态空间树称为排列树。

这类问题的解的形式是 n 元组 $(x_{0}, x_{1}, \cdots, x_{n-1})$，$x_{i}$ 表示第 i 个元素是 $x_{i}$。

下图是回溯法枚举 1、2、3 的全排列，对应的排列树：

排列树通常有 $n!$ 个叶结点。遍历排列树的时间复杂度为 $O(n!)$。

代码模板

用回溯法搜索排列树的代码模板大致如下：

/*
 * output(x): 输出可行解 x
 * constraint(t) 当前节点的约束函数
 * bound(t) 当前节点的限界函数
 * t: 当前解空间的层数
 */
void Backtrack(int t)
{
    if(t > n)
        output(x);
    else
    {
        for(int i = t; i <= n; i++)
        {
             swap(x[t], x[i]);
             if(constraint(t) && bound(t))
                 Backtrack(t + 1);
             swap(x[t], x[i]);
        }
    }
}

经典问题

• n皇后问题，显式约束为不同行、不同列的状态空间树。在不同行的前提下，n 个皇后的列位置是 n 个列的一个排列，这个排列必须满足 n 个皇后的位置不在一条斜线上。
• 旅行商问题
• 批处理作业调度问题
• 电路板配列问题

满m叉树

当问题的 n 个元素中每一个元素均有 m 种选择，要求确定其中的一种选择，使得对这 n 个元素的选择结果组成的向量满足某种性质。即寻找满足某种特性的 n 个元素取值，这些取值构成一个 n 元向量，向量每个元素的取值有 m 种。相应的状态空间树为 n 层满 m 叉树。

这类问题解的形式为 n 元组 $(x_{0}, x_{1}, \cdots, x_{n-1})$，$x_{i}$ 表示第 i 个元素的选择为 $x_{i}$。

从 1,2,3 中选出 3 个数，可以重复选，对应的满 3 叉树如下：

满m叉树通常有 $m^{n}$ 个叶结点。遍历排列树的时间复杂度为 $O(m^{n})$。

代码模板

用回溯法搜索满m叉树的代码模板大致如下：

void Backtrack(int t)
{
    if(t > n)
        output(x);
    else
    {
        for(int i = 1; i <= m; i++)
        {
            if(constraint(t) && bound(t))
            {
                 x[t] = i;
                 // 做其他相关标识;
                 Backtrack(t + 1);
                 // 做其他相关标识的反操作; // 退回相关标识
            }
        }
    }
}

经典问题

• n皇后问题：显式约束为不同行的状态空间树。在不同行的前提下，任一皇后的列位置都有 n 种取值选择。n 个列位置的取值构成一个 n 元向量，该向量的取值必须满足 n 个皇后的位置不在同一列或不在同一条斜线上的性质。
• 图的m着色问题：给定⽆向连通图$G$和$m$种不同的颜⾊。⽤这些颜⾊为图$G$的各顶点着⾊，每个顶点着⼀种颜⾊。是否有⼀种着⾊法使$G$中每条边的$2$个顶点着不同颜⾊。

---