《算法设计与分析第五章.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析第五章.ppt（46页珍藏版）》请在装配图网上搜索。
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
3、,Q,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
5、,27,28,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
6、,O,1,0,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=
7、22,50,30,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,回溯法的效率分析,
算法设计与分析第五章.ppt
