计算机算法设计与分析回溯法.ppt

1、了解第1、5章回溯、第2、学习要点回溯方法的深度优先搜索策略。通过应用回溯方法求解问题的算法框架(1)迭代回溯(2)迭代回溯(3)子集树算法框架(4)阵列树算法框架、3、样本，学习回溯方法的设计策略。(1)装载问题(2)调度批处理作业；(3)符号三角形问题(4)n后问题；(5)0-1背包问题；(6)最大群体问题；(7)图中的M着色问题(8)旅行推销员问题(9)圆阵列问题(10)电路板阵列问题(11)连续邮资问题，4回溯法的基本方法是通过搜索或组织方式来避免不必要的搜索的彻底搜索方法。牙齿方法适用于解决组合数相当多的问题。回溯方法根据问题的解决空间树中的深度优先策略，在根节点中搜索解决空间树。算

2、法搜索解决方案空间树的任意位置时，首先确定该节点是否包含问题的解决方案。如果确实不包含，请跳过对节点为根的子树的搜索，并返回到父节点。否则，进入子树并根据深度优先级策略继续搜索。回溯方法，5，问题的解决空间，问题的解决向量：回溯方法希望一个问题的解决用N元表达式(X1，X2，XN)表示。展示约束：限制元件Xi的值。隐式约束：为了解决问题，在徐璐其他零部件之间应用的约束。分析空间：在问题的一个实例中，分析向量满足显式约束的所有多组构成了该实例的分析空间。注意：同一问题可以有多个茄子表示法，一些表示法更简单，所需表示法的状态空间更小(存储容量更小，检索方法更简单)。n=3点0-1背包问题被称为完全

3、二叉树表示的解空间，6，生成问题状态的基本方法，扩展节点：扩展节点：被称为扩展节点活动节点：创建了自己但儿子尚未全部创建的节点称为活动节点：所有儿子已经创建的节点称为死节点深度优先级问题状态生成方法。彻底搜索完子树C (C根子树)后，将R更改回扩展节点，继续生成R的下一个儿子(如果有)宽度优先问题状态生成方法。扩展节点回溯方法，直到扩展节点成为死节点：必须继续利用边界函数，以避免生成无法生成最佳解决方案的问题状态。具有极限函数的深度优秀教师成法定义了回溯方法，7，回溯方法的基本思想，(1)给定问题的解决空间。(2)确定易于搜索的解决方案空间结构。(3)以深度优先级搜索解析空间，在搜索过程中使用

4、茄子函数防止错误搜索。典型的茄子修剪函数：使用约束函数从扩展节点中剪切不符合约束条件的子树。使用边界函数截断无法获得最佳解决方案的子树。用回溯方法解决问题的一个突出特征是在搜索过程中动态引起问题的解决空间。在任何时候，算法仅存储从根节点到当前扩展节点的路径。如果解析空间树中从根节点到分叶节点的最长路径长度为h(n)，则回溯方式所需的计算空间通常为O(h(n)。要显式保存整个解决方案空间，请选择O(2h(n)或O(h(n)！)内存空间。8，递归回溯，回溯方法对解析空间进行深度优先搜索，因此通常使用递归方法实现回溯方法。void back track(int)if(TN)output(x)；Els

5、e for (int i=f(n，t)；I=g(n，t)；I)XT=h(I)；可以使用If(约束(t)，9，迭代回溯，树的非迭代深度优先遍历算法，将回溯方法表示为非迭代过程。，void iterativeBacktrack()int t=1；While (t0) if (f (n，t)=g (n，t) for (int I=f (n，t)；I=g(n，t)；I)XT=h(I)；If (constraint(t)，10，子集树和排序树，O(2n)遍历子集树的计算时间，O(n)遍历排序树！)时间计算，void back track(int t)if(TN)output(x)；else for(in

6、t I=0)；I=1；I)XT=I；If(普通(t)后方轨道(t1)；void back track(int)if(TN)output(x)；else for(int I=t；I=n；I) swap(xt，Xi) : If(常规(t)后方轨道(t1)；Swap(xt，Xi):11，装载问题，共N个集装箱应分别装载C1和C2的船只，其中集装箱I的重量为wi，装载问题应确保牙齿集装箱装载在两艘牙齿的船只上的合理装载方案。如果存在，请查找装载方案。解决了指定的装载问题后，使用以下策略可以轻松地证明可以获得最佳装载方案：(1)先把第一艘轮船尽量装满。(2)将剩余容器安装在第二艘船上。尽可能多地填充第一

7、艘船，使其与选择整个容器的子集相同，从而使该子集的集装箱重量总和最接近。由此可见，装载问题与以下特殊的0-1背包问题相同。设计了用回溯方法求解挂载问题的O(2n)计算时间算法。在某些情况下，牙齿算法优于动态编程算法。12，装载问题，空间解决方法：子集树可行性约束函数(选择当前要素):父函数(渡边杏选择当前要素):当前装载重量CW剩馀容器的重量R当前最佳装载重量bestw，void backtrack (int i) /搜索层次Ir-=wi；if(CW wi bestw)Xi=0；/搜索右侧子树back track(i1)；R=wi，13，批处理作业调度，给定N个作业的集合J1，J2，Jn。每个

8、作业必须先在机器1上处理，然后在机器2上处理。作业Ji必须是机器J的处理时间tji。对于已确认的作业调度，Fji设置是作业I在系统J中完成处理的时间。要解决所有作业在系统2上完成处理的时间和称为作业调度的完成时间和批处理作业调度问题，必须为指定的N个作业开发最佳作业调度方案，以将完成时间和最小化。牙齿三茄子操作的6茄子计划方案为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。14，调度批处理作业，解决空间：阵列树，void flowshop 3360: back

9、track(int I)if(I n)for(int j=1；J f1)？f2i-13360 f1)mxj 2；F=f2iIf (f bestf) Swap(xi，XJ)；back track(I 1)；Swap(xi，XJ):F1-=MX J1；f-=f2i；class flowshop friend flow (int * *，int，int)；private 3360 void back track(Int I):Int * * M，/每个作业所需的处理时间*x，/当前作业调度*bestx，/当前最佳作业调度*f2，15，符号三角形问题，-，下图是由14个“”和14个“-”组成的符号三角

10、形。两个东湖下面都是“”，两个两湖下面都是“-”。通常，符号三角形的第一行有n个符号。符号三角形问题需要计算多个不同的符号三角形，以使给定N的“”和“-”数相等。16，符号三角形问题，解决向量：符号三角形的第一行表示为N元组x1:n。可行性约束函数：当前符号三角形中包含的“”数和“-”数不超过n*(n 1)/4未解决的判断。n*(n 1)/2是奇数，void triangle :3360 back track If(TN)sum；else for(int I=0)；I2；I)p1t=I；count=I；for(int j=2；j=t；j)pjt-j 1=pj-1t-j 1pj-1t-j 2；c

11、ount=pjt-j 1；back track(t 1)；for(int j=2；j=t；j)count-=pjt-j 1；count-=I；-复杂性分析可计算性约束O(n)时间，最坏情况下为O(2n)节点可计算性约束，解释符号三角形问题的回溯算法所需的计算时间为O(n2n)，17，N以后的问题，在nn格的棋盘上放置N个不受徐璐攻击的皇后。根据国际象棋的规则，皇后可以攻击同一排或同一排或同一斜线上的围棋。N后的问题等于在N坎的棋盘上放置N个皇后。两位皇后都不在同一排或同一排或同一排的斜线上。(阿尔伯特爱因斯坦，Northern Exposure(美国电视电视剧)，18，矢量解释：(x1，x2，

12、xn)显示约束：xi=1，2，n隐含约束：else for(int I=1；I=n；I)XT=I；if(Place(t)back track(t 1)；19，0-1背包问题，空间分析：子集树可行性约束函数：上限函数：template Typep knap 3360: bound(int I)/上限typewcleft=c-计算/按物料单位重量值降序装入物料While(I=n，20，最大组问题，给定无向图G=(V，e)。如果有UV，任意U，vU有(U，v)E，则U称为G的完整子图形。G的整个子图U是G的组，仅当U不包含在G的较大的整个子图中时。g的最大组表示g包含的顶点数最多的组。如果UV在任意

13、U，vU上有(U，v)E，则U称为G的空图形。G的空子图形U是G的独立集，仅当U不包含在G的较大空图形中时。g的最大独立集是g包含的顶点数最多的独立集。无向图G=(V，E)的补充图G=(V1，E1)由V1=V定义，(u，v)E1仅由(u，v)E定义。u是g的最大组，仅在u是g的最大独立集时可用。21，最大组问题，解决方案空间：子集树可行性约束函数：从顶点I到选定顶点集中的每个顶点都有边连接。上限函数：有足够的可选顶点，算法可以在右侧子树中找到较大的组。void clique 3360: back track(int I)/最大组计算if (i n) /到达叶节点for(int j=1；J be

14、stn) /进入右侧子树Xi=0；back track(I 1)；复杂性分析最大组问题的回溯算法backtrack所需的计算时间为O(n2n)。22，进一步改进，选择适当的搜索顺序，更有效地使用上限函数。例如，在搜索之前，可以按从小到大的顺序排列顶点。这在某种意义上等同于启发回溯方法。Si=vi、vi 1、定义vn，然后定义Sn、Sn-1、然后查找S1的解决方案。因此，可以得到更精确的上限函数，如果cn Si=max，则截断树枝。此外，如果找到从Si 1到Si的较大组，则VI必须属于找到的组。此时存在Si=Si 1牙齿。否则，存在SI=SI 1牙齿。因此，如果更新了max中的值，则可以看到找到

15、了最大值，不再需要向下搜索。23，图中的M着色问题，给定的无方向连接图G和M种不同的颜色。使用牙齿颜色将图G中的每个顶点分别着色为一种茄子颜色。g的每条边上的两个顶点是否有不同颜色的着色方法。牙齿问题是图的M颜色确定问题。如果图需要最小M茄子颜色以使连接到图每条边的两个顶点徐璐具有不同的颜色，则牙齿数M称为该图的颜色数。寻找图的颜色数M的问题称为图的M颜色最优化问题。24，矢量解释：(x1，x2，xn)表示顶点I的颜色Xi可行性约束函数。顶点I与相邻着色顶点颜色不重复。，图m着色问题，void color :3360 back track(int)if(TN)sum；for(int I=1)；I=n；I)cout Xi；Cout endlelse for(int I=1；I=m；I)XT=I；If (ok (t)回溯(t1)；bool color 33603360 ok(int k)/检查颜色可用性for(int j=1；j=n；J) if (akj=1)，复杂性分析图M可着色问题的分析空间树的内部节点数针对每个内部节点。在最坏的情况下，使用ok检