1、第五章 回溯法,学习要求：,理解回溯法的深度优先搜索策略掌握用回溯法解题的算法框架 (1)子集树算法框架 (2)排列树算法框架 通过应用范例学习回溯法的设计策略,回溯法-问题的解空间,0-1背包问题：,其解空间是：,(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1),用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少应包含问题的一个(最优)解。,C=30,W=16,15,15,V=45,25,25,回溯法,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,110,011,回溯法-基本思想,两种结点：活
2、结点和死结点,深度优先,不能向纵深方向移动,回溯法-0-1背包问题,A,B,C,D,E,F,G,H,I,K,J,L,M,N,O,1,0,1,1,1,1,1,1,0,0,0,0,0,0,011,回溯法-旅行商问题(TSP),北京,西安,徐州,上海,广州,HK,成都,回溯法,1,完全图,59,回溯法,用约束函数在扩展结点处剪去不满足约束的子树；,剪枝函数：,用限界函数剪去得不到最优解的子树。,回溯法-0-1背包问题,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,1,0,1,1,1,1,1,1,0,0,0,0,0,0,约束函数,回溯法,1,A,B,D,E,H,J,I,K,N,P,O,Q
3、,4,3,4,3,2,2,25,30,限界函数剪枝,回溯法-步骤, 针对所给问题，定义问题的解空间；, 确定易于搜索的解空间结构；, 以深度优先方式搜索解空间，并在搜索 过程中用剪枝函数避免无效搜索。,回溯法-解空间树构造,子集树：,0-1背包问题,变长码,满足所有约束条件的解状态结点称为回答结点。,回溯法,排序树:,旅行售货员问题(TSP),定长码,树中从根至叶结点的路径的集合构成解空间。树的每个叶结点称为一个解状态。,回溯法-搜索过程,搜索按深度优先策略从根开始, 当搜索到任一结点时,判断该点是包否含问题的解，包含则继续向下深度优先搜索,否则跳过该结点以下的子树(剪枝),向上逐级回溯。,例
4、1：0-1背包问题,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,1,0,1,1,1,1,1,0,0,0,0,0,0,R,S,T,U,V,W,X,Y,Z,27,28,29,30,31,1,P,Q,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,回溯法-练习(TSP),1,A,B,D,C,E,G,F,H,J,I,K,M,L,N,P,O,Q,4,4,3,3,2,2,59,66,25,回溯法-子集和问题,例3：,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,1,0,1,1,1,1,1,0,0,0,0,0,0,R,S,T,U,V,W,X,Y,Z,27,28,
5、29,30,31,1,P,Q,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,?,5.2 装载问题,回溯法,当n=3, c1=c2=50, w=10, 40, 40,若w=20, 40, 40,则无法将全部货箱装船,回溯法,等价于子集和问题,等价于划分问题,回溯法,若装载问题有解, 采用如下策略可得一个最优装载方案:,(1)将第一艘轮船尽可能装满; (2)将剩余的货箱装到第二艘轮船上。,将第一艘船尽可能装满等价于如下0-l背包问题:,回溯法,算法思路：,利用最优解性质进一步剪去不含最优解的子树。,回溯法,例1,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,1,0,
6、1,1,1,1,1,0,0,0,0,0,0,R,S,T,U,V,W,1,P,Q,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,Bestw=10,Bestw=11,回溯法,使用约束函数和限界函数分别剪去不满足约束的子树和不能产生最优解的子树，避免无效搜索。所以比穷举法效率高。,回溯法为什么比穷举法效率高？,练习：,对字符集合M=a,b,c,d,e,f，已知这些字符在文本中出现的频率分别为18, 10，23，15，62，35. 1) 画出字符集合M的最优前缀编码树。 2) 写出最优前缀编码,2.回溯法求解0-1背包问题 c=35,W=10,26,15,22,V=22,50,30,
7、10,5.7 最大团问题,回溯法-最大团问题,回溯法-最大团问题,1,2,5,1,4,5,2,3,5,最大团问题：找到所含顶点数最多的团。,回溯法-最大团问题,?,回溯法-最大团问题,最大独立集 ：所含顶点数最多的独立集,回溯法-最大团问题,5,回溯法-最大团问题,图(a)、补图的最大独立集,1,2,5,2,3,5,1,4,5,回溯法-最大团问题,约束条件：,目标函数限界：,剩余结点数目,回溯法-最大团问题,A,B,C,D,E,F,H,I,J,K,L,1,0,1,1,1,1,0,0,0,R,T,U,V,W,1,P,Q,1,0,1,1,0,1,0,1,盖思里(Guthrie),图着色问题(GCP-Graph Coloring Problem),1,2,3,4,5,1,2,3,?,4,4,4,?,图着色问题(GCP-Graph Coloring Problem),图着色问题(GCP),(1,2,3,1,3),图着色问题(GCP),例1,图着色问题(GCP),A,回溯法的效率分析,
