第5章 回溯算法

1、第五章第五章 回溯算法回溯算法2022年6月26日2理解回溯法的深度优先搜索策略。理解回溯法的深度优先搜索策略。掌握用回溯法解题的算法框架掌握用回溯法解题的算法框架（1）递归回溯）递归回溯（2）迭代回溯）迭代回溯（3）子集树算法框架）子集树算法框架（4）排列树算法框架）排列树算法框架学习要点学习要点2022年6月26日3一、回溯法的算法框架二、装载问题三、n后问题四、0-1背包问题五、最大团问题六、图的m着色问题七、旅行售货员问题2022年6月26日4一、回溯法的算法框架一、回溯法的算法框架二、装载问题三、n后问题四、0-1背包问题五、最大团问题六、图的m着色问题七、旅行售货员问题2022年6

2、月26日5深度优先搜索算法深度优先搜索算法2022年6月26日62022年6月26日7 搜索与回溯是计算机解题中常用的算法，搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，原来的选择是错误的，

3、就退回一步重新选择，继续向前探索，如此反复进行，直至得到解继续向前探索，如此反复进行，直至得到解或证明无解。或证明无解。 2022年6月26日8l迷宫游戏迷宫游戏2022年6月26日9l例：例：迷宫游戏迷宫游戏2022年6月26日10例：N后问题2022年6月26日11l 有许多问题，当需要找出它的解集或者要求回答有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要什么解是满足某些约束条件的最佳解时，往往要使用回溯法。使用回溯法。l 回溯法的基本做法是搜索，或是一种组织得井井回溯法的基本做法是搜索，或是一种组织得井井有条的、能避免不必要搜索的穷举式搜索法。这有条

4、的、能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。种方法适用于解一些组合数相当大的问题。l 回溯法在问题的解空间树中，按深度优先策略，回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。该子树，继续按深度优先策略搜索

5、。2022年6月26日12l 本节介绍回溯法算法框架的有关问题：n一、问题的解空间n二、回溯法的基本思想n三、递归回溯n四、迭代回溯n五、子集树与排列树2022年6月26日13l 问题所有可能的解构成了问题的解空间，解空间也就是进行穷举的搜索空间。l 确定正确的解空间很重要！确定正确的解空间很重要！例如：桌子上有6根火柴棒，要求以这6根火柴棒为边搭建4个等边三角形。(a) 二维搜索空间无解 (b) 三维搜索空间的解错误的解空间将不能搜索到正确答案！错误的解空间将不能搜索到正确答案！2022年6月26日14l 对于任何一个问题，可能解的对于任何一个问题，可能解的表示方式表示方式和它相应的和它相应

6、的解释解释隐含了解空间及其大小。隐含了解空间及其大小。l 例如，对于有例如，对于有n个物品的个物品的0/1背包问题，其可能解的背包问题，其可能解的表示方式可以有以下两种：表示方式可以有以下两种：（1）可能解由一个不等长向量组成，当物品）可能解由一个不等长向量组成，当物品i(1in)装入装入背包时，解向量中包含分量背包时，解向量中包含分量i，否则，解向量中不包含分，否则，解向量中不包含分量量i，当，当n=3时，其解空间是：时，其解空间是： ( ), (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3) （2）可能解由一个等长向量）可能解由一个等长向量x

7、1, x2, , xn组成，其中组成，其中xi=1(1in)表示物品表示物品i装入背包，装入背包，xi=0表示物品表示物品i没有装没有装入背包，当入背包，当n=3时，其解空间是：时，其解空间是： (0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1) 2022年6月26日15问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。显约束：对分量xi的取值限定。隐约束：为满足问题的解而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式

8、约束条件的所有多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。2022年6月26日16l 为了用回溯法求解一个具有为了用回溯法求解一个具有n个输入的问题，一般情况个输入的问题，一般情况下，将其可能解表示为满足某个约束条件的等长向量下，将其可能解表示为满足某个约束条件的等长向量X=(x1, x2, , xn)，其中分量，其中分量xi (1in)的取值范围是某个有的取值范围是某个有限集合限集合Si=ai1, ai2, , airi，所有可能的解向量构成了问题，所有可能的解向量构成了问题的的解空间解空间。 l 问

9、题的解空间一般用问题的解空间一般用解空间树解空间树（Solution Space Trees,也也称状态空间树）的方式组织，树的根结点位于第称状态空间树）的方式组织，树的根结点位于第1层，层，表示搜索的初始状态，第表示搜索的初始状态，第2层的结点表示对解向量的第层的结点表示对解向量的第一个分量做出选择后到达的状态，第一个分量做出选择后到达的状态，第1层到第层到第2层的边上层的边上标出对第一个分量选择的结果，依此类推，从树的根结标出对第一个分量选择的结果，依此类推，从树的根结点到叶子结点的路径就构成了解空间的一个可能解。点到叶子结点的路径就构成了解空间的一个可能解。2022年6月26日17l 对

10、于对于n=3的的0/1背包问题，其解空间树如下图所示，背包问题，其解空间树如下图所示，树中的树中的8个叶子结点分别代表该问题的个叶子结点分别代表该问题的8个可能个可能解。解。对物品对物品1的选择的选择对物品对物品3的选择的选择对物品对物品2的选择的选择11111100000001123457811121415310692022年6月26日18l 问题描述：某售货员问题描述：某售货员要到若干城市去推销要到若干城市去推销商品，已知各城市之商品，已知各城市之间的路程，他要选定间的路程，他要选定一条从驻地出发，经一条从驻地出发，经过每个城市一遍，最过每个城市一遍，最后回到住地的路线，后回到住地的路线，

11、使总的路程最短。使总的路程最短。l 该问题是一个该问题是一个NP完完全问题，全问题， 有有(n-1)!条条可选路线可选路线l 最优解最优解(1,3,2,4,1)，最优值最优值251234206305410ABCDEFGHIJKLMNOPQ12343443423224232022年6月26日19l 回溯法从根结点出发，按照回溯法从根结点出发，按照深度优先深度优先策略搜索（遍策略搜索（遍历）解空间树，搜索满足约束条件的解。历）解空间树，搜索满足约束条件的解。l 初始时，根结点成为一个初始时，根结点成为一个活结点活结点，同时也称为当前，同时也称为当前的的扩展结点扩展结点。在当前扩展结点处，搜索向纵深

12、方向。在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为一个新的活结点，移至一个新结点。这个新结点成为一个新的活结点，并成为当前的扩展结点。如果在当前的扩展结点处并成为当前的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为不能再向纵深方向移动，则当前的扩展结点就成为一个一个死结点死结点（即不再是一个活节点）。此时，应往（即不再是一个活节点）。此时，应往回移动（回溯）至最近的一个活结点处，并使这个回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。活结点成为当前的扩展结点。20死结点死结点扩展结点扩展结点活结点活结点扩展结点扩展结点: :

13、一个正在产生儿子的结点称为扩展结点。一个正在产生儿子的结点称为扩展结点。活结点活结点: :一个自身已生成但其儿子还没有全部生成的节点称做活结一个自身已生成但其儿子还没有全部生成的节点称做活结点。点。死结点死结点: :一个所有儿子已经产生的结点称做死结点。一个所有儿子已经产生的结点称做死结点。2022年6月26日21l 在搜索至树中任一结点时，先判断该结点对应的部在搜索至树中任一结点时，先判断该结点对应的部分解是否满足分解是否满足约束条件约束条件，或者是否超出，或者是否超出限界函数限界函数的的界，也就是判断该结点是否界，也就是判断该结点是否包含包含问题的（最优）解，问题的（最优）解，如果肯定不包

14、含，则跳过对以该结点为根的子树的如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓搜索，即所谓剪枝剪枝（Pruning）；否则，进入以该结；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。点为根的子树，继续按照深度优先策略搜索。l 在搜索过程中，通常采用两种策略避免无效搜索：在搜索过程中，通常采用两种策略避免无效搜索：（1）用）用约束条件约束条件剪去得不到可行解的子树；剪去得不到可行解的子树；（2）用）用限界函数限界函数剪去得不到最优解的子树。剪去得不到最优解的子树。 这两类函数统称为这两类函数统称为剪枝函数剪枝函数（Pruning Function）。2022年6月26日22

15、例如，对于n=3的0/1背包问题，三个物品的重量为16, 15, 15，价值为45, 25, 25，背包容量为30，从其解空间树的根结点开始搜索，搜索过程如下：ACr=C=30，V=0HIw1=16，v1=45Cr=14，V=45B1DCrw2不可行解1JCr45x=(0,1,1)1KCr=14V=45x=(1,0,0)0M 2550不是最优解0NOGVn) output(x); /n表示解空间树的高度； else for (int i=f(n,t);i0) if (f(n,t)=g(n,t) for (int i=f(n,t);in) output(x); else for (int i=0

16、;in) output(x); else for (int i=t;i当前最优载重量bestw11cxwniii不满足不满足约束函数约束函数不满足不满足上界函数上界函数34w= 16, 15, 15, c = 3001603100031163001615151510000000111113131用子集树表示其解空间，用可行性约束函数可剪去不用子集树表示其解空间，用可行性约束函数可剪去不满足条件满足条件 的子树。在子集树的第的子树。在子集树的第j+1层的结点层的结点Z处，用处，用cw记当前的装载重量，即记当前的装载重量，即 cw= ，则当，则当cw c1 时，以结点时，以结点Z为根的子为根的子

17、树中所有结点都不满足约束条件，树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去。因而该子树中的解均为不可行解，故可将该子树剪去。 jiiixw1 niiicxw1135templateclass Loading friend Type MaxLoading(Type,Type,int); private: void Backtrack(int i); int n; /集装箱数集装箱数 Type * w, /集装箱重量数组集装箱重量数组 c, /第一艘轮船的载重量第一艘轮船的载重量 cw, /当前载重量当前载重量 bestw; /当前最优载重量当前最优载重量 ;函数函

18、数MaxLoading负责负责该类成员的初始化，返该类成员的初始化，返回不超过回不超过c的最大子集的最大子集和，但未给出达到这个和，但未给出达到这个最大子集和的相应子集最大子集和的相应子集Backtrack实现回溯搜索，实现回溯搜索，Backtrack(1)实现对整个解空间的实现对整个解空间的回溯搜索，回溯搜索，Backtrack(i)搜索子集树搜索子集树中第中第i层子树。层子树。36templateType MaxLoading( Type w ,Type c, int n ) /返回最优载重量返回最优载重量 Loading x; x. w = w; x. c = c; x. n = n;

19、x. bestw = 0; x. cw = 0; /计算最优载重量计算最优载重量 x.Backtrack( 1 ); return x. bestw; 装载问题装载问题37Backtrack( int i ) /搜索第搜索第i层结点层结点 如果到达叶结点，则判断当前的如果到达叶结点，则判断当前的cw，如果，如果比前面得到的最优解比前面得到的最优解bestw好，则替换原好，则替换原最优解。最优解。 /搜索左子树搜索左子树 如果当前剩余空间可以放下当前物品，也如果当前剩余空间可以放下当前物品，也就是，就是， cw + w i = c，则把当前载重，则把当前载重 cw += w i ，递归访问其左子

20、树，递归访问其左子树，Backtrack( i + 1 )，访问结束，回到调用，访问结束，回到调用点，点， cw - = w i /搜索右子树搜索右子树 Backtrack( i + 1 ); 装载问题装载问题38templatevoid Loading: Backtrack( int i ) /搜索第搜索第i层结点层结点 if ( i n ) /到达叶结点到达叶结点 if( cw bestw ) bestw =cw; return; /搜索子树搜索子树 if( cw + w i = c ) /xi=1 cw += w i ; Backtrack( i + 1 ); cw - = w i ;

21、Backtrack( i + 1 ); /xi=0 0160030016151515100000011i = 1i = 2i = 316i = 41l w= 16, 15, 15, c = 30即使把剩余物品都即使把剩余物品都装里也不会得到比装里也不会得到比当前的最优解更好当前的最优解更好装载问题装载问题右子树永远可行！右子树永远可行！390160030016151515100000011i = 1i = 2i = 316i = 41引入一个引入一个上界函数上界函数，用于剪，用于剪去去不含最优解的子树不含最优解的子树，设，设Z是解空间树第是解空间树第i层上的当前扩层上的当前扩展结点。展结点。c

22、w是当前载重量；是当前载重量；bestw是当前最优载重量；是当前最优载重量；r是剩余集装箱的重量和；是剩余集装箱的重量和；定义上界函数为定义上界函数为cw + r。在以在以Z为根的子树中任一结为根的子树中任一结点所相应的载重量均不超过点所相应的载重量均不超过cw + r。因此，当。因此，当cw + r = bestw 时，可将时，可将Z的右子树剪的右子树剪去。去。 装载问题装载问题40l在改进算法中，引入类在改进算法中，引入类Loading的一个私有变量的一个私有变量r，用于计算上界函数，引入上界函数后，在达到，用于计算上界函数，引入上界函数后，在达到一个叶结点时就不必再检查该叶结点是否优于当

23、一个叶结点时就不必再检查该叶结点是否优于当前最优解。前最优解。l因为上界函数使算法搜索到的每个叶结点都是迄因为上界函数使算法搜索到的每个叶结点都是迄今为止找到的最优解，时间复杂性没有变化，但今为止找到的最优解，时间复杂性没有变化，但在平均情况下改进后的算法检查的结点数较少。在平均情况下改进后的算法检查的结点数较少。 装载问题装载问题41Templateclass Loading friend Type MaxLoading(Type ,Type, int ); private: void Backtrack(int i); int n; /集装箱数集装箱数 Type * w, /集装箱重量数组

24、集装箱重量数组 c, /第一艘轮船的载重量第一艘轮船的载重量 cw, /当前载重量当前载重量 bestw， /当前最优载重量当前最优载重量 ; /剩余集装箱重量剩余集装箱重量 ; 装载问题装载问题42templateType MaxLoading( Type w ,Type c, int n ) /返回最优载重量返回最优载重量 Loading x; x. w = w; x. c = c; x. n = n; x. bestw = 0; x. cw = 0; x. r = 0; for(int i =1;i = n;i +) x. r += wi; /初始时初始时r为全体物品的重量和为全体物品的

25、重量和 /计算最优载重量计算最优载重量 x.Backtrack(1); return x.bestw; 5.2 装载问题装载问题43Backtrack( int i ) /搜索第搜索第i层结点层结点 如果到达叶结点，如果到达叶结点，bestw=cw。 /修改剩余重量修改剩余重量r r = r-wi /搜索左子树搜索左子树 如果当前剩余空间可以放下当前物品也就是，如果当前剩余空间可以放下当前物品也就是， cw + w i = c，则，则把当前载重把当前载重 cw += w i ，递归访问其左子树，递归访问其左子树，Backtrack( i + 1 )，访问结束，回到调用点，访问结束，回到调用点，

26、 cw - = w i 。 /搜索右子树搜索右子树 如果剩余重量加上当前载重大于最优值，递归访问右子树，如果剩余重量加上当前载重大于最优值，递归访问右子树， Backtrack( i + 1 )。 /回到上一层调用点回到上一层调用点 r = r+wi 装载问题装载问题44templatevoid Loading: Backtrack( int i ) /搜索第搜索第i层结点层结点 if ( i n ) /到达叶结点到达叶结点 bestw = cw; return; /搜索子树搜索子树 r - = w i ; if( cw + w i bestw) /xi=0 Backtrack(i+1); r

27、 + = wi; i = 1cw = 0bestw = 0r =46cw = 0bestw = 0r =30i = 2cw = 16bestw = 0r =15i = 3cw = 16bestw = 0r =0i = 4cw = 16bestw = 161000cw = 0bestw = 16r =151cw = 15bestw = 16r =0cw = 0bestw = 16r =301cw = 30bestw = 30cw = 15bestw = 30r =0cw = 0bestw = 30r =15cw = 0bestw = 30r =30cw = 16bestw = 16r =0cw

28、= 16bestw = 16r =15l w= 16, 15, 15, c = 3045Templateclass Loading friend Type MaxLoading(Type ,Type, int , int ); private: void Backtrack(int i); int n; /集装箱数集装箱数 *x, /当前解当前解 *bestx; /当前最优解当前最优解 Type * w, /集装箱重量数组集装箱重量数组 c, /第一艘轮船的载重量第一艘轮船的载重量 cw, /当前载重量当前载重量 bestw， /当前最优载重量当前最优载重量 ; /剩余集装箱重量剩余集装箱重量

29、 ;装载问题装载问题46templateType MaxLoading( Type w ,Type c, int n, int bestx ) /返回最优载重量返回最优载重量 Loading X; X.x = new int n+1 ; X. w = w; X. c = c; X. n = n; X.bestx = bestx; X. bestw = 0; X. cw = 0; X. r = 0; for(int i =1;i = n;i +) X. r += wi; /初始时初始时r为全体物品的重量和为全体物品的重量和 /计算最优载重量计算最优载重量 X.Backtrack(1); dele

30、te X.x; return x.bestw; 装载问题装载问题47templatevoid Loading: Backtrack( int i ) /搜索第搜索第i层结点层结点 if ( i n ) /到达叶结点到达叶结点 for( j =1; j=n; j+) bestxj=xj; bestw = cw; return; /搜索子树搜索子树 r - = w i ; if( cw + w i bestw) xi=0; Backtrack(i+1); r + = wi; 装载问题装载问题48l bestx可能被更新可能被更新O(2n)次，算法计算时间复杂性次，算法计算时间复杂性为为O(n2n)

31、。l 采用两种策略之一改进算法使其复杂度减至采用两种策略之一改进算法使其复杂度减至O(2n)（1）首先运算只计算最优值的算法，计算出最优装）首先运算只计算最优值的算法，计算出最优装载量载量W，所需计算时间为，所需计算时间为O(2n)，然后再运行改进，然后再运行改进后的后的backtrack，并在算法中将，并在算法中将bestw置为置为W。（2）动态地更新）动态地更新bsetx，在第，在第i层的当前结点处，当层的当前结点处，当前最优解由前最优解由xj, ji，和，和bestxj，i=j组成，每当组成，每当算法回溯一层时，将算法回溯一层时，将xi存入存入bestxi,这样一来，这样一来，在每个结点

32、处更新在每个结点处更新bestx只需只需O(1)时间，从而算法时间，从而算法中跟新中跟新bestx所需的时间为所需的时间为O(2n)。 装载问题装载问题49l非递归的方式可以省去非递归的方式可以省去O(n)的递归栈空间的递归栈空间templateType MaxLoading( Type w ,Type c, int n, int bestx ) /迭代回溯迭代回溯 int i = 1; /当前层当前层 / x1: i -1为当前路径为当前路径 int *x = new int n+1 ; Type bestw = 0, /当前最优装载重量当前最优装载重量 cw = 0; /当前载重量当前载重

33、量 r = 0; /剩余集装箱重量剩余集装箱重量 for( int j = 1; j =n; j+) r += wj; 装载问题装载问题50/搜索子树搜索子树while( true ) while( i= n & cw + wi n) /到达叶结点到达叶结点 for( int j = 1; j = n; j+) bestxj = xj; bestw = cw; else /进入右子树进入右子树 r -= wi; xi = 0; i+; while( cw + r 0 & !x i ) /从右子树返回从右子树返回 r += wi; i -; if( i = 0) delete x

34、; return bestw; / 进入右子树进入右子树 x i = 0; cw -= wi; i +; 51/搜索子树搜索子树while( true ) while( i= n & cw + wi n) /到达叶结点到达叶结点 for( int j = 1; j = n; j+) bestxj = xj; bestw = cw; else /进入右子树进入右子树 r -= wi; xi = 0; i+; i = 1cw = 0bestw = 0r =46cw = 0bestw = 0r =30i = 2cw = 16bestw = 0r =15i = 3cw = 16bestw =

35、0r =0i = 4cw = 16bestw = 16100装载问题装载问题l w= 16, 15, 15, c = 3052i = 1cw = 0bestw = 0r =46cw = 0bestw = 0r =30i = 2cw = 16bestw = 0r =15i = 3cw = 16bestw = 0r =0i = 4cw = 16bestw = 161000cw = 0bestw = 16r =151cw = 15bestw = 16r =0cw = 0bestw = 16r =301cw = 30bestw = 30cw = 15bestw = 30r =0cw = 0bestw

36、= 30r =15cw = 0bestw = 30r =30cw = 16bestw = 16r =0cw = 16bestw = 16r =15while( cw + r 0 & !x i ) /从右子树返回从右子树返回 r += wi; i -; if( i = 0) delete x; return bestw; / 进入右子树进入右子树 x i = 0; cw -= wi; i +; 装载问题装载问题l w= 16, 15, 15, c = 302022年6月26日53习题习题5-12022年6月26日542022年6月26日55习题习题5-22022年6月26日562022年

37、6月26日572022年6月26日58一、回溯法的算法框架二、装载问题三、三、n后问题后问题四、0-1背包问题五、最大团问题六、图的m着色问题七、旅行售货员问题2022年6月26日59N N 皇后问题是在皇后问题是在N NN N 的国际象棋棋盘上的国际象棋棋盘上, , 放置放置N N 个皇后个皇后, ,使任何两个皇后都不能相互攻击。也就使任何两个皇后都不能相互攻击。也就是说是说, , 任何两个皇后任何两个皇后, , 都不在同一行、同一列或都不在同一行、同一列或同一斜线上。同一斜线上。N N 皇后问题是由八皇后问题演化而皇后问题是由八皇后问题演化而来的。八皇后问题于来的。八皇后问题于1848 1

38、848 年由国际象棋棋手年由国际象棋棋手MaxBazzel MaxBazzel 提出。八皇后问题自从提出之后提出。八皇后问题自从提出之后, , 吸吸引了许多著名数学家的关注引了许多著名数学家的关注, , 其中包括其中包括Carl Carl GaussGauss。近年来。近年来, N , N 皇后问题成为计算机应用领皇后问题成为计算机应用领域内的一个经典问题域内的一个经典问题, , 不但成为测试算法的一个不但成为测试算法的一个工具工具, , 还成为检验并行计算系统效率的一个有效还成为检验并行计算系统效率的一个有效工具。工具。引言引言2022年6月26日60l 八皇后问题是一个非常著名的问题，最初

39、是由著名八皇后问题是一个非常著名的问题，最初是由著名数学家高斯提出的。问题的描述是这样的：在一个数学家高斯提出的。问题的描述是这样的：在一个8 8的棋盘上，摆放的棋盘上，摆放8个皇后，任意两个皇后不能处个皇后，任意两个皇后不能处在同一行、同一列和同一斜线上。该问题也可以被在同一行、同一列和同一斜线上。该问题也可以被扩展为在一个扩展为在一个n n的棋盘上摆放的棋盘上摆放n个皇后的问题。个皇后的问题。l 在在nn格的棋盘上放置彼此不受攻击的格的棋盘上放置彼此不受攻击的n个皇后。个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋

40、子。行或同一列或同一斜线上的棋子。n后问题等价于在后问题等价于在nn格的棋盘上放置格的棋盘上放置n个皇后，任何个皇后，任何2个皇后不放在个皇后不放在同一行或同一列或同一斜线上。同一行或同一列或同一斜线上。2022年6月26日61l 4皇后问题：*l 8皇后问题：1Q2Q3Q4Q5Q6 Q7Q8Q1 2 3 4 5 6 7 82022年6月26日62例：N后问题2022年6月26日63经典的回溯算法，该算法的思路如下：经典的回溯算法，该算法的思路如下： 依次在棋盘的每一行上摆放一个皇后。 每次摆放都要检查当前摆放是否可行。如果当前的摆放引发冲突，则把当前皇后摆放到当前行的下一列上，并重新检查冲突

41、。 如果当前皇后在当前行的每一列上都不可摆放，则回溯到上一个皇后并且将其摆放到下一列上，并重新检查冲突。 如果所有皇后都被摆放成功，则表明成功找到一个解，记录下该解并且回溯到上一个皇后。2022年6月26日646543211 2 3 4 5 6i+j=k+l2022年6月26日65i-j=k-l6543211 2 3 4 5 62022年6月26日66l 解向量：(x1, x2, , xn)，xi表示皇后i放在棋盘的第i行的第xi列。l 显约束：xi=1,2, ,nl 隐约束：1)不同列：xixj (ij)2)不处于同一正、反对角线：|i-j|xi-xj|l 解空间：排列树l 约束函数：xix

42、j (ij) and |i-j|xi-xj|2022年6月26日67 为了用回溯法求解4皇后问题，算法尝试生成并以深度优先方式搜索一棵完全四叉有根树，树的根对应于没有放置皇后的情况。第一层的节点对应于皇后在第一行的可能放置情况，第二层的节点对应于皇后在第二行的可能放置情况，依次类推。2022年6月26日68/place函数测试若将皇后k放在xk列是否与前面已放置的k-1个皇后都不在同一列，而且都不在同一斜线上。bool Queen:Place(int k) for (int j=1;jn) sum+;/sum记录当前已找到的可行方案数。 else for (int i=1;in时，表示算法已搜

43、索至一个叶结点，得到一个新的皇后互不攻击方案，因此当前已找到的可行方案sum加1。l当i0) xk+=1; while(xk=n)&!(place(k) xk+=1; if(xk=n) if(k=n) sum+; else k+; xk=0; else k- -; 迭代回溯迭代回溯2022年6月26日72一、回溯法的算法框架二、装载问题三、n后问题四、四、0-1背包问题背包问题五、最大团问题六、图的m着色问题七、旅行售货员问题2022年6月26日73l 给定n种物品和一个背包，物品i的重量是wi，价值pi,背包容量为C，问如何选择装入背包的物品，使装入背包中的物品的总价值最大？l 对于

44、每种物品只能选择完全装入或不装入，一个物品至多装入一次。2022年6月26日74l 解空间：子集树l 可行性约束函数：或：cw+wi=ccxwijjj175n=4,c=7,w= 3,5,2,1, p = 9,10,7,40,03,90,086,205,163,97,173,95,101000001111用子集树表示其解空间，左儿子如果可行，进入左子树，只有右子树中有可能包含最用子集树表示其解空间，左儿子如果可行，进入左子树，只有右子树中有可能包含最优解时才进入右子树搜索，否则将右子树剪去。优解时才进入右子树搜索，否则将右子树剪去。上界函数：上界函数：cp + rbestp 当前获得价值当前获得

45、价值+剩余价值剩余价值当前最优价值。当前最优价值。13,9010 0-1背包问题背包问题76l有时即使满足了有时即使满足了cp + rbestp ，但实际上背，但实际上背包并不能装下所有剩余物品，也就是上界包并不能装下所有剩余物品，也就是上界cp + r大了。大了。l缩小上界可以提供另一个更好的上界函数。缩小上界可以提供另一个更好的上界函数。l计算右子树中解的上界时，将剩余物品依其计算右子树中解的上界时，将剩余物品依其单位重量价值排序，然后依次装入物品，直单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满至装不下时，再装入该物品的一部分而装满背包，由此得到的价值是右子

46、树的上界，如背包，由此得到的价值是右子树的上界，如果这个上界不能达到当前得到的最优值，则果这个上界不能达到当前得到的最优值，则不搜索该子树。不搜索该子树。5.3 0-1背包问题背包问题77l以物品单位重量价值的递减序装入物品。以物品单位重量价值的递减序装入物品。ln=4, c= 7, p =9, 10, 7, 4, w =3, 5, 2,1l单位价值量单位价值量3, 2, 3.5, 4。l先装入物品先装入物品4，然后，然后3，1，物品，物品2最多装最多装0.2，得到一个解得到一个解1, 0.2, 1, 1，相应的上界为，相应的上界为22。5.3 0-1背包问题背包问题78l将物品按单位价值量排

47、序。将物品按单位价值量排序。l在解空间树的当前扩展结点处，仅当要进在解空间树的当前扩展结点处，仅当要进入右子树时才计算上界函数入右子树时才计算上界函数Bound，判断，判断是否可以将右子树剪去。是否可以将右子树剪去。l进入左子树时，不需要计算上界。进入左子树时，不需要计算上界。5.3 0-1背包问题背包问题79templateTypep Knap: Bound( int i) /计算上界计算上界 Typew cleft = c cw; /剩余容量剩余容量 Typep b = cp; /以物品单位重量价值递减序装入物品以物品单位重量价值递减序装入物品 while ( i= n & wi=

48、 cleft) cleft -= wi; b += pi; i+; /装满背包装满背包 if( i=n ) b+= pi/wi*cleft; return b; 0-1背包问题背包问题80n=4,c=7,w=1，2，3，5, p = 4，7，9 ， 100,01, 43,11116,2016,2001920192020=205.3 0-1背包问题背包问题81templateclass Knap /背包描述背包描述 friend Typep Knapsack(Typep*, Typew*,Type, int); private: Typep Bound(int i); void Backtrac

49、k(int i); Typew c; /背包容量背包容量 int n; /物品数物品数 Typew * w, /物品重量数组物品重量数组 Typep * p, /物品价值数组物品价值数组 Typew cw; / 当前重量当前重量 Typep cp; /当前价值当前价值 Typep bestp; /当前最优价值当前最优价值;Backtrack实现回溯搜索，实现回溯搜索，Backtrack(1)实现对整个解空间的实现对整个解空间的回溯搜索，回溯搜索，Backtrack(i)搜索子集树搜索子集树中第中第i层子树。层子树。计算第计算第i层结点的上界层结点的上界5.3 0-1背包问题背包问题82clas

50、s Object /物品物品 friend int Knapsack(int *, int *, int, int ); public: int operator = a.d); private: int ID; float d; / 单位重量价值单位重量价值; 0-1背包问题背包问题83templateTypep Knapsack(Typep p , Typew w , Typew c, int n) /为为Knap:Backtrack 初始化初始化 Typew W = 0; Typep P =0; Object * Q = new Objectn; for ( int i = 1; i =

51、 n; i+ ) Q i-1. ID = i; Q i-1. d =1.0*pi/wi; P += pi; W+= wi; if( W =c ) return P; /装入所有物品装入所有物品 /依物品单位重量价值排序依物品单位重量价值排序 Sort( Q, n); Knap K; K.p = new Typep n +1 ; K.w = new Typew n+1 ; for ( int i = 1; i = n; i+) K.pi = p Qi-1.ID; K.wi = w Qi-1.ID; K.cp = 0; K. cw = 0; K.c = c; K.n = n; K.bestp =

52、0;/ 回溯搜索回溯搜索 K.Backtrack(1); delete Q; delete K.w; delete K.p; return K.bestp;5.3 0-1背包问题背包问题84 templateTypep Knap: Backtrack( int i) if ( i n ) bestp = cp; return; if( cw + wi bestp) /xi = 0 Backtrack(i+1); 0-1背包问题背包问题如何计算？如何计算？85算法效率算法效率 由于计算上界函数由于计算上界函数Bound需要需要O(n)时间，时间，在最坏情况下有在最坏情况下有O(2n)个右儿子结点

53、需要计个右儿子结点需要计算上界函数，故解算上界函数，故解0-1背包问题的回溯算法背包问题的回溯算法Backtrack所需的计算时间为所需的计算时间为O(n2n)。 0-1背包问题背包问题2022年6月26日86一、回溯法的算法框架二、装载问题三、n后问题四、0-1背包问题五、最大团问题五、最大团问题六、图的m着色问题七、旅行售货员问题2022年6月26日87l 完全子图完全子图：给定无向图G=(V，E)。如果UV，且对任意u，vU有(u，v)E，则称U是G的完全子图。l 团团：G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。l G的最大团的最大团：是指G中所含顶点数最多的团。12

54、4532022年6月26日88l 空子图空子图：如果UV且对任意u，vU有(u，v)E，则称U是G的空子图。l 独立集独立集：G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。l G的最大独立集的最大独立集：是G中所含顶点数最多的独立集。l 补图补图：对于任一无向图G=(V，E)其补图G=(V1，E1)定义为：V1=V，且(u，v)E1当且仅当(u，v)E。l U是是G的最大团当且仅当的最大团当且仅当U是是G的最大独立集。的最大独立集。12453124532022年6月26日89l 解空间：子集树l 可行性约束函数： 顶点i到已选入的顶点集中每一个顶点都有边相连。 l 上界函数：

55、有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。2022年6月26日90void Clique:Backtrack(int i)/ 计算最大团 if (i n) / 到达叶结点 for (int j = 1; j = n; j+) bestxj = xj; bestn = cn; return; int OK = 1; / 检查顶点 i 与当前团的连接 for (int j = 1; j bestn) / 进入右子树 xi = 0; Backtrack(i+1);复杂度分析复杂度分析最大团问题的回溯算法backtrack所需的计算时间为O(n2n)。2022年6月26日91一、回溯法

56、的算法框架二、装载问题三、n后问题四、0-1背包问题五、最大团问题六、图的六、图的m着色问题着色问题七、旅行售货员问题2022年6月26日92l 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。l 若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。l 求一个图的色数m的问题称为图的m可着色优化问题。2022年6月26日93l 可平面图：如果一个图的所有顶点和边都能用某种方式画在一个平面上且没有任何两边相交，则称这个图是可平面图。l 四色

57、定理：任何平面图都是可以4着色的。2022年6月26日94l 图的m着色问题： 给定一个一般连通图G=(V,E)和m种颜色，如果这个图不是m可着色的就给出否定回答，如果这个图是m可着色的，则要找出所有不同的着色方案。2022年6月26日95l 解向量：(x1, x2, , xn)表示顶点i所着颜色xi 。l 解空间：完全m叉树l 可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。2022年6月26日96void Color:Backtrack(int t) if (tn) sum+; /当前已找到的可当前已找到的可m着色方案数加着色方案数加1； for (int i=1; i=n; i+)

58、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) / 检查第检查第k个顶点当前所选颜色个顶点当前所选颜色xk的可用性；的可用性； for (int j=1;j=n;j+) if (akj=1)&(xj=xk) return false; return true;2022年6月26日97l图m可着色问题的解空间树中内结点个数是mi(0in-1)。l对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(

59、mn)。因此，回溯法总的时间耗费是mi(mn)=nm(mn-1)/(m-1)=O(nmn)(0in-1)2022年6月26日98一、回溯法的算法框架二、装载问题三、n后问题四、0-1背包问题五、最大团问题六、图的m着色问题七、旅行售货员问题七、旅行售货员问题2022年6月26日99 旅行商问题是一个经典的组合优化问题。经典旅行商问题是一个经典的组合优化问题。经典./- 可以描述为：一个商品推销员要去若干个城市推销商品，可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使

60、总的行程最短。从出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的中，找一个权值最小的HamiltonHamilton 回路。由于该问题的可回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个组合爆炸，它是一个NPNP 完全问题。由于其在交通运输、完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用，电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。国内外学者对其进行了大量的研究。2022年6月2