2015算法第八章回溯法

1、第8章 回溯法吉林大学计算机学院谷fmgu2002主要内容p 8.1p 8.2一般8-皇后p 8.3 子集和数p 8.4 图的着色(略)p 8.5 哈密顿环(略)(略)p 8.6 背包(略)8.1 一般Ø 什么是回溯§ 迷宫回溯回溯回溯Ø 什么是回溯法§ 回溯法是一种搜索算法回溯出口的解，§ 回溯法是以深度优先的方式系统地搜索它适用于解一些组合数较大的。§ 寻求一组求满足某些约束条件的最优解。38.1 一般p 解的形式回溯法要求限界函数的解可以用一个n-元组(x1,¼, xn)来表示，其中xi取自于某个有穷集Si。通常，需要

2、求取一个使某一规范函数P(x1, ¼, xn)取极值或满足其条件的。有时还要找出满足规范函数P的所有。假设集合Si的大小是mi，满足规范函数P的可能的元组数目为m=m1´m2 ´ ¼ ´ mn 。p 硬性处理：构造m个n元组并逐一检测是否满足P，从而找出的所有最优解。p 回溯法不断地用修改过的限界函数Pi(x1, ¼, xi)去测试正在构造的n元组的部分，看其是否可能导致最优解，如果不能，就4将可能要测试的mi+1 ¼ mn个略去。回溯求解的基本概念回溯法的解需要满足一组综合的约束条件，通常分为：显式约束和隐式约束。可能与实

3、例I有关，也可能无关显式约束条件： 限定每。个x只从一个给定的集合上取值。例如，xi³0，即Si=所有非负实与数xi=0或1，即Si =0,1隐式约束条件： 规定了实例I的解空间中那些满足规范函数的元组，描述了xi必须彼此相关的情况。解空间：满足显式约束的所有元组。可行解：解空间中满足隐式约束条件的元组。5实例I有关例8.1（8-皇后）p 在一个8´8棋盘上放8个皇后，使每两个皇后之间都不能互相“”，即：使得每两个皇后都不能在同一行、同一列及同一条斜角线上。p 假定皇后i放在行i上，8皇后可以表示为8-元组(x1,¼,x8)，其中xi是皇后i被放置的列号。p 显式

4、约束条件：Si =1, 2, 3, 4, 5, 6, 7, 8,1£i£8解空间：88p 隐式约束条件：没有两个x 可以相同，且i解空间：8！6没有两个皇后可以在同一条斜角线上。(4,6,8,2,7,1 ,3,5)QQQQQQQQ例8.2子集和数及描述已知n+1个正数：wi(1£i£n)和M，要求找出wi 的p和等于M。集使得子集中元例如：n=4，(w1, w2, w3, w4)=(11, 13, 24, 7)， M=31。则满足要求的子集是(11, 13, 7)和(24, 7) 。p用wi的下标来表示。一般情况下，所有的p解都是k-元组(x1,

5、8;, xk)，1£k£n，不同的解k值不同。显示约束条件：xiÎj|j是整数wj的下标且1£j£n 隐式约束条件：xi互不相同且相应的wk的和数等pp于M为7子集和数的描述另一种表示p 解采用大小固定的n-元组(x1,¼, xn) 表达，其中：xi Î0,1,1£i£n，若 xi=0,解集合不包含wi；若 xi=1，解集合包含wi；(1, 2, 4)和(3, 4)可以表示为则例中(1,1,0,1)和(0,0,1,1)。8解空间的树结构p 回溯算法通过系统的检索给定的解空间来确定描述。的解。解空间可以用树

6、结构加以p 对于一个给定的解空间，可能有多种树结构。9例8.3n-皇后p n个皇后将被放置在n´n的棋盘上且使得没有两个皇后可以互相。p n-皇后是8 -皇后的推广，其解空间由n-元组(1,2,n)的n!个排列所组成。p n=4时的树结构¾ 排列树。树的xi的可能的取值标记。由i级到i+1级结点的边给出xi的值。解空间由从根节点到叶节点的所有路径定义。10Ø 4-皇后的解空间树x1=142350911202225274434211111221232628解空间树(状态空间树)的一些概念§状态(problem state)：的每一个结点确定所求解的一个状态

7、。§ 状态空间(state space)：由根结点到其他结点的所有路径确定了这个的状态空间。§ 解状态(solution states)： 是这样一些状态S，对于这状态，由根到S的些路径确定了这个解空间中的一个元组。§状态(answer states)：是这样的一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这（满足隐式约束条件）。§ 状态空间树(state space tree)：解空间的树结构。的一个解状态Í 解状态Í状态(解空间的结点)例8.4 子集和数的解空间树1§ 解空间是节点到x1=1x =4任何结点的

8、所有路径。§ 根结点到自身的空路径1x =3x =211( )对应一个空x2=4x =2x2=42x =4x =3x2=32102§红色的路11径分别对应：x3=4x3=3x3=4x3=4( ), (1) , (1, 2)( ), (2) , (2, 3)( ), (4)(1, 2, 4)(2, 3, 4)12131415x4=416的解空间树2：每一个解的子集由子集和数元组(x1,¼, xn)所表示，xiÎ0,1，1£i£n n=4时，叶节点2n=24=16。x1=0x1=1x2=019x3=120x2=0x2=118x3=027x

9、2=1x3=0x3=1x3=013x3=021x3=112x3=126101010101010101030312829242522231614151189红色路径表示元组(1,1,0,1)一个大小固定的n-从根结点到的一条路径叶结点确定解空间中的一个元组回溯法的一些特点§ 回溯法在求§ 回溯法在求的所有的任一， 要遍历树才能结束。，只要搜索到的一个可以结束。§ 回溯法在包含所有解的解空间，按深度优先的策略，从根结点出发搜索解空间树。§ 回溯法搜索至解空间树的任一结点时，先该结点是否一定不包含的解。如果一定不包含，则跳过以该结点为根的子树，逐层向其祖先结点

10、回溯。否则就进入该子树，继续按深度优先的策略进行搜索。15解空间树(状态空间树)的一些概念§ 静态树(static trees)：树结构与所要解决例无关。的实§ 动态树(dynamic trees)： 树结构是与实例相关的，且树结构是动态确定的。§ 活结点：已经生成而其所有的儿子结点还没有全部生成的结点。§ E-结点(正在扩展的结点)： 当前正在生成其儿子结点的活结点。§ 死结点：不再进一步扩展或者其儿子结点已全部 生成的结点.16状态的生成§ 第一种状态生成：当前的E-结点R 一旦生成一个新的儿子结点C，这个C结点就变成一个新的E-

11、结点，当检测完了子树C后，R结点就再次成为E-结点，生成下一个儿子结点。(该点生成法)也称为深度优先结§ 第二种状态生成：一个E-结点一直保持到变成死结点为止。它又分为两种：宽度优先生成方)法(队列)和D-检索(栈§ 第一种状态生成§ 第二种状态生成对溯法。对应分枝-限界法。17例8.54-皇后§ 开始把根结点作为唯一的活结点，根结点就成为E-结点而且路径为( )；接着生成儿子结点， 假定按自然数递增的次序来生成儿子，那么结点2 被生成，这条路径为(1)，即把皇后1放在第1列上。1x1=12§ 结点2变成E-结点，它再生成结点3，路径变为(1,

12、 2)，即皇后1在第1列上，皇后2 在第2列上，所以结点3被杀死，此时应回溯。x = 223kill18121§ 回溯到结点2生成结点8，路径变为(1, 3)，则结点8成为E-结点，它生成结点9和结点11都会被杀死(即它的儿子表示不可能导致的棋盘格局)，所以结点8也被杀死。溯。1x1=12x2= 2x2=33kill8x3=4x3=29kill11kill19123121231§ 回溯到结点2生成结点13，路径变为(1, 4)， 结点13成为E-结点，由于它的儿子表示的是1一些不可能导致 结点13也被杀死，结点的棋盘格局，因此溯。x1=12x2= 4x2= 2x2= 313

13、x =3kill823x3=4x3=2x3=39kill11kill1416killx4=315kill201234121231§ 结点2的所有儿子表示的都是不可能导致的棋盘格局，因此结点2也被杀死；再回溯到结点1生成结点18， 路径变为(2)1§ 结点18的儿子结点19、结点24被杀死，溯x1=2x1=1218x2= 4x2= 1x2= 2x2= 3x2= 319248133killx3=2killkillx3=4x3=2x3=39kill11kill1416killx4=315kill2112121§ 结点18生成结点29，结点29成为E-结点，路径变为(2,

14、4)；§ 结点29生成结点30，1x1= 2x1=1218路径变为(2,4,1)§ 结点30生成结点31，x2= 4x2=1x2=429x3=1x2= 2x2= 38x2= 324kill路径变为(2,4,1,3)， 找到一个4-皇后的可行解。19133killx3=2killx3=4x3=2x3=31309kill11kill1416kill23x4=3314x4=315kill可行解12322121回溯算法的三个步骤1、所给定义的解空间，解空间应至少包含的一个最优解。2、确定易于搜索的解空间树结构。3、以深度优先方式搜索空间树，并在搜索过程中使用限界函数避免无效搜索。2

15、3回溯法搜索过程§ 从根结点出发，以深度优先方式搜索整个解空间。§ 首先根结点成为一个活结点，同时也成为当前的扩展结点。在当前扩展结点处，搜索向纵深方向移至一个新结点，该新结点成为一个新的活结点，并成为当前扩展结点。§ 如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时溯至最近的一个活结点处，并使该活结点成为当前的扩展结点。§ 回溯法以这种方式递归地在解空间中搜索, 直至找到所要求的解空间中已没有活结点时为止。24回溯算法的形式化描述§ 假设回溯法要找出所有的§ 设(x1, x2,¼, xi-1)是状

16、态空间到一个结点的路径；结点；由根§ T(x1,¼, xi-1)是下述所有结点xi的集合，它使得对于每一个xi，(x1, x2,¼, xi)是一条由根到结点xi的路径；§ 假定一些限界函数Bi，如果路径(x1, x2,¼, xi)不可能延伸到一个结点，则Bi(x1, x2,¼, xi)取假值，否则取真值。1416§X(1:n)中的第i个分量就是那些选自集合T(x1, x2,¼, xi-1)且使Bi为真的xi 。25算法8.1 回溯的一般procedure BACKTRACK(n)int k, n;local X(1

17、: n); k¬1;while (k>0) do限界函数B(X(1)¼X(k)哪些X(k)满足隐式约束条件。repeatend BACKTRACK26if ( 还剩有没检验的X(k)使得X(k)ÎT(X(1)¼X(k-1) and B(X(1)¼X(k)=TRUE )thenk¬k+1;/考虑下一个集合elsek¬k-1;/回溯endifif (X(1) ¼ X(k)是一条抵达结点的路径) then print ( X(1)¼X(k) );/打印数组Xendifprocedure BACKTRACK

18、(n) int k, n;local X(1: n); k¬1;while (k>0) doif ( 还剩有没检验的X(k)使得X(k)ÎT(X(1)¼X(k-1) andB(X(1)¼X(k)=TRUE )then if (X(1) ¼ X(k)是一条抵达答案结点的路径)then print ( X(1)¼X(k) ); endifk¬k+1;k=2k=31416k=4若只需要一个解,怎样修改算法？elsek¬k-1; endifrepeatend BACKTRACK27算法8.2 递归回溯算法proced

19、ureRBACKTRACK(k)globalX(1:n);int k, n;for ( 满足下式的每个X(k), X(k)ÎT(X(1),¼, X(k-1)and B(X(1),¼, X(k)=true) if (X(1),¼,X(k)是一条抵达print (X(1)¼X(k);do结点的路径thenRBACKTRACK(k+1);call对于所有可以由根结点到达，并可能使限界函数B为真的结点X(k)， (X(1)¼X(k)是否是一条能endRBACKTRACK抵达结点的路径28 进入算法时, X中的前k-1个分量X(1)¼

20、X(k-1)已经被赋值回溯法的效率估计n 回溯法的效率主要取决于四种因素：生成结点的时间子结点的数量检验结点的时间ü 生成下一个X(k)的时间ü 满足显式约束条件的X(k)的数目ü 限界函数Bi的计算时间ü 满足Bi的X(k)的数目n 限界函数能够大大减少生成的结点数，但在计算时间和减少程度上要进行折中。29通过检验的结点数量效率估计p 一旦选定了一种状态空间树结构，前三种因素与所要解决的实例无关，只有第四种因素，对于的不同实例，生成的结点数是不相同的。，回溯算法最坏情况下的时间复杂度为pO(p(n)2n)或O(q(n)n!)，其中p(n)和q(n)为n

21、的多项式。p 尽管回溯法对同一不同实例在计算时间上出现巨大差异，但在n很大时，对某些实例仍然十分有效。30p 用回溯算法处理一棵树所要生成的结点数，可以效率估计-估计满足Bi的X(k)的数目p 蒙特卡罗Ø 在状态空间生成一条随机路径。Ø 设X是这条路径上第i级的一个结点。Ø 在结点X处用限界函数确定没受限界的儿子结点数目mi 。Ø 在这mi个儿子结点中随机选择一个作为下一个结点。Ø 这条路径在以下结点处结束：或者它是一个点，或者该结点的所有儿子结点都已被限界。Ø 用这些m 可以估算出这棵状态空间不受限界结点不受限界结点的估计数m=1+

22、m1+m1´m2+m1´m2´m3 +¼，mi表示第i级结点平均没受限界的儿子结点数。效率估计-估计满足Bi的X(k)的数目p 蒙特卡罗Ø 优点：找到所有结点的情况非常有用，限界函数固定不变，计算方便，对状态空间一级结点都适用。Ø 缺点：同只求一个，生成的结点数远小于m，随着检索的进行，限界函数应该更强，使得m的值更小。32效率估计Procedure ESTIMATE/程序沿着状态空间不受限界结点的估计数/一条随机路径产生这棵m ¬1; r ¬1; k ¬1loopTk ¬X(k): X(k)

23、Î T(X(1), ¼, X(k-1) ) Bk (X(1), ¼, X(k-1)andif SIZE(Tk)=0 then exit endifr ¬r´SIZE(Tk)m ¬m+rX(k) ¬CHOOSE(Tk)k ¬k+1 repeat return(m)end ESTIMATE/第k级的结点数/前第k级的结点总数/从Tk中随机地挑选一个元素338.28-皇后描述及分析pp 限界函数p 求n-皇后p 效率分析的所有解34描述： 在一个8´8棋盘上放置8个皇后，使得每两个皇后之间都不能互相“”，即每两

24、个皇后都不能在同一行、同一列及同一条斜角线上。Ø 8皇后可以表示为8-元组(x1, ¼, x8)， 其中xi是放置皇后i所在的列号Ø 图中的可行解表示为一个8-元组，即(4, 6, 8, 2, 7, 1, 3, 5)Q1Q2Q3Q4Q5Q6Q7Q8用二维数组A(1:8,1:8)的下标来标记每个皇后的位置，那么可以看到:对于在由左到右的同一条斜角线上的每个元素具有相同的“行-列”值;对于在由右到左的同一条斜角线上的每个元素则具有相同的“行+列”值设有两个皇后被放置在(i, j )和(k, l )位置上, 那么当且仅当i-j = k-l或 i+j = k+l 时, 它

25、们才在同一条斜角线上。将这两个等式分别变换成: j-l = i-k或 j-l = k-i 。因此当且仅当 |j-l|=|i-k| 时( 即两个皇后所在位置的行差距等于列差距时)，两个皇后在同一条斜角线上。36a11a12a13a14a15a16a17a18a21a22a23a24a25a26a27a28a31a32a33a34a35a36a37a38a41a42a43a44a45a46a47a48a51a52a53a54a55a56a57a58a61A62a63a64a65a66a67a68a71a72a73a74a75a76a77a78a81a82a83a84a85a86a87a8837限界

26、函数p PLACE(k)：ü 令X(k)与X(i)逐个比较，i=1, ¼, k-1。ü 若X(k)=X(i)或者|X(i)-X(k)|=|i-k|Ø 则返回false；Ø 否则返回true。对X(k)的限定算法8.4 能否放置一个新皇后?procedurePLACE(k)inti , k;i¬1;while ( i<k )doif (X(i)=X(k) or ABS(X(i)-X(k)=ABS(i-k) thenreturn (false); endifi¬i+1;repeatreturn (true);l )位置上即

27、为不能放皇后，应返回false值endPLACE38/ 若两个皇后在同一列上，或在同一对角线上，则说明该位置若一个皇后能放在第k行第X(k)列, 则返回true，否则返回false；X是全程数组，进入此过程了k个值，ABS是绝对值函数算法8.5 求n-皇后的回溯算法描述求所有解procedureNQUEENS(n)intk, n, X(1:n);X(1)¬0 ;k¬1;/ k是当前行；X(k)是当前列/ 对所有的行执行循环语句/移到下一列当该位置不while (k>0) do X(k)¬X(k)+1;能放皇后时转到下一列repeatrepeatend NQU

28、EENS39if (X(k)£n) then/找到一个位置if (k=n) then/若是一个完整的打印数组Xprint (X);else k¬k+1; X(k)¬0; /否则转到下一行endifelsek¬k-1;/ 没有合适的位置，回溯endifwhile ( X(k)£n and Not PLACE(k) ) doX(k)¬X(k)+1;X(1)=0 ;k=1;while (k>0) do X(k)=X(k)+1;while (X(k)£n and Not PLACE(k) do 1£n and Not

29、 true , 循环不执行 if (X(k)£n) thenif (k¹n) then 不执行else k=k+1=2; X(2)=0; end whilek=2;while (k>0) do X(k)=X(k)+ PLACE(2)while ( X(k) i=1;3£n and Nwhile ( i<k )do if (X(i)¹X(k) or |X(i)-X(k)|¹|i-k|) theni=i+1=2; 结束循环不执行if (X(k)£n)if (k¹n) k=return (true);else end

30、whileQ1Q21234X130k=3;while (k>0) do X(k)=X(k)+1;while (X(k)£n and Not PLACE(k) do 5n , 循环不执行if (X(k)n)then不执行elsek=k-1=2; /回溯 end whilek=2;while (k>0) doX(k)=X(k)+1=3+1=4;while ( X(k)£n and NotPLACE(k) )do 4£n and Not true , 循环不执行if (X(k)£n) thenif (k¹n) then 不执行else k

31、=k+1=3; X(3)=0; end while41Q1Q21234X140k=3;while (k>0) do X(k)=X(k)+1;while (X(k)£n and Not PLACE(k) do 2£n and Not true , 循环不执行; if (X(k)<n) thenif (k¹n) then 不执行else k=k+1=4; X(4)=0; end whilek=4;while (k>0) do X(k)=X(k)+1=1;while ( X(k)£n and Not PLACE(k) )do 5n , 循环不

32、执行if (X(k)n)then不执行elsek=k-1=3; /回溯 end while42Q1Q2Q31234X1425k=3;while (k>0) do X(k)=X(k)+1;while (X(k)£n and Not PLACE(k) do 5n , 循环不执行if (X(k)n)then不执行elsek=k-1=2; /回溯 end whilek=2;while (k>0) do X(k)=X(k)+1=4+1=5; while ( X(k)£n and NotPLACE(k) )do 5n , 循环不执行if (X(k)n)then不执行elsek=k-1=1; /回溯 end while43Q1Q21234X155k=1;while (k>0) do X(k)=X(k)+1;while (X(k)£n and Not PLACE(k) do 2£n and Not true , 循环不执行; if (X(k)£n) thenif (k¹n) then 不执行else k=k+1=2; X(2)=0; end whilek=2;while (k>0) do X(k)=X(k)+1;wh