第五章 回溯法
填空题会有代码填空，大题会手动回溯
学习要点
理解回溯法的深度优先搜索策略。
掌握用回溯法解题的算法框架
（1）递归回溯
（2）迭代回溯
（3）子集树算法框架
（4）排列树算法框架
5.1 回溯法的算法框架
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。
回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
1、问题的解空间
用回溯法解问题时，应明确定义问题的解空间。
解空间往往用向量集表示。
问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。
显约束：对分量xi的取值限定。
隐约束：为满足问题的解而对不同分量之间施加的约束。
解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。
2、回溯的基本思想
扩展结点：一个正在产生儿子的结点称为扩展结点。
活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结点。
死结点：一个所有儿子已经产生的结点称做死结点。
深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）。
宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点。
回溯法从开始结点（根结点）出发，以深度优先方式搜索整个解空间。
基本思想
1?? 针对所给问题，定义问题的解空间；
2?? 确定易于搜索的解空间结构；
3?? 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索
常用剪枝函数：
用约束函数在扩展结点处剪去不满足约束的子树；
用限界函数剪去得不到最优解的子树。
3、递归回溯——背诵
void Backtrack (int t) //t为递归深度
{
if (t>n)
Output(x); //记录或输出可靠解x，x为数组
else
for (int i=f(n,t); i<=g(n,t); i++)
{
//f(n,t)表示在当前扩展结点处未搜索过的子树的起始编号
//g(n,t)为终止编号
x[t]=h(i); //h(i)表示当前扩展结点处x[t]的第i个可选值
if (Constraint(t)&&Bound(t)) //剪枝
Backtrack(t+1);
}
}
回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。
4、迭代回溯——会填空即可
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(t)&&Bound(t)){
if (solution(t)) //判断是否已得到可行解
Output(x);
else
t++;
}
}
else
t--;
}
}
f(n,t)表示在当前扩展结点处未搜索过的子树的起始编号
g(n,t)为终止编号
h(i)表示当前扩展结点处x[t]的第i个可选值
5、子集树和排列树(重点)
子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。时间复杂度 Ω ( 2 n ) Ω(2^n) Ω(2n)。算法描述如下：
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);
}
}
排列树当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。时间复杂度 Ω ( n ! ) Ω(n!) Ω(n!)。算法描述如下：
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]);
}
}
5.2 装载问题
1、问题描述
有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且 ∑ i = 1 n w i ≤ c 1 + c 2 \sum _{i=1}^n w_i\le c_1+c_2 ∑i=1n?wi?≤c1?+c2?，装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这2艘轮船。如果有，找出一种装载方案。
例如：
n=3, c1=c2=50，且w=[10,40,40]。
装载方案：
第一艘轮船装集装箱1和2；二艘轮船装集装箱3。
如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近c1。
2、算法分析
解空间：子集树
可行性约束函数(选择当前元素)： ∑ i = 1 n w i x i ≤ c 1 x i ∈ { 0 , 1 } \sum _{i=1}^n w_i x_i\le c_1\quad x_i\in\{0,1\} ∑i=1n?wi?xi?≤c1?xi?∈{0,1}
template<typename Type>
class Loading
{
template<typename T>
friend T MaxLoading(T [],T,int);
private:
void Backtrack(int i);
int n; //集装箱数
Type *w; //集装箱重量数组
Type c; //第1艘轮船的载重量
Type cw; //当前载重量
Type bestw; //当前最优载重量
};
template<typename Type>
void Loading<Type>::Backtrack(int i) //搜索第i层结点
{
if(i>n) //到达叶结点
{
if(cw>bestw)
bestw=cw;
return;
}
if(cw+w[i]<=c) //进入左子树，x[i]=1
{
cw+=w[i];
Backtrack(i+1); //继续搜索下一层
cw-=w[i]; //退出左子树
}
Backtrack(i+1); //进入右子树，x[i]=0
}
template<typename Type>
Type MaxLoading(Type w[],Type c,int n) //返回最优载重量
{
Loading<Type> X;
X.w=w; //初始化X
X.c=c;
X.n=n;
X.bestw=0;
X.cw=0;
X.Backtrack(1); //从第1层开始搜索
return X.bestw;
}
int main()
{
const int n=6;
int c=80;
int w[]={0,20,40,40,10,30,20}; //下标从1开始
int s=MaxLoading(w,c,n);
cout<<s<<endl;
return 0;
}
算法在每个结点处花费O(1)时间，子集树中结点个数为O( 2 n 2^n 2n)，故算法的计算时间为O( 2 n 2^n 2n)。
3、上界函数
对于上一算法可引入一个上界函数，用于剪去不含最优解的子树。
上界函数(不选择当前元素)：当前载重量cw+剩余集装箱的重量r≤当前最优载重量bestw。
template<typename Type>
class Loading
{
template<typename T>
friend T MaxLoading(T [],T,int);
private:
void Backtrack(int i);
int n; //集装箱数
Type *w; //集装箱重量数组
Type c; //第1艘轮船的载重量
Type cw; //当前载重量
Type bestw; //当前最优载重量
Type r; //剩余集装箱重量
};
template<typename Type>
void Loading<Type>::Backtrack(int i) //搜索第i层结点
{
if(i>n) //到达叶结点
{
if(cw>bestw)
bestw=cw;
return;
}
r-=w[i]; //剩余集装箱重量
if(cw+w[i]<=c) //进入左子树，x[i]=1
{
cw+=w[i];
Backtrack(i+1); //继续搜索下一层
cw-=w[i]; //退出左子树
}
if(cw+r>bestw) //上界函数
//进入右子树，x[i]=0
Backtrack(i+1);
r+=w[i];
}
4、构造最优解
为构造最优解，需在算法中记录与当前最优值相应的当前最优解。
在类Loading中增加两个私有数据成员：
int* x：用于记录从根至当前结点的路径；
int* bestx：记录当前最优解。
算法搜索到叶结点处，就修正bestx的值。
public class Loading {
// 船最大装载问题
private int n;// 集装箱数
private int[] x;// 当前解
private int[] bestx;// 当前最优解
private int[] w;// 集装箱重量数组
private int c;// 第一艘船的载重量
private int cw;// 当前载重量
private int bestw;// 当前最优载重量
private int r;// 剩余集装箱重量
void backTrack(int i)// 搜索第i层结点
{
if (i > n) {
// 到达叶结点
if (cw > bestw) {
for (int j = 1; j <= n; j++) {
bestx[j] = x[j];
}
bestw = cw;
}
return;
}
r -= w[i];
// 剩余集装箱重量
if (cw + w[i] <= c) {
// 进入左子树
x[i] = 1;
// 装第i个集装箱
cw += w[i];
backTrack(i + 1);
// 进入下一层
cw -= w[i];
// 退出左子树
}
if (cw + r > bestw) {
// 进入右子树
x[i] = 0;
// 不装第i个集装箱
backTrack(i + 1);
}
r += w[i];
}
public Loading(int[] w, int c, int n, int[] bestx) {
this.w = w;
this.c = c;
this.n = n;
this.bestx = bestx;
this.bestw = 0;
this.cw = 0;
for (int i = 1; i <= n; i++) {
this.r += w[i];
}
this.x = new int[n + 1];
}// 构造器
public static void main(String[] args) {
int n = 5;
int c = 10;
int w[] = {0, 7, 2, 6, 5, 4};// 下标从1开始
int bestx[] = new int[n + 1];
Loading test = new Loading(w, c, n, bestx);
test.backTrack(1);
for (int i = 1; i <= n; i++) {
System.out.print(bestx[i] + " ");
}
System.out.println();
System.out.println(test.bestw);
return;
}
}
由于bestx可能被更新O(2n)次，故算法的时间复杂性为O(n2^n)。
5、迭代回溯(填空即可)
由于数组x记录了解空间树中从根到当前扩展结点的路径，利用这些信息，可将上述回溯法表示成非递归的形式。
n=3, c1=c2=50，且w=[10,40,40]
//迭代回溯法，返回最优载重量
template<typename Type>
Type MaxLoading(Type w[],Type c,int n,int bestx[])
{
//初始化根结点
int i=1;
int *x=new int[n+1];
Type bestw=0;
Type cw=0;
Type r=0;
for(int j=1;j<=n;j++)
r+=w[j];
while(true) //搜索子树
{
while(i<=n&&cw+w[i]<=c) //进入左子树，条件为真，则一直往左搜索
{
r-=w[i];
cw+=w[i];
x[i]=1;
i++;
}
if(i>n) //到达叶结点
{
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestw=cw;
}
else //进入右子树
{
r-=w[i];
x[i]=0;
i++;
}
while(cw+r<=bestw) //剪枝回溯
{
i--;
while(i>0&&!x[i]) //从右子树返回
{
r+=w[i];
i--;
}
if(i==0) //如返回到根，则结束
{
delete[] x;
return bestw;
}
//进入右子树
x[i]=0;
cw-=w[i];
i++;
}
}
}
算法的计算时间为O(2^n)。
5.3 n皇后问题(重点,三个函数都要掌握)
1、问题描述
在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
2、算法设计
解向量：(x1,x2,…,xn)
用n元组x[1:n]表示n后问题的解，其中x[i]表示皇后i放在棋盘的第i行的第x[i]列。
显约束：xi=1,2,…,n
隐约束：
不同列：xi≠xj
不处于同一正反对角线：|i-j|≠|xi-xj|
回溯法解n后问题时，用完全n叉树表示解空间，用可行性约束Place()剪去不满足行、列和斜线约束的子树。
Backtrack(i)搜索解空间中第i层子树。
sum记录当前已找到的可行方案数。
3、四皇后问题
问题描述
在4 x 4棋盘上放上4个皇后，使皇后彼此不受攻击。不受攻击的条件是彼此不在同行（列）、斜线上。求出全部的放法。
解表示
解向量： 4元向量X=(x1,x2,x3,x4)， xi 表示皇后i放在i行上的列号，如(3,1,2,4)
解空间：｛(x1,x2,x3,x4)｜xi∈S，i=1~4｝S={1,2,3,4}
可行性约束函数
显约束： xi∈S，i=1~4
隐约束(i ≠ j)：xi ≠ xj (不在同一列)
? |i－xi|≠|j－xj| (不在同一斜线)
四皇后问题的解空间树是一棵完全4叉树，树的根结点表示搜索的初始状态，从根结点到第2层结点对应皇后1在棋盘中第1行的可能摆放位置，从第2层结点到第3层结点对应皇后2在棋盘中第2行的可能摆放位置，依此类推。
4、算法实现
public class nQueen {
//n皇后问题
private int n;//皇后个数
private int[] x;//当前解
private long sum;//当前已找到可行方案数
public nQueen(int n){
this.n = n;
this.sum = 0;
this.x = new int[n+1];
for (int i = 0; i <=n ; i++) {
x[i]=0;
}
this.backTrack(1);
}
/**
* 放置在第k行
*
* @param k
* @return 是否可行
*/
private boolean place(int k) {
for (int i = 1; i < k; i++) {
if (Math.abs(k - i) == Math.abs(x[k] - x[i]) || x[i] == x[k]) {
//
return false;
}
}
return true;
}
/**
* 递归回溯
* @param t
*/
public void backTrack(int t) {
if (t > n)
sum++;
else
for (int i = 1; i <= n; i++) {//[1:n]列
x[t] = i;//放在第i列
if (place(t))
backTrack(t + 1);
}
}
}
/**
* 非递归回溯
*
* @param t
*/
public void backTrack_o(int t) {
x[1] = 0;
int k = 1;
while (k > 0) {
x[k] += 1; //第k行的放到下一列
//x[k]不能放置，则放到下一列，直到可放置
while ((x[k] <= n) && !place(k))
x[k] += 1;
if (x[k] <= n) //放在n列范围内
if (k == n) //已放n行
sum++;
else //不足n行
{
k++; //放下一行
x[k] = 0; //下一行又从第0列的下列开始试放
}
else //第k行无法放置，则重新放置上一行（放到下一列）
k--;
}
}
5.4 0-1背包问题(重点)
1、算法描述
解空间：子集树
0-1背包问题是子集选取问题，其解空间可用子集树表示。
可行性约束函数： ∑ i = 1 n w i x i ≤ c 1 \sum_{i=1}^n w_ix_i \le c_1 ∑i=1n?wi?xi?≤c1?
上界约束：当右子树中有可能包含最优解时才进入右子树搜索，否则剪去右子树。
设r是当前剩余物品价值总和，cp是当前价值，bestp是当前最优价值，当cp+r≤bestp时，剪去右子树。
计算右子树中解的上界更好的方法是将剩余的物品依其单位重量价值排序，然后依次装入物品，直到装不下时，再装入该物品一部分而装满背包，由此得到的价值是右子树中解的上界。——将背包问题作为0-1背包问题的上界
2、算法实现
template<typename Typew,typename Typep>
class Knap
{
friend Typep Knapsack<>(Typep *,Typew *,Typew,int);
//<>指明友员函数为模板函数
private:
Typep Bound(int i); //计算上界
void Backtrack(int i);
Typew c; //背包容量
int n; //物品数
Typew *w; //物品重量数组
Typep *p; //物品价值数组
Typew cw; //当前重量
Typep cp; //当前价值
Typep bestp; //当前最优价值
};
template<typename Typew,typename Typep>
void Knap<Typew,Typep>::Backtrack(int i) //回溯
{
if(i>n)
{
bestp=cp;
return;
}
if(cw+w[i]<=c) //进入左子树
{
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)>bestp) //进入右子树
Backtrack(i+1);
}
template<typename Typew,typename Typep>
Typep Knap<Typew,Typep>::Bound(int i) //计算上界
{
Typew cleft=c-cw; //剩余的背包容量
Typep b=cp; //b为当前价值
while(i<=n&&w[i]<=cleft) //依次装入单位重量价值高的整个物品
{
cleft-=w[i];
b+=p[i];
i++;
}
if(i<=n) //装入物品的一部分
b+=p[i]*cleft/w[i];
return b; //返回上界
}
class Object //物品类
{
friend int Knapsack(int *,int *,int,int);
public:
int operator <(Object a) const
{
return (d>a.d);
}
int ID; //物品编号
float d; //单位重量价值
};
template<typename Typew,typename Typep>
Typep Knapsack(Typep p[],Typew w[],Typew c,int n)
{
Typew W=0; //总重量
Typep P=0; //总价值
Object* Q=new Object[n]; //创建物品数组，下标从0开始
for(int i=1;i<=n;i++) //初始物品数组数据
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
}
if(W<=c) //能装入所有物品
return P;
QuickSort(Q,0,n-1); //依物品单位重量价值非增排序
Knap<Typew,Typep> K;
K.p=new Typep[n+1];
K.w=new Typew[n+1];
for(int i=1;i<=n;i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
K.Backtrack(1);
delete[] Q;
delete[] K.w;
delete[] K.p;
return K.bestp;
}
计算上界需要O(n)时间，最坏情况下有 O ( 2 n ) O(2^n) O(2n)个右儿子结点需要计算上界，故算法所需要的时间为 O ( n 2 n ) O(n2^n) O(n2n)
5.5 图的m着色问题
1、问题描述
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。
这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。
2、算法设计
用图的邻接矩阵a表示无向连通图G。
解向量：(x1, x2, … , xn)表示顶点i所着颜色x[i]
可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。
class Color
{
friend int mColoring(int,int,int **);
private:
bool OK(int k); //检查颜色是否可用
void Backtrack(int t);
int n; //图的顶点数
int m; //可用颜色数
int **a; //图的邻接矩阵
int *x; //当前解
long sum; //当前已找到的可m着色方案数
};
bool Color::OK(int k) //检查顶点k颜色是否可用
{
for(int j=1;j<=n;j++){
if((a[k][j]==1)&&(x[j]==x[k])) //有边相连且两顶点颜色相同
return false;
}
return true;
}
void Color::Backtrack(int t)
{
if(t>n)
{
sum++;
for(int i=1;i<=n;i++)
cout<<x[i]<<' ';
cout<<endl;
}
else
for(int i=1;i<=m;i++) //m种颜色
{
x[t]=i; //顶点t使用颜色i
if(OK(t))
Backtrack(t+1);
x[t]=0; //恢复x[t]的初值
}
}
int mColoring(int n,int m,int **a)
{
Color X;
//初始化X
X.n=n;
X.m=m;
X.a=a;
X.sum=0;
int *p=new int[n+1];
for(int i=0;i<=n;i++)
p[i]=0;
X.x=p;
X.Backtrack(1);
delete[] p;
return
}
3、算法效率
时间耗费 O ( n m n ) O(nm^n) O(nmn)
判断下图是否是3可着色
5.6 TSP问题（旅行售货员问题）【一级重点】
1、算法描述
已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路
解空间：排列树
开始时x=[1,2,…,n]，则相应的排列树由x[1:n]的所有排列构成。
2、递归算法
当i=n时，当前扩展结点是排列树的叶结点的父结点，此时检查图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边，如果两条边都存在，则找到一条回路。再判断此回路的费用是否优于当前最优回路的费用，是则更新当前最优值和最优解。
当i<n时，当前扩展结点位于排列树的第i-1层。图G中存在从顶点x[i-1]到x[i]的边时，检查x[1:i]的费用是否小于当前最优值，是则进入排列树的第i层，否则剪去相应子树。
3、算法实现
public class TSP {
/**
* 已给一个n个点的[完全图])，每条边都有一个长度，
* 求总长度最短的经过每个顶点正好一次的封闭回路
*/
private int n;//图的顶点数
private int[] x;//当前解
private int[] bestx;//当前最优解
private int[][] a;//邻接矩阵
private int cc;//当前费用
private int bestc;//当前最优值
private static final int NO_EDGE = Integer.MAX_VALUE;//无边标记
public TSP(int[][] a, int[] v, int n) {
this.a = a;
this.n = n;
this.bestx = v;
this.bestc=NO_EDGE;
this.cc = 0;
this.backTrack(2);
}
public void backTrack(int i) {
if (i == n) {
//当i=n时，当前扩展结点是排列树的叶结点的父结点，此时检查图G是否存在一条从
// 顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边，如果两条边都存在，
// 则找到一条回路。再判断此回路的费用是否优于当前最优回路的费用，是则更新当前最优值和最优解。
if (a[x[n - 1]][x[n]] != NO_EDGE && a[x[n]][1] != NO_EDGE &&
(cc + a[x[n - 1]][x[n]] + a[x[n]][1] < bestc || bestc == NO_EDGE)) {
for (int j = 1; j <= n; j++) {
bestx[j] = x[j];
}
bestc = cc + a[x[n - 1]][x[n]] + a[x[n]][1];
}
} else {
//当i<n时，当前扩展结点位于排列树的第i-1层。图G中存在从顶点x[i-1]到x[i]的边时，
// 检查x[1:i]的费用是否小于当前最优值，是则进入排列树的第i层，否则剪去相应子树。
for (int j = i; j <= n; j++) {
if (a[x[i - 1]][x[j]] != NO_EDGE && (cc + a[x[i - 1]][x[j]] < bestc || bestc == NO_EDGE)) {
swap(x[i], x[j]);
cc += a[x[i - 1]][x[i]];
backTrack(i + 1);
cc -= a[x[i - 1]][x[i]];
swap(x[i], x[j]);
}
}
}
}
private void swap(int x, int y) {
int temp = x;
x = y;
y = temp;
}
}
4、算法效率
算法backtrack在最坏情况下可能需要更新当前最优解O((n-1)!)次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为O(n!)。