501-回溯法

回溯法的算法框架

什么时候使用回溯法

• 当需要找出问题的解集或者满足某些约束条件的最优解时常使用回溯法
• 回溯法的基本方法就是搜索，是一种组织得井井有条的，能规避不必要搜索的穷举式搜索法
• 这种方法适用于解一些组合数相当大的问题，如排列、子集 0-1 背包问题、n 皇后安排问题等可以使用回溯法

回溯法的流程

• 回溯法在问题的解空间树中，按深度优先策略，从根节点出发搜索整个解空间树
• 算法搜索值解空间树的任意一点，先判断该节点是否包含问题的解
• 如果不包含，跳过对该节点为根的子树的搜索树，继续该节点兄弟节点的搜索
• 否则，进入该子树，继续按深度优先策略搜索

名词解释

• 问题的解向量：回溯法希望一个问题的解能够表示成一个 n 元组 $(x_1,x_2,\dots ,x_n)$ 0-1 背包问题 n 元组-每个物品是否选择组成的 01 n 元组
• 显约束：对分量 $x_i$ 的取值限定
• 隐约束：为满足问题的解而对不同分支施加的约束 (如 01 背包要求背包装的物品价值最高)
• 解空间：对问题的一个实例，解向量满足显示约束条件的所有 n 元组，构成了该实例的一个解空间。组织成一棵树=⇒解空间树

注意：同一个问题可能有不同的解空间树表示，有些表示方法更简单，解空间更小，搜索方法更块

• 扩展节点：一个正在产生儿子的节点称为拓展节点

• 活结点：一个自身以生成但其儿子还没有全部生成的节点乘坐活节点

• 死结点：一个所有儿子已经产生的节点称作死结点

• 深度优先问题的状态生成法（演示）： 如果对一个扩展节点 R，一档长生了他的儿子 C，就把 C 当作新的扩展节点，R 称为活结点。在完成对子树 C（以 C 为根的子树）的穷尽搜索之后，将 R 重新变成扩展即欸但，继续生成 R 的下一个儿子（如果存在） R 的全部孩子即欸但产生完毕，R 称为死结点

• 宽度优先的问题状态生成法：在一个扩展节点变成死结点之前，它一致是扩展节点（第六章内容）

• 回溯法：为了避免生成那些不可能产生最佳接的问题的问题状态, 要不断利用简直函数来处理那些实际上不可能产生所需解或最优解的儿子节点，以减少问题的计算量

• 具有剪枝函数的深度优先生成树法称为回溯法

回溯法的基本思想

1. 针对所给问题，定义问题的解空间（所有可能的解的集合）
2. 确定易于搜索的解空间结构（树）
3. 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

常用的剪枝函数：

1. 用约束函数在扩展节点出剪去不满足约束的子树；
2. 用限界函数剪去得不到最优解的子树

回溯法解题的一个显著特征：搜索过程中动态产生问题的解空间树，即边搜索边拓展分支 （不同于数据结构中树的深度遍历方法，先创建树，再深度遍历）

在任何时刻，算法只保存从根节点到当前拓展节点的路径

若解空间树从根节点到叶节点的最长路径的长度为 $h(n)$，则回溯法所需的计算空间通常为 $O(h(n))$

显示的存储整个解空间则需要 $O(2^{h(n)})$ 或 $O((n)!)$ 的内存空间

递归回溯算法框架

子集树与排列树的回溯算法框架

子集树回溯算法，首先判断路线长度是否到达 n ，到达了输出结果 x 数组中保存了结果 否则 for 循环遍历当前节点的两个子树，如果子节点满足约束条件，递归到下一层，t+1 来标记到达的层数

排列树回溯算法，判断路线长度和子集树一致 否则需要遍历所有的排列情况；首先遍历剩余可选择的节点，把选择到的节点先放到 $x[t]$ 的位置，此时包括 $x[t]$ 在内的左边都是已经选择好的元素，右边都是待选择的元素，这样数据规整的放到两边方便递归算法处理，递归时只需要从右边待选择的元素中遍历就可以了；递归结束再把元素放回原来的位置

装载问题

以三个集装箱为例

三个集装箱，每个集装箱有装和不装两个选择，可以得到解空间树如图 搜索这棵树来找到最佳答案 搜索方法使用递归方法

第一个 if 是到达叶子节点结束时，输出结果 r 保存剩下没有判断的集装箱的重量和 第二个 if 搜索左子树，保证单前重量 cw 加上当前集装箱 $w[i]$ 不超过船的重量上限；递归搜索完，需要把当前重量恢复成没装这个集装箱的大小，方便后续搜索右分支（不装当前集装箱的情况） 第三个 if 搜索右子树，保证剩余的集装箱的重量加上当前集装箱的重量大于 bestw，否则这里也没有最优解，没必要搜索了 最后退出这一节点，回到上一层，把剩余重量 r 还原

时间复杂性 使用回溯法解装载问题的时间复杂性是 $O(2^n)$。在某些情况下概算法优于动态规划算法

回溯法如何计算其时间复杂性？

1. 计算出解空间中除叶子层之外的节点总数 $f(n)$
2. 每个非叶子即欸但扩展出其下一层的所有分支的时间复杂性 $g(n)$
3. 复杂性为 $O(f(n)\ast g(n))$ 以最优装载问题为例，$f(n)=w^n-1,g(n)=O(1)$，因此其时间复杂性为 $O(2^n)$

本章讨论的时间复杂性只有理论意义，没有实际意义，因为计算的是在没有任何剪枝的情况下的时间复杂性，实际上效率要好很多

例子

批处理作业的调度

这里机器 2 的完成时间是从开始开始计算，中间可能会有空闲的时间也要计算上

三个作业一共有 6 种排列顺序 以顺序 132 为例 开始时刻是 0 先进行作业 1，分别耗时 2，1，第二个机器要在第一个机器结束之后开始，所以 $Fi2$ 是 2+1=3 进行作业 3，分别耗时 2，3，第一个机器在结束上一个作业的基础上开始，即 2+2=4，第二个机器需要在第一个机器结束之后进行，还要在上一个任务结束后进行，此时第一个机器结束更晚，从 4+3=7 进行作业 2，分别耗时 3，1，第一个机器 7+3=10，第二个机器max（10,7）+1=7+1=8

解空间树是：排列树

第一个 if 来保存最优排列和最优值 f，f 是每一个作业结束时间的累加和 for 循环对应排列树中的搜索方式 f 1 是第一个机器作业完成的时间；$f2[i]$ 是第二个机器作业完成的时间，他从 $f2[i-1],f1$ 中更晚完成的时间过来 如果当前 f 小于bestf 可以进行递归，否则剪枝剪掉 将当前任务作为排好的换到左边，此时 $x[i]$ 以及左边是排顺序的任务，右边是待排列的任务 递归完成，把任务换回原来的位置 f 1 ，f 回退到上一个任务的状态

符号三角形

根据第一行的样式，向下拓展符号，前一行相邻的符号相同得到当前符号是+，前一行符号不相同得到当前符号是-

算法需要在解空间树中查找（第一行的各种组合）

解向量：用 n 元组 $x[1:n]$ 表述符号三角形的第一行 可行性约束函数：当前符号三角形所包含的”+“个数和”-“个数均不超过 n*（n+1）/4=half (均不超过子树节点数量的一半)

无解的判断：n*(n+1)/2 为奇数（树的节点数为奇数，两种符号不能平分）

第一个 if 判断两种符号有没有超过整个树的一半节点数，超过了，直接结束 (裁剪) 第二个if 判断搜索的第一行符号是否到达最后（且符合节点相等条件），记录解的数量 i 控制的循环遍历左右子树，分别代表，第 1 行的第 t 个符号是 + 或 - ；count 记录减号个数 j 控制的循环，当第一行增加一个符号之后，整个子树最右边就会多出一列，这个循环用来把这一列填上符号，同时记录减号的个数 递归到下一个符号 for 循环退出这一个符号选择，把刚刚加上的一列的 count 数值退掉 count 退掉第一行这个节点的计数

时间复杂度 计算可行性约束（计算刚加上的那一列里面符号的个数）需要 $O(n)$ 时间，最坏情况下有 $O(2^n)$ 个即欸但需要计算可行性约束，故解符号三角三角形问题的回溯算法所需的计算时间为 $O(n{2}^n)$

N 皇后问题

第一种解空间树是 4 叉树

每个皇后在一行上有四个可选位置（显约束：两个皇后不同行）

解向量：$x_1,x_2,...,x_n$，每一行一个皇后的位置 显约束：$x_i=1,2,...,n$ 任意两个皇后不同行 隐约束：1. 不同列：$x_i!=x_j$ 2. 不处于同一正/反对角线：$|i-j|\ne |x_i-x_j|$

Palce 是判定隐约束的函数，包括判断新的皇后是否和之前的皇后同列或者同一斜线，都不在返回true

Backtrack 函数是回溯的函数 第一个 if 记录符合的答案个数 否则 for 循环遍历 n 个分支，即下一层的皇后可以选择的所有位置，然后判断是否符合隐条件，递归到下一行

解空间树是排列树

显约束：任意两个皇后不同行，不同列

解向量：$x_1,x_2,...,x_n$，每一行一个皇后的位置 显约束：任意两皇后不同行、不同列。$x_1,x_2,\dots ,x_n$ 是 1，2，…，n 排列 隐约束：不处于同一正/反对角线：$i-j\ne |x_i-x_j|$

Place 函数是判别隐约束条件，当前皇后和前面所有皇后不再同一斜线 Backtrack 函数使用排列树回溯算法，递归查找答案

0-1 背包问题

0-1 背包问题的解是从 n 个物品中选出一定量的物品保证最终价值最大，它的解是所有物品的一个子集

解空间：子集树 可行性约束函数：${\sum }_{i=1}^n{w}_i{x}_i\le c_1$

该问题和装载问题的区别在于限界函数，即对右分支进行剪枝的函数，在装载问题中，右分支是不选择当前物品，如果不选择当前物品，剩下的货箱加上当前装的货箱数量小于最优解，那右分支就没必要在遍历了

同样对于 0-1 背包问题，我们需要限界函数能够判断右分支（不选择当前物品）能否获得更高的价值，否则就没必要遍历了 这是设计了一个 bound 函数，对剩下的物品进行贪心选择（需要提前按照单位重量价值比排列好数据），来判断时候需要对右分支进行搜索

左子树if：cw 是当前重量，cp 是当前价值；然后递归到下一个物品选择；回溯 cw 和 cp，准备进入右子树（不选择当前物品） 右子树 if: 先判断剩余的物品（i+1 及其之后的物品）能够装进背包的价值是否超过 bestp；然后递归

限界函数

贪心计算从 i 物品开始及其之后的所有物品的最大价值 cleft 是背包剩余的空间；b 是总价值 While 循环结束有两种情况，一个是物品全装进去了；一种是背包满了，还剩一个小空间塞不进去了 背包满了，还需要把最后一个物品切出一小部分塞到背包中 (对应最后if)，这样估计出价值的边界

最大图问题

最大团中的点任意两个都有连接，如图中 125，145，235

解空间：子集树 可行性约束函数：顶点 i 到已选入的顶点集中每一个顶点都有边相连 上界函数：有足够多的可选择顶点，使得算法有可能在右子树中找到更大的团

第一个 if 如果遍历完一次所有节点，保存最大团的节点，和最大团点的数量 下一个 for 循环，检查和前 i-1 个节点和第 i 个节点是否都有连接|构成最大团 下一个 if，满足和前 i-1 个节点有连接可以进入左子树，递归到下一个节点 下一个 if，判断剩余节点加上已经选择的节点是否大于最优情况的节点数，满足则进入右子树，不选择当前节点，递归到下一个节点

时间复杂性 最大团问题使用回溯法所需的时间复杂度 $O(n{2}^n)$，整个树的节点是 $2^n$ 规模，每个节点需要判断和前 i-1 个节点是否相连，规模为 $n$

图的 m 着色问题

把涂色表示成图的结构，表示他们的相邻关系

解向量： $(x_1,x_2,\dots ,x_n)$ 表示顶点 i 所着颜色 可行性约束函数：顶点 i 与已着色的相邻点颜色不重复

第一个 if 保存答案个数 接下来 for 循环，遍历当前顶点可选择的颜色，ok 函数来判断当前颜色 i 是否可选，可选递归为下一个节点选择颜色

Ok 函数检查选择的颜色是否可选，通过遍历已经涂好颜色的（j<k）且和 k 顶点相连（$a[k][j]==1$）的顶点的颜色（$x[j]==x[k]$），是否和 k 节点相同来判断

圆排列问题

因为大小不同的圆摆在一个平面上时，小圆可以躲在大圆下面，所以不同的排列方式会导致全部圆所占的水平长度

观察

可以看到圆排列好之后，不一定第一个圆的最左边就是起始位置，如上图，第一个圆很小，第二个圆很大; 同样最后一个圆不一定是决定最优边界的

左右边界：使用所有圆的圆心坐标减去半径，在其中取最小值作为左边界；同样用所有圆圆心坐标加上半径作为右边边界 对于 i+1 个圆，计算他的坐标，需要假设他和之前的每一个圆相切，计算出坐标，使用横轴坐标最大的那个坐标

代码

第一个 if 记录最优答案 接下来 for 循环，使用排序树的方式，遍历剩余的可选择的圆；先把选择的顶点放到应经选择的顶点后面，使用 swap 交换过去；计算出当前圆的圆心；粗略的检查当前的左右粗略宽度是否超过最小值；使用右边境：当前圆的坐标加上半径，左边境：第一个圆的坐标减去半径；即 $centerx+r[t]-(0-r[1])$，来粗略估计; 满足条件，把圆心保存递归到下一个圆的选择 最后回退圆的数据位置

计算加入当前圆之后，当前圆的位置，这个顺序是按照加入顺序固定的，不存在叉到前面的情况； 假设当前圆和前面的圆都相切，计算出圆心，选数值最大（最靠右的）的圆心作为当前圆的圆心

计算出左右边界，相减的圆排列长度；分别用每个圆的圆心加上/减去半径得到每个圆的左右边界，在取左边界最小值，右边界最大值，做差得到圆排列长度

观察可以看到，计算一次准确的左右边界，需要遍历所有的圆，非常消耗时间，所以界限函数使用了一个粗略的估计，减少算法开销

待改进

去重复排列是说，有半径相同的圆的时候，当选择第 i 个圆时，这些相同的圆是等价的，可以直接算一个

排列树搜索-补充

回顾 回溯法是解空间树上搜索解的算法 常见的解空间树：子集树、n 叉树、排列树

N 个元素构成的排列树：

1. 元素互不相等，每个从根到叶子的路径信息构成一个独立的排列
2. 有重复元素是，全排列中会有重复排列
3. 有些问题互为镜像的两个排列只考虑一个即可，如何去掉镜像的拍列

下面以输出全排列为例讲解算法设计思路 针对具体问题，参考本问题

输出 n 个不同元素的全排列

这一小节就是之前的排列树的知识点，略

n 个有重复元素，输出无重复的全排列

t 及之后 122，用来作为下一层的可选元素，其中包括重复元素 2，当遍历到第二个元素 2 时，对前面遍历过的当前层数据进行对比，看当前元素是否出现过，出现过就跳过递归，进行下一个元素的判定

代码对比之前的代码，只多了红色部分; 当前层从 i=t 开始到 i=n 结束，当 i 遍历时，把当前元素和从 t 到 i-1 的元素进行对比，跳过重复元素

n个不同元素, 输出去镜像的全排列

对于一对镜像排列，首尾元素存在大小关系，只要限制首元素大于尾元素或尾元素大于首元素，就可以保证把镜像情况去掉 具体实现，先确定首元素，根据大小找一个尾元素，把剩余的 n-2 个元素进行全排列

demirror 函数是确定首尾元素，首元素交换到 $x[1]$，尾元素交换到 $x[n]$ ，对中间的 n-2 个元素进行回溯递归，递归完成交换回 $x[1],x[n]$

总结

1. 去镜像搜索时间耗费降低为原来的 $\frac{1}{2}$
2. 一个 n 元素集合，有 k 个元素是重复的，重复度是 $p_1,p_2\dots p_k$，则无重复排列数是：$\frac{n!}{p_1!p_2!\dots p_k!}$
3. 回溯法之排列树，根据问题考虑是否去重负，去镜像
4. 考虑：既要去重复，又要去镜像，算法如何设计？

电路板排序问题-补充

这些连接块是固定的，需要排列的是槽，改变槽的排列可以改变跨越槽的最大连线数

例

把 N 理解成一个多头的数据线，他的每一个头需要插到槽上，这样这一股线就会跨过其他中间的槽，每跨过一条线会让 Density 增加，反应线的密集程度。通过排列，让最大的 Density 变小

问题分析

• 回溯法，解空间树：排列树，找出电路板的最佳排列
• 整型数组 B 表示输入 . $B[i][j]$ 的值为 1 代表电路板 i 在连接块 $N_j$ 中
• 设 $totel[j]$ 是连接块 $N_j$ 中的电路板数
• 对于电路板的部分排列 $x[1:i]$，设 $now[j]$ 是 $x[1:i]$ 中所包含的 $N_j$ 中的电路板数
• 连接块 $N_j$ 的连线跨越插槽 i 和插槽 i+1 之间，当且仅当 now[j]>0 且now[j]!=total[j] 用这个条件来计算 m 个连接块跨越插槽 i 和 i+1 之间的连线条数

数组 B，每一列代表一个连接块 $N_j$ 其中数值 1 代表这个电路板在连接块中

算法设计

第一个 if，递归长度到达 n，代表一次排列完成，且因为后面剪枝的效果可以保证此时是更优解 第一个 for 循环，从剩余的槽中选择一个 第二个 for 循环，遍历每个连接块，找到插在当前槽上的连接块（通过 $now[k]$ 变成 1）；比较每个连接块已经组合好的槽数 $now[k]$ 和每个连接块总的槽数 $total[k]$，只要是 now>1 说明这个连接块在左边使用了至少一个槽，now<total 说明这个连接块在右边还有要使用的槽，此时当前位置上面就会有一条线，把线的数量记录起来 比较 cd，ld，保留更大的连线数 如果当前最大连线数小于当前最大连线数，继续递归到下一个槽，否则结束 最后 for 循环把 now 数组回退 注意: 王学东哪本教材，最后的 for 循环位置错误，应该是上面代码的位置

算法分析

时间耗费最多的计算量是拓展孩子节点 最坏的情况下，所有的孩子节点都被拓展出来，也就是解空间树去掉根节点和解空间数的最后一层节点（叶子层不再拓展），剩余的节点总数，可知是 $cn!$ 个（可查文献）(c 未必是正数，是一个比较小的常量)

每个孩子节点出花费 $O(m)$ 计算时间（每个儿子节点计算草荐连线数需要耗费 $O(m)$，还原 now 数组需要耗费 $O(m)$

因此，回溯算法 Backtrack 所需要的时间复杂度为 $O(mn!)$

总结

1. 问题的解空间数是排列树
2. 叶子层是 n-1 层的节点（因为最后一个节点右边没有连接线）
3. 剪枝条件 $ld<bestd$
4. Bacjtracj (int i, int cd)，双参数设计

回溯法通常时间复杂度非常高，时间复杂度是最坏情况下的，但是回溯法实际上会剪掉很多分支，他的性能实际上比理论上会好很多，因此虽然理论时间复杂度很高，但是实际中还会使用回溯法

算法演示

完整代码在专栏

连续邮资问题

每个邮件最多 m 个邮票，把邮件的总价值变成，1，2，3，4 … 的连续增数列，求数列最多多长 只限制 n 和 m，面值需要选择

问题分析

处理过程中，首先选择第一个面值的邮票，计算出他可以表示的连续数值范围，其中最大数值（右边界）记为 r；例如数值为 1 的邮票，当 m=4 时（最多四张邮票），可以组成 1，2，3，4 四种数值，那么 r=4； 接下来考虑两种面值（按照面值递增顺序）的情况，对第二种数值有俩个条件，第一，要比前一个面值大（已经在面值递增中保证了）；二，需要小于等于一种面值时的 r+1（如果大于 r+1 ，数值就不能连续了）；所以上面说 $x[2]$ 的取值在 2~5 之间，即 $x[i]$ 的取值需要在 $x[i-1]+1,r+1$ 之间

第一个面值必须选择 1，后续逐层递归选择，但是需要保证子节点满足（2）中的条件： 新的节点面值在 $x[i-1],r$ 之间

第一个 for 循环，j 的范围是 $[0,x[i-2]\ast (m-1)]$，代表 m-1 张第 i-2 个面值的邮票，预留了一张的位置是留给第 i-1 个面值的邮票，这个数值代表了前 m-1 中邮票的数值的上限（实际可能到不了）；

遍历这些数值，$y[j]$ 中保存了组成数值 j 需要的最小的邮票张数，当 $y[j]<m$ 代表在数值 j 的基础上还可以在添加几张邮票，这样数值 $j+x[i]\ast \text{可添加邮票张数}k$ ，这些数值中的最小邮票张数可能会更新，通过比较原来的票数 $y[j+x[i-1]\ast k]$ 和在 j 的基础上添加 k 张票的票数 $y[j]+k$，保存更少的票数到 $y[j+x[i-1]\ast k]$

y 数组中初始数值是 maxint，代表这个数值还没有被表示出来；在 for 循环结束后，可能会有比 r 还大的数值被表示出来，使用 while 循环来跳过这些已经连续起来的数值，循环结束时 r 在最后一个连续数值后面，在使用 r—变成能表示的连续数值上限

赋初始值，因为数值为 1 的情况肯定存在，所以从 i=2 开始遍历，此时需要 i-2 个面值的上界 r，即只有 $x[0]$ 面值（没有面值）时的情况，此时r=0；后面 i=1 是的 r 可以有 i=1 是的情况根据（6）计算出来

算法设计

第一部分代码，更新 y 数组，即（6）的过程 接下来 if，判断是否到达叶子节点，判断是否需要保存最优值，和最优值所选择的面值 Else 中首先使用 z 数组保存 y 数组，方便递归后恢复 y 数组 接下来 for 循环选择所有可选择的面值，进行递归，递归中会修改 y 数组数值，递归结束后，外面使用 z 数组恢复 y 数组；然后删除 z 数组

总结

算法演示

旅行售货员问题

1. 因为是环路问题，从哪一个城市出发都可以，所以直接指定一个开始城市；直接减少了 n-1 个分支
2. 由于当只剩下一个城市的事后就没的选择了，我们把最后的叶子几点提到 n-1 层，因为 n-1 层确定了，第 n 层也是确定的

第一个 if 当到达第 n 层时，判定第 n -1 个城市和第 n 各城市是否有连接，以及第 n 个城市和第 1 个城市是否右连接，这样能形成环路；然后检查是不是最短路线，保存最优路线 bestx 和最优距离 besc

Else 遍历剩下的城市，先判断这个城市和 i-1 城市是否相连，且加上这一段长度小于最好的长度 bestc; 或者当前城市是第一个城市，没有前一个城市

回溯法效率分析与总结

约束函数对下一个要展开的节点进行约束 限界函数是一个估计右分支数值范围的

重排原理 对许多问题而言，在搜索试探时选取 $x[i]$ 的值顺序是任意的。其他条件相当的前提下，让可取值最少的 $x[i]$ 优先. 观察下图

这样上层分支更少，如果发生裁剪，减去的分支节点更多

小结