算法分析与设计第5章课件.ppt

1、1、第五章，回溯法，学习要点，理解回溯法的深度优先搜索策略，掌握回溯法求解问题的算法框架，1)递归回溯，2)迭代回溯，3)子集树算法框架，4)树算法框架的安排，通过应用实例学习回溯法的设计策略，1)加载问题；2)批处理作业调度；3)N后问题；4)0-1背包问题；5)最大群体问题；6)旅行推销员问题，2。引言，有许多问题。当有必要找出它的解集或问什么解是满足某些约束的最佳解时，通常使用回溯法。回溯的基本方法是搜索，或者是一种组织良好并能避免不必要的搜索的穷举搜索方法。这种方法适用于解决一些具有大量组合的问题。回溯法根据深度优先策略从根节点搜索解空间树。当算法在解空间树中搜索任何一点时，首先判断该

2、节点是否包含问题的解：如果不包含，则跳过以该节点为根的子树搜索，逐层回溯到其祖先节点；否则，输入子树并根据深度优先策略继续搜索。3、5.1回溯法的算法框架。本节介绍了回溯法算法框架的相关问题：1 .问题2的解决空间。回溯法的基本思想。递归回溯4。迭代回溯5。子集树和树的排列。首先，应用回溯法求解问题时，应明确定义问题的解空间。问题的解空间应该包含至少一个问题的(最优)解。问题的解向量：回溯法希望问题的解可以表示为一个N元公式(x1，x2，xn)。解空间：对于一个问题的例子，其解向量满足约束的所有多元组构成该例子的解空间。注意：同样的问题可以用很多方式表达，其中一些更简单，需要更小的状态空间(更

3、少的存储和简单的搜索方法)。例如，对于有n个可选项目的0-1背包问题，其解空间由长度为n. 5，2的0-1个向量组成。回溯法的基本思想和步骤：(1)定义给定问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先的方式搜索解空间，并使用剪枝函数避免无效搜索。通用剪枝函数：使用约束函数在扩展节点处切断不满足约束的子树；用有界函数切掉不能得到最优解的子树。复杂性：回溯法解决问题的一个显著特点是问题的解空间是在搜索过程中动态生成的。在任何时候，算法只保存从根节点到当前扩展节点的路径。6、产生问题状态的基本方法，扩展节点：产生子节点的节点称为扩展节点活节点；一个由自身而不是其所有子节点产生的节点

4、被称为活节点死节点；由所有子节点产生的节点称为死节点深度优先问题状态生成方法：如果扩展节点R产生子节点C，它将被视为新的扩展节点。在完成子树C(以C为根的子树)的穷举搜索之后，R再次变成扩展节点，并且连续生成R的下一个子节点(如果有的话)。7.示例1 0-1背包问题，n=3，c=30，w=16，15，15，v=45，25，25问题描述：一名销售员想在几个城市销售商品。知道了城市之间的距离，他必须选择一条从他的住所出发的路线，经过每个城市一次，最后回到他的住所，这样总的距离最短。这个问题是(n-1)的NP完全问题！最优解(1，3，2，4，1)和最优值是25，9和3。递归回溯对解空间进行深度优先搜

5、索。因此，回溯法通常是用递归方法实现的。无效回溯(int t) if (tn)输出(x)；否则为(int i=f(n，t)；i0) if (f(n，t)=g(n，t)表示(int i=f(n，t)；in)输出(x)；否则为(int I=0；in)输出(x)；(int I=t；/到达叶节点更新最优解bestx，bestw返回；r-=wI；if(CW wIbestw) xI=0；/搜索右子树回溯(i1)； r=wI；，17，5.3批处理作业调度，1。问题描述，2。案例分析，3。算法描述，18。问题描述，给定一组n个作业J1，J2，Jn。每项工作都必须由机器1处理，然后由机器2处理。作业Ji要求机器

6、j的处理时间为tji。对于一个确定的作业计划，让Fji为作业I在机器j上完成处理的时间。所有作业在机器2上处理的时间之和称为作业计划的完成时间。批处理作业调度问题要求对于给定的n个作业，应制定出最佳的作业调度方案以最小化完成时间。19，2，案例分析，这三个作业的六种可能的调度方案是1，2，3；1，3，2；2，1，3；2，3，1；3，1，2；3，2，1；它们相应的完成时间分别是19、18、20、21、19和19。最佳调度方案是1、3和2，它们的完成时间之和是18。20，3。算法描述，无效流图：回溯(int I) if(I n) for(int j=1；j f1)？F2I-1: f1)Mxj2；f

7、=F2I；if (f bestf) Swap(xi，xj)；回溯(i1)；交换(xi，xj)； f1-=Mxj1；f-=F2I；，解空间：树的排列复杂度：T(n)=O(n！)，21，5.5 n，1。问题描述2。问题分析3。算法描述22。1.问题描述。没有被对方攻击的n个皇后被放置在nn格的棋盘上。根据国际象棋的规则，女王可以攻击同一行、列或对角线上的棋子。n后的问题相当于把n个皇后放在nn格的棋盘上，任何两个皇后都不在同一行、同一列或同一条对角线上。23，2，问题分析，解向量：(x1，x2，xn)显式约束：Xi=1，2，n隐式约束：1)不同的列：xixj 2)不在同一对角线上：| I-j |

8、| Xi-xj jn)和；(int I=1；/到达叶节点更新最优解bestx，bestp返回；r-=wI；如果(cw wi bestp)/输入右子树xI=0；回溯(i1)；，解空间：子集树可行性约束函数：wixiC上界函数：Bound()算法：little，26，上界函数，bound(int i)/计算上界Typew分裂=C-CW；/剩余容量Typep b=cp/加载文章，同时(I n)按单位权重值的降序/到达叶节点(int j=1；最佳)/输入右子树xI=0；回溯(i1)； ，32。第四，进一步的改进和适当的搜索顺序可以使上界函数发挥更有效的作用。例如，在搜索之前，顶点可以从最小到最大排序。

9、从某种意义上说，这相当于给回溯法增加灵感。33，5.8 M图的着色问题，1。基本概念2。问题分析3。算法描述4。复杂性分析。1.基本概念，给定G和M不同颜色的无向图。用这些颜色给图G的顶点着色，每个顶点都用一种颜色着色。有没有一种着色方法可以使G中每条边的两个顶点有不同的颜色？这个问题就是图的m-可着色决策问题。如果一个图至少需要m种颜色才能使图的每条边所连接的两个顶点具有不同的颜色，那么这个数m就叫做图的颜色数。寻找图的色数m的问题称为图的m-可着色优化问题。35，2。问题分析，解向量：(x1，x2，xn)表示顶点I的颜色xi可行性约束函数：顶点I的颜色不会与已着色的相邻顶点的颜色重复。36

10、，3。算法描述，无效颜色：回溯(int t) if(TN) sum；对于(int I=1；i=n。I)cout xI；cout endl否则为(int I=1；I=m；I) xt=I；如果(Ok(t)回溯(t1)； bool color : ok(int k)/检查颜色可用性 for(int j=1；j=n。j)如果(akj=1)，37。4.复杂性分析表明，图m着色问题的解空间树的内部节点数为mi(0in-1)。对于每个内部节点，在最坏的情况下，用ok检查当前扩展节点的每个子节点的颜色可用性需要0(Mn)。因此，回溯法的总时间成本是mi(Mn)=nm(Mn-1)/(m-1)=o(nmn)(0I

11、n-1)，38，5.9旅行商问题，无效回溯(int I) if (I=n) if(。=noedge，39，5.9旅行商问题，解空间：排列树复杂度分析：算法回溯可能需要更新当前最优解O(n-1)在最坏的情况下！)次，每次更新bestx需要O(n)，因此整个算法的计算时间复杂度为O(n！).本节的要点如下：1 .影响回溯算法效率的因素2。重排原理3。回溯算法的效率。概率方法。影响回溯算法效率的因素。从前面具体例子的讨论中可以看出，回溯算法的效率在很大程度上取决于以下因素：(1)生成xk的时间；(2)满足显式约束的xk值的数量；(3)计算约束函数约束的时间；(4)计算上界函数的上界时间；(5)满足约束函数和上界函数约束的所有xk的个数。一个好的约束函数可以显著减少生成的节点数。然而，这种约束函数通常是计算密集型的。因此，在选择约束函数时，通常会在生成的节点数和约束函数的计算量之间进行权衡。42，2。重排原理。对于许多问题，在搜索启发式时，选择xi的值的顺序是任意的。在其他条件相等的前提下，让具有最不理想值的xi优先。在图(a)中，如果从第一层切下一个子树，那么应该同时考虑的所有分支中会有12个分支被删除。至于图(b)，虽然从第一层中切掉了一个子树，但是从应该考虑的分支中只删除了八个分支。前者的效果明显优于后者。(a)、(b)、43。选择了回溯法的效率和解空间的结构。影响回