算法设计与分析第五章1演示课件.ppt

回溯法-最大团问题 1 2 4 5 3 (a) 1 2 (b) 1 2 5 (c) {1,2,5},{1,4,5},{2,3,5} 最大团问题：找到所含顶点数最多的团。 回溯法-最大团问题 1 2 4 5 3 (a) (b) 1 3 1 2 3 4 (c) ? 回溯法-最大团问题 1 2 4 5 3 (a) 2 4 (b) 最大独立集 ：所含顶点数最多的独立集 第五章 回溯法 学习要求： ?理解回溯法的深度优先搜索策略 ?掌握用回溯法解题的算法框架 (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 1 0 1 1 1 1 1 1 0 0 0 0 0 0 110 011 回溯法-基本思想 两种结点：活结点和死结点 A B D E C 深度优先 不能向纵深方向移动 回溯法-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 A B D C E G F H J I K M L N P O Q 2 4 3 3 4 4 2 3 2 4 4 3 3 2 2 完全图 1 2 3 4 6 30 10 20 5 4 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 4 3 4 2 3 2 4 C G F M L 2 3 4 4 3 3 2 2 1 2 3 4 6 30 10 20 5 4 25 30 限界函数剪枝 回溯法-步骤 ? 针对所给问题，定义问题的解空间； ? 确定易于搜索的解空间结构； ? 以深度优先方式搜索解空间，并在搜索 过程中用剪枝函数避免无效搜索。 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 2 4 3 3 4 4 2 3 2 4 4 3 3 2 2 1 2 3 4 6 30 10 20 5 4 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 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 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) 写出最优前缀编码