5.算法设计与分析__回溯算法

回溯法是一种组织搜索的一般技术，有“通用的解题法”之称，用它可以系统的搜索一个问题的所有解或任一解。
有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。
可以系统地搜索一个问题的所有解或任意解，既有系统性又有跳跃性。
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。
这种以深度优先的方式系统地搜索问题的解的方法称为回溯法。

1 回溯算法的理论基础

1.1 问题的解空间

应用回溯法求解时，需要明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。
例如，对于有n种可选择物品的0—1背包问题，其解空间由长度为n的0—1向量组成，该解空间包含了对变量的所有可能的0—1赋值

1.2 回溯法的基本思想

在生成解空间树时，定义以下几个相关概念：
活结点：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。
扩展结点：当前正在生成其儿子结点的活结点叫扩展结点（正扩展的结点）。
死结点：不再进一步扩展或者其儿子结点已全部生成的结点就是死结点。

在确定了解空间的组织结构后，回溯从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。
这个开始结点成为一个活结点，同时成为当前的扩展结点。在当前的扩展结点，搜索向深度方向进入一个新的结点。这个新结点成为一个新的活结点，并成为当前的扩展结点。
若在当前扩展结点处不能再向深度方向移动，则当前的扩展结点成为死结点，即该活结点成为死结点。此时回溯到最近的一个活结点处，并使得这个活结点成为当前的扩展结点。
回溯法以这样的方式递归搜索整个解空间（树），直至满足中止条件。


设G=(V, E)是一个带权图，其每一条边(u, v)∈E的费用（权）为正数w(u, v)。目的是要找出G的一条经过每个顶点一次且仅经过一次的回路，即汉密尔顿（Hamilton）回路v1，v2 ，…，vn ，使回路的总权值最小：

回溯法找最小费用周游路线的主要过程

在回溯法搜索解空间树时，通常采用两种策略（剪枝函数）避免无效搜索以提高回溯法的搜索效率：
用约束函数在扩展结点处减去不满足约束条件的子树；
用限界函数减去不能得到最优解的子树。
解0—1背包问题的回溯法用剪枝函数剪去导致不可行解的子树。
解旅行商问题的回溯算法中，如果从根结点到当前扩展结点的部分周游路线的费用已超过当前找到的最好周游路线费用，则以该结点为根的子树中不包括最优解，就可以剪枝。

1.3 子集树与排列树

有时问题是要从一个集合的所有子集中搜索一个集合，作为问题的解。或者从一个集合的排列中搜索一个排列，作为问题的解。
回溯算法可以很方便地遍历一个集合的所有子集或者所有排列。
当问题是要计算n个元素的子集，以便达到某种优化目标时，可以把这个解空间组织成一棵子集树。
例如，n个物品的0-1背包问题相应的解空间树就是一棵子集树。
这类子集树通常有2n个叶结点，结点总数为2n +1-1。
遍历子集树的任何算法，其计算时间复杂度都是Ω(2n)。

伪代码

//形参t为树的深度，根为1
void backtrack (int t)
{
　　if (t>n) update(x);
　　else
　　　　for (int i=0; i<=1; i++)　　//每个结点只有两个子树
　　　　{
　　　　　　x[t]=i;　　　　　　　  //即0/1
　　　　　　if (constraint(t) && bound(t)) backtrack(t+1);
　　　　}
}

约束函数constraint(t)和限界函数bound(t)，称为剪枝函数。
函数update(x)是更新解向量x的。
约束函数constraint(t)，一般可以从问题描述中找到。

当所给的问题是确定n个元素满足某种性质的排列时，可以把这个解空间组织成一棵排列树。
排列树通常有n!个叶子结点。因此遍历排列树时，其计算时间复杂度是Ω(n!) 。
例如，旅行商问题就是一棵排列树。
伪代码

//形参t为树的深度，根为1
void backtrack (int t)
{
　　if (t>n) update(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]);　　　　//恢复状态
　　　　}
}

2 装载问题

给定n个集装箱要装上一艘载重量为c的轮船，其中集装箱i的重量为wi。集装箱装载问题要求确定在不超过轮船载重量的前提下，将尽可能多的集装箱装上轮船。
由于集装箱问题是从n个集装箱里选择一部分集装箱，假设解向量为X(x1, x2, …, xn)，其中xi∈{0, 1}， xi =1表示集装箱i装上轮船， xi =0表示集装箱i不装上轮船。
输入
每组测试数据：第1行有2个整数c和n。C是轮船的载重量（0＜c＜30000），n是集装箱的个数（n≤20）。第2行有n个整数w1, w2, …, wn，分别表示n个集装箱的重量。
输出
对每个测试例，输出两行：第1行是装载到轮船的最大载重量，第2行是集装箱的编号。

该问题的形式化描述为：

在5.4节，最优装载问题中，是要求在装载体积不受限制的情况下，而这里是不超过轮船的载重量。
用回溯法解装载问题时，其解空间是一棵子集树，与0—1背包问题的解空间树相同。

可行性约束函数可剪去不满足约束条件的子树：

令cw(t)表示从根结点到第t层结点为止装入轮船的重量，即部分解(x1, x2 , …, xt)的重量：

当cw(t)>c时，表示该子树中所有结点都不满足约束条件，可将该子树剪去。

算法6.3（1） 装载问题回溯算法的数据结构

算法6.3（2） 装载问题回溯算法的实现

算法6.3（3） 剩余集装箱的重量r初始化

3 0－1背包问题

给定一个物品集合s＝｛1，2，3，…，n｝，物品i的重量是wi，其价值是vi，背包的容量为W，即最大载重量不超过W。在限定的总重量W内，我们如何选择物品，才能使得物品的总价值最大。
输入
第一个数据是背包的容量为c（1≤c≤1500），第二个数据是物品的数量为n（1≤n≤50）。接下来n行是物品i的重量是wi，其价值为vi。所有的数据全部为整数，且保证输入数据中物品的总重量大于背包的容量。
当c＝0时，表示输入数据结束。
输出
对每组测试数据，输出装入背包中物品的最大价值。

令cw(i)表示目前搜索到第i层已经装入背包的物品总重量，即部分解(x1, x2 , …, xi)的重量：

对于左子树， xi =1 ，其约束函数为：

若constraint(i)＞W，则停止搜索左子树，否则继续搜索。
对于右子树，为了提高搜索效率，采用上界函数Bound(i)剪枝。
令cv(i)表示目前到第i层结点已经装入背包的物品价值：

令r(i)表示剩余物品的总价值：

则限界函数Bound(i)为：

假设当前最优值为bestv，若Bound(i)＜bestv，则停止搜索第i层结点及其子树，否则继续搜索。显然r(i)越小， Bound(i)越小，剪掉的分支就越多。
为了构造更小的r(i) ，将物品以单位重量价值比di=vi/wi递减的顺序进行排列：
d1≥d2≥… ≥dn
对于第i层，背包的剩余容量为W-cw(i)，采用贪心算法把剩余的物品放进背包，根据贪心算法理论，此时剩余物品的价值已经是最优的，因为对剩余物品不存在比上述贪心装载方案更优的方案。

算法6.4（1） 0－1背包问题回溯算法的数据结构

对物品以单位重量价值比递减排序的因子是：
bool cmp(Object a, Object b)
{
if(a.d>=b.d) return true;
else return false;
}
物品的单位重量价值比是在输入数据时计算的：
for(int i=0; i<n; i++)
{
scanf("%d%d",&Q[i].w,&Q[i].v);
Q[i].d = 1.0*Q[i].v/Q[i].w;
}
使用C++标准模板库的排序函数sort()排序：
sort(Q, Q+n, cmp);
算法6.4（2） 0－1背包问题回溯算法的实现

//形参i是回溯的深度，从0开始
void backtrack(int i)
{
　　//到达叶子结点时，更新最优值
　　if (i+1>n) {bestv = cv; return;}
　　//进入左子树搜索
　　if (cw+Q[i].w<=c)
　　{
　　　　cw += Q[i].w;
　　　　cv += Q[i].v;
　　　　backtrack(i+1);
　　　　cw -= Q[i].w;
　　　　cv -= Q[i].v;
　　}
　　//进入右子树搜索
　　if (Bound(i+1)>bestv) backtrack(i+1);
}

算法6.4（3） 限界函数Bound()的实现

//形参i是回溯的深度
int Bound(int i)
{
　　int cleft = c-cw;　　　//背包剩余的容量
　　int b = cv;　　　　　　//上界
　　//尽量装满背包
　　while (i<n && Q[i].w<=cleft)
　　{
　　　　cleft -= Q[i].w;
　　　　b += Q[i].v;
　　　　i++;
　　}
　　//剩余的部分空间也装满
　　if (i<n) b += 1.0*cleft*Q[i].v/Q[i].w;
　　return b;
}

4 图的m着色问题

给定无向连通图G=(V, E)和m种不同的颜色，用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中相邻的两个顶点有不同的颜色?
这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。
编程计算：给定图G=(V, E)和m种不同的颜色，找出所有不同的着色法和着色总数。
输入
第一行是顶点的个数n（2≤n≤10），颜色数m（1≤m≤n）。
接下来是顶点之间的相互关系：a b
表示a和b相邻。当a，b同时为0时表示输入结束。
输出
输出所有的着色方案，表示某个顶点涂某种颜色号，每个数字的后面有一个空格。最后一行是着色方案总数。

对m种颜色编号为1，2，…，m，由于每个顶点可从m种颜色中选择一种颜色着色，如果无向连通图G=(V, E)的顶点数为n，则解空间的大小为mn种，解空间是非常庞大的，它是一棵m叉树。
当n＝3，m＝3时的解空间树：

图的m着色问题的约束函数是相邻的两个顶点需要着不同的颜色，但是没有限界函数。
假设无向连通图G=(V, E)的邻接矩阵为a，如果顶点i和j之间有边，则a[i][j]=1，否则a[i][j]=0。
设问题的解向量为X (x1, x2 , …, xm) ，其中xi∈{1, 2, …, m}，表示顶点i所着的颜色是x[i]，即解空间的每个结点都有m个儿子。

算法6.5（1） 图的m着色问题回溯算法的数据结构

算法6.5（2） 图的m着色问题回溯算法的实现

//形参t是回溯的深度，从1开始
void BackTrack(int t )
{
　　int i;
　　//到达叶子结点，获得一个着色方案
　　if( t > n )
　　{
　　　　sum ++ ;
　　　　for(i=1; i<=n ;i++)
　　　　　　printf("%d ",x[i]);
　　　　printf("\n");
　　}
　　else 
　　　　//搜索当前扩展结点的m个孩子
　　　　for(i=1; i<=m; i++ )
　　　　{
　　　　　　x[t] = i;
　　　　　　if( Same(t) )　BackTrack(t+1);
　　　　　　x[t] = 0;
　　　　}
}

算法6.5（3） 检查相邻结点的着色是否一样的约束函数

//形参t是回溯的深度
bool Same(int t)
{
　　int i;
　　for(i=1; i<=n; i++ )
　　　　if( (a[t][i] == 1) && (x[i] == x[t]))
　　　　　　return false;
　　return true;
}

算法BackTrack(int t)中，对每个内部结点，其子结点的一种着色是否可行，需要判断子结点的着色与相邻的n个顶点的着色是否相同，因此共需要耗时O(mn)，而整个解空间树的内部结点数是：

所以算法BackTrack(int t)的时间复杂度是：

5 n皇后问题

6 旅行商问题

7 流水作业调度问题

8 子集和问题

9 ZOJ1145-Dreisam Equations

10 ZOJ1157-A Plug for UNIX

11 ZOJ1166-Anagram Checker

12 ZOJ1213-Lumber Cutting