【精品】课件---第5章 回溯法.ppt

第5章 回溯法 学习要点 理解回溯法的深度优先有哪些信誉好的足球投注网站策略。 掌握用回溯法解题的算法框架 （1）递归回溯 （2）迭代回溯 （3）子集树算法框架 （4）排列树算法框架 通过应用范例学习回溯法的设计策略。 （1）装载问题； （2）批处理作业调度； （3）符号三角形问题 （4）n后问题； （5）0-1背包问题； （6）旅行售货员问题 回溯法的直观印象 （1）回溯法有“通用的解题法”之称。 用它可以系统地有哪些信誉好的足球投注网站一个问题的所有解或最优解。回溯法是一个既带系统性又带有跳跃性的有哪些信誉好的足球投注网站算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发，有哪些信誉好的足球投注网站解空间树。 回溯法的直观印象 （2）回溯法在问题的解空间树中，按深度优先策略，从根结点出发有哪些信誉好的足球投注网站解空间树。算法有哪些信誉好的足球投注网站至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的有哪些信誉好的足球投注网站，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略有哪些信誉好的足球投注网站。 回溯法的直观印象 （3）回溯法在用来求问题的所有解（或最优解）时，要回溯到根，且根结点的所有子树都已被有哪些信誉好的足球投注网站遍才结束。而在求任一解时，只要有哪些信誉好的足球投注网站到一个解就结束。这种以深度优先的方式系统地有哪些信誉好的足球投注网站问题的解的算法称为回溯法，它适合于解一些组合数较大的问题。 回溯法：任务描述 问题描述：假定问题的解能表示成一个n元组(x1,…,xn),其中xi取自某个有穷集si 解空间：所有这些n元组的集合构成问题的解空间。 回溯法：任务描述 并非解空间中的所有元素都是问题的解 存在性问题：求满足某些条件（约束条件）的一个或全部元组，如果不存在这样的元组，算法应返回No。满足约束条件的元组称为问题的可行解（Feasible Solution） 优化问题：给定一组约束条件，在满足约束条件的元组中求使某目标函数达到最大（小）值的元组。满足目标函数的元组称为问题的最优解（Optimal Solution） 剪枝函数和回溯法 问题的解空间 问题的解空间 例1 0-1背包问题 n=3, C=30, w={16, 15, 15}, v={45, 25, 25} 开始时，Cr=C=30，V=0，A为唯一活结点，也是当前扩展结点 扩展A，先到达B结点 Cr=Cr-w1=14，V=V+v1=45 此时A、B为活结点，B成为当前扩展结点 扩展B，先到达D Crw2，D导致一个不可行解，回溯到B 再扩展B到达E E可行，此时A、B、E是活结点，E成为新的扩展结点 扩展E，先到达J Crw3，J导致一个不可行解，回溯到E 再次扩展E到达K 由于K是叶结点，即得到一个可行解x=(1,0,0)，V=45 K不可扩展，成为死结点，返回到E E没有可扩展结点，成为死结点，返回到B B没有可扩展结点，成为死结点，返回到A 例1 0-1背包问题 n=3, C=30, w={16, 15, 15}, v={45, 25, 25} A再次成为扩展结点，扩展A到达C Cr=30，V=0，活结点为A、C，C为当前扩展结点 扩展C，先到达F Cr=Cr-w2=15，V=V+v2=25，此时活结点为A、C、F，F成为当前扩展结点 扩展F，先到达L Cr=Cr-w3=0，V=V+v3=50 L是叶结点，且5045，得到一个可行解x=(0,1,1)，V=50 L不可扩展，成为死结点，返回到F 再扩展F到达M M是叶结点，且2550，不是最优解 M不可扩展，成为死结点，返回到F F没有可扩展结点，成为死结点，返回到C 例1 0-1背包问题 n=3, C=30, w={16, 15, 15}, v={45, 25, 25} 再扩展C到达G Cr=30，V=0，活结点为A、C、G，G为当前扩展结点 扩展G，先到达N，N是叶结点，且2550，不是最优解，又N不可扩展，返回到G 再扩展G到达O，O是叶结点，且050，不是最优解，又O不可扩展，返回到G G没有可扩展结点，成为死结点，返回到C C没有可扩展结点，成为死结点，返回到A A没有可扩展结点，成为死结点，算法结束，最优解X=(0,1,1)，最优值V=50 例1 0-1背包问题 例2 旅行售货员问题 问题描述：某售货员要到若干城市去推销商品，已知各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。 该问题是一个NP完全问题， 有(n-1)!条可选路线。 最优解(1,3,2,4,1)， 或( 1,4,2,3,1)， 59、66、25、66、25、59 最优值25 在第四章中,我们用动态规划的方法讨论了背包问题。这里，我们将用回溯的方法求解背包问题。 问题的解空间：由各分量 xi(取值0或1）的2n个不同的n元向量组成。与子集和数问题的解空间相同。也用树结构表示（满二叉树）。