《课件-pptch6ppt》由会员分享，可在线阅读，更多相关《课件-pptch6ppt（24页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章 回溯方法回溯方法 算法的基本思想算法的基本思想 定和子集定和子集 与与 0/10/1背包问题背包问题 n n皇后和旅行商问题皇后和旅行商问题 图的图的着色问题着色问题 回溯法效率分析回溯法效率分析 回溯算法的基本思想回溯算法的基本思想 ?解空间解空间 多阶段解决问题的方案，决策序列，所有可能的决策序列构多阶段解决问题的方案，决策序列，所有可能的决策序列构 成解空间。成解空间。k k- -定解空间：前面定解空间：前面k k个决策确定后所有可能的决策序个决策确定后所有可能的决策序 列。从求解问题的角度看，每确定一组前列。从求解问题的角度看，每确定一组前k k个决策就相当于问题个决策就
2、相当于问题 求解到一个状态。未解状态对应求解到一个状态。未解状态对应0 0- -定子空间。定子空间。 ?状态空间树状态空间树 以未解状态为根节点，确定各步决策的过程可以用一棵树描述以未解状态为根节点，确定各步决策的过程可以用一棵树描述 出来。根节点的子节点就是第一步决策确定后的所有问题状态，出来。根节点的子节点就是第一步决策确定后的所有问题状态， 对应于各个对应于各个1 1- -定子空间。当一个完整的决策序列做出之后，实际定子空间。当一个完整的决策序列做出之后，实际 上已经达到了一个解状态。上已经达到了一个解状态。 ?解向量解向量: : x x 1 1 , x, x 2 2, , , x, x
3、 n n ?显式约束显式约束: : 只约束变量的取值范围。只约束变量的取值范围。 ?隐式约束：强制变量之间的关联和制约。隐式约束：强制变量之间的关联和制约。 ?目标函数：极大或极小倾向或目的，有些问题不设目标函数。目标函数：极大或极小倾向或目的，有些问题不设目标函数。 ?可行解：满足约束条件的解，在状态空间树中的答案节点。可行解：满足约束条件的解，在状态空间树中的答案节点。 旅行商问题状态空间树旅行商问题状态空间树 A CD B 4 5 20 106 30 32 0 1 31 41 21 42 33 43 22 34 44 35 45 23 36 46 592525 1.A； 2.AB, AC
4、, AD; 3.ABC,ABD,ACB, ACD,ADB,ADC; 4. ABCA,ABDA, ACBA,ACDA, ADBA, ADCA 定和子集问题的状态空间树定和子集问题的状态空间树(1)(1) 172 1 47 89 5 3 6 1114 1516 12 10 13 2629 3031 27 25 28 1922 2324 20 18 21 1 0 1 0 1 0 1 0 1 0 1 0 x1=1 x1= 0 x2=1x2=1x2= 0x2= 0 x3= 0x3= 0x3= 0x3= 0 x3= 1 x3= 1x3= 1 x3= 1 x4= 1 x4= 0 x4= 1x4= 1 静态树
5、： 树结构独立于解决 的问题实例本身。 节点编号：以深度 优先搜索顺序编号 定和子集问题状态空间树定和子集问题状态空间树(2)(2) 1 2345 678 121314 16 91011 15 x2=4x2=3 x2=4 x2=3 x2=2 x1=4 x1=3 x1=2 x1=1 x3=3x3=4 x4=4 x3=4x3=4 x2=4 动态树： 树结构依赖于问 题实例的树结构。 节点编号：以宽度 优先搜索顺序编号 n=4, m=31 (w1,w2,w3,w4)=(11,13,24,7), n n皇后问题状态空间树皇后问题状态空间树 563540455161 8 13192429 3 50 2
6、1834 1 5 12 10 7 211715 545248323646433841 9 1114162022252730 46 64625957 4744423937333128 262365 63 605855 5349 4 3 4 2 3 2 4 3 4 1 3 1 4 2 4 1 2 1 3 2 3 1 2 1 3 4 2 4 2 3 3 4 1 4 1 3 2 4 1 4 1 2 2 3 1 3 1 2 2 3 4 1 3 4 1 2 4 12 3 x1= 1 x1= 4 x1= 3x1= 2 N=4, 节点按D-搜索次序编号 回溯算法基本思想回溯算法基本思想 枚举枚举枚举枚举： m
7、=mm=m 1 1 mm 2 2 mm n n 个可能的解硬性处理。个可能的解硬性处理。 剪枝函数剪枝函数剪枝函数剪枝函数：约束条件：约束条件( (约束函数约束函数) )、最优值的界（限界函数）、最优值的界（限界函数） 回溯法回溯法回溯法回溯法: : 一次针对一个部分生成一个解向量，使用限界函数测试一次针对一个部分生成一个解向量，使用限界函数测试 正在形成的解向量是否有成功的可能性。如果得知通过部分正在形成的解向量是否有成功的可能性。如果得知通过部分 向量向量 (x(x 1 1 ,x ,x 2 2 , ,x ,x k k ) ) 无法得到最优解，那么完全可以忽略之后的无法得到最优解，那么完全可
8、以忽略之后的 mmk+1 k+1 mm n n 个测试向量。个测试向量。 解的搜索解的搜索解的搜索解的搜索：使用状态空间树，以深度优先顺序系统生成问题状：使用状态空间树，以深度优先顺序系统生成问题状 态，决定其中那些状态是解状态，最终确定那些状态是答案态，决定其中那些状态是解状态，最终确定那些状态是答案 状态。状态。 从根节点开始，逐步生成各节点的子节点。节点已经生成并从根节点开始，逐步生成各节点的子节点。节点已经生成并 且其子孙节点还有未生成的，这样的节点称为活节点。对于且其子孙节点还有未生成的，这样的节点称为活节点。对于 一个活节点，当前它的子节点正在生成，称为扩展节点。一一个活节点，当前
9、它的子节点正在生成，称为扩展节点。一 个已经生成、不再扩展（没有子节点需要继续生成）的节点个已经生成、不再扩展（没有子节点需要继续生成）的节点 称为死节点。当前扩展节点称为死节点。当前扩展节点R R的新的子节点的新的子节点C C一旦生成，这个一旦生成，这个 节点就做为新的扩展节点。当子树节点就做为新的扩展节点。当子树C C被扩展到最大极限时，被扩展到最大极限时，R R 再次成为扩展节点，这就是回溯。生成问题状态总是在扩展再次成为扩展节点，这就是回溯。生成问题状态总是在扩展 节点处生成其子节点。节点处生成其子节点。 n n皇后问题皇后问题 解向量：解向量：(x(x 1 1 ,x ,x 2 2 ,
10、 ,x ,x n n ) ) 显式约束：显式约束：x x i i 1,2,1,2,n,n； x x i i x x j j 当当i i j j时。时。 隐式约束：隐式约束： i i j j | x| x i i - -x x j j | | |i |i- -j| j|。 1 4 1 3 3 1 4 2 2 4 1 3 1 4 2 34 31 30 18 2956 3551 50 1 54 38 39 2 13 14 8 44 3 4 1 3 2 2 1 2 3 4 1 3 2 n n皇后问题的回溯算法皇后问题的回溯算法 PlacePlace(k)/(k)/如果第如果第k k个皇后能放个皇后能放
11、 / /在第在第XkXk列列, ,则返回则返回true,true,否则否则 / /返回返回false. Xfalse. X是一个全程数是一个全程数 / /组组, ,进入此过程时已经设置进入此过程时已经设置 / /了了k k个值个值 globalglobal X1k; X1k; integerinteger i,k;i,k; i:=1;i:=1; whilewhile i0 dodo ?Xk:=Xk+1;/Xk:=Xk+1;/转到下一列转到下一列 ?whilewhile XkXk n n andand Place(k)=false Place(k)=false dodo ?Xk:=Xk+1;Xk
12、:=Xk+1; ?endwhileendwhile ?if if XkXk n n thenthen ?if if k=n k=n thenthen ?Print(X);Print(X); ?elseelse k:=k+1; Xk:=0; /k:=k+1; Xk:=0; /转到下一行转到下一行 ?endifendif ?elseelse k:=kk:=k- -1;/1;/回溯回溯 ?endifendif ?endwhileendwhile ?endnQueensendnQueens 旅行商问题旅行商问题 ?代表代表n n个城市的顶点个城市的顶点0,1,2,0,1,2,n ,n- -1; 1;
13、城市城市 i, j i, j 之间的路程之间的路程 w(i, j)w(i, j)； 数组数组 (i (i 1 1,i ,i2 2 , ,i ,i n n ) ) 代表一个周游代表一个周游 i i 1 1 i i 2 2 i i n n i i 1 1 。 ?可行解的前可行解的前 k k- -1 1个分量个分量x x 1 1 , ,x ,x k k- -1 1 确定后，判定确定后，判定x x 1 1 x x k k- -1 1 x xk k 能否构能否构 成一条路径，需要检查成一条路径，需要检查 x xk k x x 1 1 , , , x, x k k x x k k- -1 1 约束条件 约
14、束条件 ?当前路长：当前路长：cl cl = w(x= w(x 1 1 , x, x 2 2 )+w(x)+w(x 2 2 , x, x 3 3 )+ )+ +w(x+w(x k k- -2 2 , x, x k k- -1 1 ), ), ?已知最佳游路长：已知最佳游路长： fl fl。如果如果 cl cl + w(x+ w(x k k- -1 1 , x, x k k ) ) fl fl 限界函数限界函数 则则 x x 1 1 x x k k- -1 1 x xk k 不是最短周游路径的一部分，因而不必继续向前不是最短周游路径的一部分，因而不必继续向前 搜索，即状态空间树中此状态后面的子树
15、被剪掉（剪枝）。搜索，即状态空间树中此状态后面的子树被剪掉（剪枝）。 ?更新最佳目标值：当更新最佳目标值：当 k = nk = n时，如果时，如果 cl cl + w(x+ w(x k k- -1 1 , x, x k k ) +w(x) +w(x k k , x, x 1 1 ) 1 dodo Xk:=Xk+1 Xk:=Xk+1 modmod n;/n;/给给XkXk预分配一个值预分配一个值 for for j from 1j from 1 to to n n dodo if if NextValue(k)=true NextValue(k)=true thenthen cl:=cl+W(Xkcl:=cl+W(Xk- -1,Xk); break; 1,Xk); break; endifendif Xk:= Xk+1 Xk:= Xk+1 modmod n; /n; /重新给重新给XkXk分配值分配
