算法设计与分析.pptx

学习要求：学习要求：理解回溯法的理解回溯法的深度优先深度优先搜索策略搜索策略掌握用回溯法解题的掌握用回溯法解题的算法框架算法框架 (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回溯法回溯法ABCDEFGHIJKLMNO10111111000000110011回溯法回溯法-基本思想基本思想两种结点两种结点：活结点活结点和和死结点死结点ABDEC深度优先深度优先不能向纵深方向移动不能向纵深方向移动回溯法回溯法-0-1背包问题背包问题ABCDEFGHIKJLMNO10111111000000011回溯法回溯法-旅行商问题旅行商问题(TSP)北北京京西西安安徐徐州州上上海海广广州州HK成成都都回溯法回溯法1ABDCEGFHJIKMLNPOQ243344232443322完完全全图图123463010205459回溯法回溯法用约束函数在扩展结点处剪去不满足约束的子树；用约束函数在扩展结点处剪去不满足约束的子树；剪枝函数：剪枝函数：用限界函数剪去得不到最优解的子树。用限界函数剪去得不到最优解的子树。回溯法回溯法-0-1背包问题背包问题ABCDEFGHIJKLMNO10111111000000约约束束函函数数回溯法回溯法1ABDEHJIKNPOQ4342324CGFML234433221234630102054252530限界函限界函数剪枝数剪枝回溯法回溯法-步骤步骤 针对所给问题，定义问题的解空间；针对所给问题，定义问题的解空间；确定易于搜索的解空间结构；确定易于搜索的解空间结构；以深度优先方式搜索解空间，并在搜索以深度优先方式搜索解空间，并在搜索 过程中用剪枝函数避免无效搜索。过程中用剪枝函数避免无效搜索。回溯法回溯法-解空间树构造解空间树构造子集树：子集树：0-1背包问题背包问题 变长码变长码满足所有约束条件的解状态结点称为回答结点。满足所有约束条件的解状态结点称为回答结点。回溯法回溯法排序树排序树:旅行售货员问题旅行售货员问题(TSP)定长码定长码树中从根至叶结点的路径的集合树中从根至叶结点的路径的集合构成解空间。树的每个叶结点称构成解空间。树的每个叶结点称为一个解状态。为一个解状态。回溯法回溯法-搜索过程搜索过程搜索按深度优先策略从根开始搜索按深度优先策略从根开始,当搜索到当搜索到任一结点时任一结点时,判断该点是包否含问题的解，包判断该点是包否含问题的解，包含则继续向下深度优先搜索含则继续向下深度优先搜索,否则跳过该结否则跳过该结点以下的子树点以下的子树(剪枝剪枝),),向上逐级回溯。向上逐级回溯。例例1 1：0-1背包问题背包问题ABCDEFGHIJKLMNO1011111000000RS TU V W XYZ 27 28 2930 311PQ1010101010101010回溯法回溯法-练习练习(TSP)1ABDCEGFHJIKMLNPOQ243344232443322123463010205459666625回溯法回溯法-子集和问题子集和问题例例3：ABCDEFGHIJKLMNO1011111000000RS TU V W XYZ 27 28 2930 311PQ1010101010101010?5.2 装载问题装载问题回溯法回溯法当当n=3,c1=c2=50,w=10,40,40,若若w=20,40,40则无法将全部货箱装船则无法将全部货箱装船 回溯法回溯法等价于子集和问题等价于子集和问题 等价于划分问题等价于划分问题 回溯法回溯法若装载问题有解若装载问题有解,采用如下策略可得一个最优装载方案采用如下策略可得一个最优装载方案:(1)将第一艘轮船尽可能装满将第一艘轮船尽可能装满;(2)将剩余的货箱装到第二艘轮船上。将剩余的货箱装到第二艘轮船上。将第一艘船尽可能装满等价于如下将第一艘船尽可能装满等价于如下0-l背包问题背包问题:回溯法回溯法算法思路：算法思路：利用最优解性质进一步利用最优解性质进一步剪去不含最优解的子树。剪去不含最优解的子树。回溯法回溯法例例1 1ABCDEFGHIJKLMNO1011111000000RS TU V W1PQ1010101010101010Bestw=10Bestw=11回溯法回溯法使用约束函数和限界函数分别剪去不满足使用约束函数和限界函数分别剪去不满足约束的子树和不能产生最优解的子树，避约束的子树和不能产生最优解的子树，避免无效搜索。所以比穷举法效率高。免无效搜索。所以比穷举法效率高。回溯法为什么比穷举法效率高？回溯法为什么比穷举法效率高？练习：1.1.对字符集合对字符集合M=a,b,c,d,e,f，已知这些字符在文本中出现的频率，已知这些字符在文本中出现的频率分别为分别为18,10，23，15，62，35.1)1)画出字符集合画出字符集合M的最优前缀编码树。的最优前缀编码树。2)2)写出最优前缀编码写出最优前缀编码2.回溯法求解回溯法求解0-1背包问题背包问题 c=35,W=10,26,15,22,V=22,50,30,105.7 最大团问题最大团问题回溯法回溯法-最大团问题最大团问题12453(a)12(b)125(c)125(d)4回溯法回溯法-最大团问题最大团问题12453(a)12(b)125(c)1,2,5,1,4,5,2,3,5最大团问题：找到所含顶点数最多的团。最大团问题：找到所含顶点数最多的团。回溯法回溯法-最大团问题最大团问题12453(a)(b)131234(c)?回溯法回溯法-最大团问题最大团问题12453(a)24(b)最大独立集最大独立集 ：所含顶点数最多的独立集：所含顶点数最多的独立集 回溯法回溯法-最大团问题最大团问题12453(a)1234(b)512453(c)回溯法回溯法-最大团问题最大团问题12453(a)图图(a)、补图的最大独立集、补图的最大独立集1,2,5,2,3,5,1,4,5125(b)回溯法回溯法-最大团问题最大团问题约束条件：约束条件：目标函数限界：目标函数限界：剩余结点数目剩余结点数目 当前团的尺寸当前团的尺寸 已求出的最大团的尺寸已求出的最大团的尺寸 不是团不是团剪枝剪枝剪枝剪枝回溯法回溯法-最大团问题最大团问题ABCDEFHIJKL101111000RTU V W1PQ101S0101010M010GNO1001010Bestn=31243Bestn=3盖思里盖思里(Guthrie)“四色猜想四色猜想”阿佩尔阿佩尔(K.Appel)和哈肯和哈肯(W.Haken)科赫科赫(J.Koch)图着色问题图着色问题(GCP-Graph Coloring Problem)12543(a)12345rygb12543(b)123?4 4 4?图着色问题图着色问题(GCP-Graph Coloring Problem)图着色问题图着色问题(GCP)4(a)1235(1,2,3,1,3)图着色问题图着色问题(GCP)例例1 1123图着色问题图着色问题(GCP)A回溯法的效率分析回溯法的效率分析