ACM第5章回溯法

1、第5章 回溯法1第5章 回溯法n回溯法的算法框架p回溯法的基本思想p递归回溯和迭代回溯的算法分析p问题的解空间概念n装载问题n批处理作业调度n0-1背包问题n回溯法的效率分析方法2第5章 回溯法3回溯法概述回溯法概述n 有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。n 回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。第5章 回溯法4回溯法概述回溯法概述n 回溯法在包含问题的所有解的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断

2、该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。第5章 回溯法5回溯法概述回溯法概述n 回溯法在用来求解问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索遍才结束。n 回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。n 这种以深度优先方式系统搜索问题解的算法称为回溯法，它适合用于求解组合数较大的问题。第5章 回溯法回溯法的算法框架回溯法的算法框架n问题的解空间概念问题的解空间概念n回溯法的基本思想回溯法的基本思想n递归回溯的算法分析递归回溯的算法分析n迭代回溯的算法分析迭代回溯的算法分

3、析6第5章 回溯法7问题的解空间问题的解空间n 问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。n 显约束：对分量xi的取值限定。n 隐约束：为满足问题的解而对不同分量之间施加的约束。n 解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。第5章 回溯法问题的解空间问题的解空间n问题的解空间应至少包含问题的一个（最优）解。p例如，对于n种可选择物品的0-1背包问题，其解空间由长度为n的0-1向量组成。 当n=3时，其解空

4、间为： (0,0,0), (0,0,1), (0,1,0), (1,0,0), (0,1,1), (1,1,0), (1,1,0), (1,1,1),8第5章 回溯法9问题的解空间问题的解空间n=3时的时的0-1背包问题用完全二叉树表示的解空间背包问题用完全二叉树表示的解空间第5章 回溯法10生成问题状态的基本方法生成问题状态的基本方法n 扩展结点扩展结点: :一个正在产生儿子的结点称为扩展结点n 活结点活结点: :一个自身已生成但其儿子还没有全部生成的节点称做活结点n 死结点死结点: :一个所有儿子已经产生的结点称做死结点第5章 回溯法11生成问题状态的基本方法生成问题状态的基本方法n 深度

5、优先的问题状态生成法：深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）n 宽度优先的问题状态生成法：宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点第5章 回溯法生成问题状态的基本方法生成问题状态的基本方法n 回溯法：回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。n 具有限界函数的深度优先生成法

6、称为回溯法具有限界函数的深度优先生成法称为回溯法p用约束函数在扩展结点处剪去不满足约束的子树；和用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。p采用剪枝函数，可避免无效搜索，提高回溯法的搜索效率。 第5章 回溯法0-1背包问题示例背包问题示例nn=3,w=16,15,15,p=45,25,25,c=3013可行解：(1,0,0),(0,1,1,),(0,0,1),(0,0,0)第5章 回溯法0-1背包问题示例背包问题示例14第5章 回溯法旅行售货员问题旅行售货员问题n问题：p某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选择一条从驻地出发，经过每个城市一遍，

7、最后回到驻地的路线，使总的路程（或旅费）最小。15第5章 回溯法旅行售货员问题旅行售货员问题16596625n) output(x);/到叶子结点，记录或输出可行解x else/f(n,t)和g(n,t)分别表示在当前扩结点处未搜索过的子树的起始编号和终止编号for (int i=f(n,t);i0) if (f(n,t)=g(n,t) /f(n,t)和g(n,t)分别表示在当前扩结点处未搜索过的子树的起始编号和终止编号 for (int i=f(n,t);in) output(x);/控制递归深度，即解空间的高度，tn时已搜索到叶子结点 else for (int i=0;in) outpu

8、t(x);/已经搜索到叶子结点，进行记录或输出 else for (int i=t;ic1时，以结点Z为根的子树中所有结点不满足约束条件3311cxwniii第5章 回溯法装载问题装载问题34public class Loading static int n;/集装箱数 static int w;/集装箱重量数组 static int c;/第一艘轮船的载重量 static int cw;/当前载重量 static int bestw;/当前最优载重量public static int maxLoading(intww,int cc,intxx)/初始化类数据成员 n=ww.length-1;

9、 w=ww; c=cc; bestw=0; /计算最优装载重量 backtrack(1); return bestw; 第5章 回溯法装载问题装载问题35public static void backtrack(int i) /搜索第i层结点 if(in)/到达叶结点，得到可行解 if(cwbestw)/判断此解是否更优 bestw=cw;/更新最优解 return; /没有到达叶子结点，搜索子树，内部结点 if(cw+wi=c)/搜索左子树，即xi=1cw+=wi; backtrack(i+1);/进一步搜索子树 cw-=wi;/回溯 backtrack(i+1);/搜索右子树，即xi=0，

10、不选，直接搜索其子树 可行性约束函数第5章 回溯法装载问题装载问题n算法复杂度p算法backtrack动态地生成问题的解空间树。在每个结点处花费O(1)时间。子集树中结点个数为O(2n)，故backtrack所需的计算时间为O(2n)。p另外，backtrack还需要额外的O(n)栈空间。36第5章 回溯法装载问题（上界函数）装载问题（上界函数）n设Z是解空间树第i层上的当前扩展结点，CW是当前载重量，bestw是当前最优装载重量，r剩余集装箱重量，即n定义上界函数为cw+r。在以Z为根的子树中任一结点所相应的载重量均不超过cw+r。因此，当cw+rbestw时，可将Z的右子树剪去。37nij

11、jwr1第5章 回溯法装载问题（上界函数）装载问题（上界函数）38public class Loading /类数据成员 static int n;/集装箱数 static int w;/集装箱重量数组 static int c;/第一艘轮船的载重量 static int cw;/当前载重量 static int bestw;/当前最优载重量 staticintr;/剩余集装箱重量剩余集装箱重量/初始化初始化rfor(inti=1;in)/到达叶结点，得到可行解 if(cwbestw)/判断此解是否更优 bestw=cw;/更新最优解 return; /没有到达叶子结点，搜索子树，内部结点 r

12、-=wi; if(cw+wibestw) /上界函数上界函数 backtrack(i+1);/搜索右子树，即xi=0， r+=wi; 第5章 回溯法装载问题（上界函数）装载问题（上界函数）n在改进算法中，引入类Loading的一个私有变量 r，用于计算上界函数，引入上界函数后，在达到一个叶结点时就不必再检查该叶结点是否优 于当前最优解。 n 因为上界函数使算法搜索到的每个叶结点都是 迄今为止找到的最优解，时间复杂性没有变化O(2n)，但在平均情况下改进后的算法检查的结点数较少。 40第5章 回溯法装载问题（构造最优解）装载问题（构造最优解）n记录与当前最优值bestw相应的当前最优解。n在Lo

13、ading中增加两个私有数据成员x和bestx。nx用于记录从根到当前结点的路径nbestx记录当前最优解，算法搜索到达一个叶节点处，就修正bestx的值。41第5章 回溯法装载问题（构造最优解）装载问题（构造最优解）42public class Loading /类数据成员 static int n;/集装箱数 static int w;/集装箱重量数组 static int c;/第一艘轮船的载重量 static int cw;/当前载重量 static int bestw;/当前最优载重量 static int r;/剩余集装箱重量 staticintx;/当前解当前解staticint

14、bestx;/当前最优解当前最优解第5章 回溯法装载问题（构造最优解）装载问题（构造最优解）43public static int maxLoading(intww,int cc,intxx) n=ww.length-1; w=ww; c=cc; bestw=0; x=new int n+1; bestx=xx; for(int i=1;in)/到达叶结点 if(cwbestw) for(int j=1;j=n;j+) bestxj=xj;/当前最优解 bestw=cw; return; r-=wi; if(cw+wibestw)/搜索右子树 xi=0; backtrack(i+1); r+=

15、wi; 第5章 回溯法装载问题（迭代回溯）装载问题（迭代回溯）n数组x记录了解空间树中从根到当前扩展结点的路径，这些信息包含了回溯法在回溯时的所需信息。n因此利用数组x所含的信息，可将递归回溯表示成非递归形式。45第5章 回溯法装载问题（迭代回溯）装载问题（迭代回溯）46 while(true)/搜索子树 while(i=n &cw+win)/到达叶结点 for (int j=1;j=n;j+) bestxj=xj; bestw=cw; 第5章 回溯法装载问题（迭代回溯）装载问题（迭代回溯）47 else/进入右子树 r-=wi; xi=0; i+; while (cw+r0 &

16、; !xi) r+=wi; i-; /从右子树返回 if (i=0) delete x; return bestw; xi=0; cw-=wi; i+; 第5章 回溯法装载问题（迭代回溯）装载问题（迭代回溯）n算法maxLoading所需的计算时间仍为O(2n)。48第5章 回溯法批处理作业调度批处理作业调度n问题：p给定n个作业的集合J1,J2,Jn。每个作业Ji都有两项任务要分别在2台机器上完成。p每个作业必须先由机器1处理，然后由机器2处理。p作业Ji需要机器j的处理时间为tji，其中i=1,2,.,n; j=1,2。p对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所

17、有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。49niiFf12第5章 回溯法50jittji机器1机器2作业121作业231作业323这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。l批处理作业调度问题要求对于给定的批处理作业调度问题要求对于给定的n n个作业，制个作业，制定最佳作业调度方案，使其完成时间和达到最小。定最佳作业调度方案，使其完成时间和达到最小。例例: : n=3n=3批处理作业调度批处理作业调

18、度第5章 回溯法批处理作业调度批处理作业调度n批处理作业调度的解空间树（排列树）51第5章 回溯法批处理作业调度批处理作业调度52public classFlowShop static int n, / 作业数 f1, / 机器1完成处理时间 f, / 完成时间和 bestf; / 当前最优值 static int m; / 各作业所需的处理时间 static int x; / 当前作业调度 static int bestx; / 当前最优作业调度 static int f2; / 机器2完成处理时间第5章 回溯法批处理作业调度批处理作业调度53private static void back

19、track(int i) if(i n) /已搜索到叶子结点，最后层次，已得到一个新的调度方案 for (int j = 1; j = n; j+) /记录 根到叶子结点的路径bestxj = xj;/当前最优路径 bestf = f; /当前最优解 else/i=n，没有到叶子结点 for (int j = i; j f1)?f2i-1:f1)+mxj2; /第i个作业在机器2上的完成时间 f+=f2i; if (f bestf) /剪枝函数，有没有必要进一步搜索，有没有可能得到最优解 MyMath.swap(x,i,j); backtrack(i+1); MyMath.swap(x,i,j

20、); f1-=mxj1; f-=f2i; 第5章 回溯法批处理作业调度批处理作业调度n算法效率p算法backtrack在每个结点处花费O(1)时间，故在最坏情况下，整个算法的计算时间复杂性为为O(n!)。54第5章 回溯法n 0-1背包问题是子集选取问题。一般情况下，0-1背包问题是NP难的。n 0-1背包问题的解空间可用子集树表示。n 在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树中有可能包含最优解时才进入右子树搜索。否则将右子树剪去。n 设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。计算右子树上界的方法是将剩余物品依其单位重量价值排序

21、，然后依次装入物品，直至装不下去时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界。55第5章 回溯法n 单位重量价值3, 2, 3.5, 4n 最优值不超过22，x=1, 0.2, 1, 1。56第5章 回溯法n解空间：子集树n可行性约束函数：n上界函数：p为了计算上界，可先将物品依其单位重量价值从大到小排序，此后只要按顺序考察各物品即可。p在实现时，由Bound计算当前结点处的上界。类Knap的数据成员记录解空间树中的结点信息，以减少参数传递及递归调用所需的栈空间。在解空间树的当前扩展结点处，仅当要进入右子树时才计算上界与其父节点的上界Bound，以判断是否可将右子树剪去

22、。进入左子树时不需要计算上界，因为其上界与其父结点的上界相同。5711cxwniii第5章 回溯法58l Bound计算当前结点处的上界private static double bound(int i) / 计算上界 double cleft = c - cw; / 剩余容量 double bound = cp; / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; bound += pi; i+; / 装满背包 if (i n)/到达叶节点flag=bestpcp;if(flag) bestp=cp;for(i=1;i

23、=n;i+)bestxIDi=xIDi;return;if(cw+wibestp)/进入右子树xIDi=0;Backtrack(i+1);第5章 回溯法n 在记录最优解时需要注意一个问题。因为回溯的顺序是按照物品单位价值从高到低的顺序进行的，而输出的最优解则需要按照原顺序输出。所以在回溯中记录路径时，需注意记录的是原来次序下的路径，而不是排序后的路径。在这里我们在排序之前已经定义好一个类Q。类中的数据成员ID用来记录物品原来的位置。则排序后，物品原来的位置记录仍能被找到。则搜索到某个结点时，则xIDi=1,否则xIDi=0.61第5章 回溯法n 算法效率p计算上界需要O(n)时间，在最坏情况下

24、有O(2n)个右儿子结点需要计算上界，故解0-1背包问题的回溯算法backtrack所需的计算时间为O(n2n)。62第5章 回溯法63算法时间复杂度优点缺点改进方法动态规划O(minnc, 2n ）可求得最优决策序列速度较慢建立动态规划递归方程回溯法O(n 2n）能够获得最优解时间复杂度较高判断右子树时，按效率密度vi/wi对剩余对象排序分枝-限界法O(2n )速度较快，易求解占用的内存较大，效率不高最大收益或最小消耗分枝-限界法，FIFO法贪心算法O(nlogn）可以达到局部最优解，用时少不能考虑到整体最优解，程序可读性低于动态规划对范围广的问题可以产生接近的最优解第5章 回溯法旅行售货员

25、问题的提法是旅行售货员问题的提法是：某售货员要：某售货员要到若干城市去推销商品，已知各城市之到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或总旅费到驻地的路线，使总的路程（或总旅费）最小。）最小。第5章 回溯法设设G=（V，E）是一个带权图。图中各边的费用是一个带权图。图中各边的费用（权）为一正数。图中的一条周游路线是包括（权）为一正数。图中的一条周游路线是包括V中的每个顶点在内的一条回路。一条周游路线的中的每个顶点在内的一条回路。一条周游路线的

26、费用是这条路线上所有边的费用之和。费用是这条路线上所有边的费用之和。所谓旅行售货员问题就是要在图所谓旅行售货员问题就是要在图G中找出一条有中找出一条有最小费用的周游路线。最小费用的周游路线。14323010204561，2，4，3，11，3，2，4，11，4，3，2，1第5章 回溯法1432301020456ABCDEFGHIJKLMNOPQ1234344443332222旅行售货员问题的解空间树旅行售货员问题的解空间树第5章 回溯法67解空间：排列树private static void backtrack(int i) if (i = n) if(axn - 1xn Float.MAX_V

27、ALUE & axn1 Float.MAX_VALUE & (bestc = Float.MAX_VALUE | cc+axn - 1xn+axn1bestc) for (int j = 1; j = n; j+) bestxj = xj; bestc = cc+axn - 1xn+axn1; else for(int j = i; j = n; j+) / 是否可进入xj子树? if(axi - 1xj Float.MAX_VALUE & (bestc = Float.MAX_VALUE | cc+axi - 1xjhalf)|(t*(t-1)/2-counthalf

28、) /若+号统计 超过半数，或-号超过半数 return; if (tn) sum+; /符号填充完毕 elsefor (int i=0;i2;i+) p1t=i; /第一行第t个符号 count+=i; /“+”号统计 for (int j=2;j=2时，可以运算出下面行的某些符号 pjt-j+1=pj-1t-j+1pj-1t-j+2; /通过异或运算下行符号 count+=pjt-j+1; backtrack(t+1); /在第一行增加下一个符号 for (int j=2;j=t;j+) count-=pjt-j+1; count-=i; + + - + - + + - - - - +-

29、+ + + - - + + - - + - - - +复杂度分析复杂度分析计算可行性约束需要O(n)时间，在最坏情况下有 O(2n)个结点需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为 O(n2n)。第5章 回溯法n后问题在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1 2 3 4 5 6 7 812345678QQQQQQQQ第5章 回溯法算法设计：对于n后问题，用n元组x1:n表示它的解。x1:n表示皇后i放在棋

30、盘的第i行的第xi列。由于不允许将任何2个皇后放在同一列上，所以解向量中的诸xi互不相同。例如：x6 x4 x7 x1 x8 x2 x5 x3QQQQQQQQ123456781，2，3，4，5，6，7，8第5章 回溯法任何2个皇后不能放在同一斜线上？它是问题的一个隐约束条件。我们可以把它化成显约束的形式。现在进一步讨论将此问题的隐约束化成显约束的过程。第5章 回溯法如果将n*n格的棋盘看作是一个二维方阵，行号从上到下，列号从左到右依次为1，2n则：从左上角到右下角的主对角线及其平行线上（斜率为-1的每一条斜线上），元素的2个下标值的差（行号-列号）值相等。同理，斜率为+1的每一条斜线上，元素的

31、2个下标值的和（行号+列号）值相等。 a00 a01 a0n-1 a10 a11 a1n-1 . am-1 0 am-1 1 am-1 n-1 A= 若2个皇后位置为（i,j)和(k,l),且（i-j)=(k-l),或（i+j)=(k+l),则这2个皇后处于同一斜线上。第5章 回溯法那么，（i-j)=(k-l),（i+j)=(k+l)这两个方程可以等价与（i-k)=(j-l)和（i-k)=(l-j),则只要abs（i-k)=abs(j-l)成立，表明这2个皇后位于同一条斜线上。于是，问题的隐约束化成了显约束。解向量：(x1, x2, , xn)显约束：xi=1,2, ,n隐约束： 1)不同列：

32、xixj 2)不处于同一正、反对角线：|i-j|xi-xj|第5章 回溯法78 private static boolean place (int k) for (int j=1;jn) sum+; elsefor (int i=1;in)/到达叶结点for(intj=1;j=n;j+)bestxj=xj;bestn=cn;return;/检查顶点i与当前团的连接intOK=1;for(intj=1;jbestn)/进入右子树xi=0;Backtrack(i+1);复杂度分析最大团问题的回溯算法backtrack所需的计算时间显然为O(n2n)。第5章 回溯法1、求出n=4时的所有解（用坐标序

33、列（i，j）表示，其中1=i、jn)/到达叶结点for(intj=1;j=n;j+)bestxj=xj;bestn=cn;return;/检查顶点i与当前团的连接booleanok=true;for(intj=1;jbestn)/进入右子树xi=0;backtrack(i+1);复杂度分析复杂度分析最大团问题的回溯算法backtrack所需的计算时间显然为O(n2n)。12453第5章 回溯法91选择合适的搜索顺序，可以使得上界函数更有效的发挥作用。例如在搜索之前可以将顶点按度从小到大排序。这在某种意义上相当于给回溯法加入了启发性。定义Si=vi,vi+1,.,vn，依次求出Sn,Sn-1,.

34、,S1的解。从而得到一个更精确的上界函数，若cn+Sin)sum+;else for(inti=1;i=m;i+)xt=i;if(ok(t)backtrack(t+1);privatestaticbooleanok(intk)/检查颜色可用性for(intj=1;jn) sum+; for (int i=1; i=n; i+) cout xi ; cout endl; else for (int i=1;i=m;i+) xt=i; if (Ok(t) Backtrack(t+1); bool Color:Ok(int k)/ 检查颜色可用性检查颜色可用性 for (int j=1;j=n;j+

35、) if (akj=1)&(xj=xk) return false; return true;第5章 回溯法复杂度分析复杂度分析 图图m可着色问题的解空间树中内结点个数可着色问题的解空间树中内结点个数是是对于每一个内结点，在最坏情况下，用对于每一个内结点，在最坏情况下，用ok检查检查当前扩展结点的每一个儿子所相应的颜色可用当前扩展结点的每一个儿子所相应的颜色可用性需耗时性需耗时O(mn)。因此，回溯法总的时间耗费。因此，回溯法总的时间耗费是是10niim)() 1/() 1()(10nnniinmOmmnmmnm第5章 回溯法100给定n个大小不等的圆c1,c2,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且所给的3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图所示。其最小长度为242第5章 回溯法101privatestaticfloatc