第5章回溯法.ppt

《第5章回溯法.ppt》由会员分享，可在线阅读，更多相关《第5章回溯法.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5 5章章 回溯法回溯法1理解回溯法的深度优先搜索策略。理解回溯法的深度优先搜索策略。掌握用回溯法解题的算法框架掌握用回溯法解题的算法框架通过应用范例学习回溯法的设计策略。通过应用范例学习回溯法的设计策略。学习要点学习要点2回溯算法的基本思想回溯算法也叫试探法，它是一种利用试探回溯算法也叫试探法，它是一种利用试探或回溯或回溯(Backtracking)的搜索技术求解的方的搜索技术求解的方法。法。回溯算法在问题的解空间中回溯算法在问题的解空间中使用一种可以避免不必要搜索的穷举式搜索法，可以系统的搜索一个问题的所有解或任一解。3回溯法的应用领域广泛对于许多问题，当需要找出问题的全部解或者找出满

2、足某些约束条件的（最优）解时，往往要使用回溯法。回溯法有“通用的解题法通用的解题法”之称。4回溯法的搜索方式通常将问题的解空间组织成树或图的形式将问题的解空间组织成树或图的形式，使得回溯法能方便地搜索整个解空间。回溯法在问题的解空间树中，按深度优先按深度优先策略（或先序遍历，根策略（或先序遍历，根-左左-右顺序），从右顺序），从根结点出发搜索解空间树根结点出发搜索解空间树。注意：这棵解空间树不是遍历前预先建立这棵解空间树不是遍历前预先建立的，而是隐含在遍历过程中的，而是隐含在遍历过程中。5回溯法的搜索方式为了避免不必要的搜索，算法搜索至解空为了避免不必要的搜索，算法搜索至解空间树的任意一点时，

3、间树的任意一点时，先判断该结点是否包先判断该结点是否包含问题的解含问题的解。如果肯定不包含，则跳过对该结点为根的如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略否则，进入该子树，继续按深度优先策略搜索。搜索。65.1回溯法的算法框架1.问题的解空间问题的解向量：回溯法希望一个问题的问题的解向量：回溯法希望一个问题的解能够表示成一个解能够表示成一个n元式元式(x1,x2,xn)的形式。的形式。如，对于有如，对于有n个可选择物品的个可选择物品的0-1背包问题，背包问题，其解空间由长度为其解空间由长度为n的的

4、0-1向量组成。向量组成。对于对于n元式元式(x1,x2,xn)形式的解：形式的解：对分量对分量xi的取值约束条件，的取值约束条件，xi=0 or 1。75.1回溯法的算法框架1.问题的解空间解空间：对于问题的一个实例，满足约解空间：对于问题的一个实例，满足约束条件的所有多元组束条件的所有多元组(解向量解向量)，构成了，构成了该实例的一个解空间。该实例的一个解空间。85.1回溯法的算法框架1.问题的解空间0-1背包问题的解空间包含了对变量的所有可能的0-1赋值，向量总数有2n个。如，当n=3时，0-1背包问题的解空间为(1,1,1,),(1,1,0,),(1,0,1,),(0,1,1,),(1

5、,0,0,),(0,1,0,),(0,0,1,),(0,0,0,).共23个解向量。91.问题的解空间在此将解空间组织成树将解空间组织成树的形式。对于n=3时的0-1背包问题，其解空间用一棵完全二叉树表示，如下图：解空间树的第解空间树的第i层到第层到第i+1层边上的标号给出了变量层边上的标号给出了变量xi的值。的值。从树根到叶的任一路径表示解空间中的一个元素从树根到叶的任一路径表示解空间中的一个元素(解向量解向量)。例如：从跟结点例如：从跟结点A到结点到结点K的路径对应于解空间中的元素的路径对应于解空间中的元素(1,0,0)。105.1回溯法的算法框架2.回溯法的基本思想用回溯法解题的一个显著

6、特征是在搜索在搜索过程中动态产生问题的解空间过程中动态产生问题的解空间。确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索（动态产生）整个解空间。115.1回溯法的算法框架2.回溯法的基本思想从开始结点（根结点）出发，这个开始结点就成为一个活结点，同时也成为当前的扩展结点。活结点活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点。扩展结点扩展结点:一个正在产生儿子的结点称为扩展结点。125.1回溯法的算法框架2.回溯法的基本思想在当前扩展结点处，搜索向纵深方向移在当前扩展结点处，搜索向纵深方向移至一个新结点至一个新结点。这个新结点就成为一个新的活结点，并

7、成为当前扩展结点。如果在当前扩展结点处不能再向纵深方如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点向移动，则当前扩展结点就成为死结点。死结点死结点:一个所有儿子已经全部产生的结点称做死结点。135.1回溯法的算法框架2.回溯法的基本思想当前扩展结点成为死结点时，应往回移当前扩展结点成为死结点时，应往回移动（回溯）至最近的一个活结点处动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空回溯法即以这种工作方式递归地在解空间中搜索间中搜索，直至找到所要求的解，或解空间中已无活结点时终止。142.回溯法的基本思想例1：0-1背包以n

8、=3时的0-1背包为例，考虑如下实例：w=16,15,15,p=45,25,25,c=30。从其解空间树的根结点开始搜索其解空间。开始时，根结点A是唯一的活结点，也是当前扩展结点。在当前扩展结点A处，可纵深移至B或C。152.回溯法的基本思想例1：0-1背包在当前扩展结点A处，可纵深移至B或C。选择先移至B，即选取物品w1，此时，A、B均为活结点，B成为当前扩展结点。在B处剩余背包容量是r=30-16=14，获取价值45。从B可纵深移至D或E，先考虑移至D，但现仅有的背包容量容不下物品w2，故移至D导致一个不可行解。而从B移至E不占用背包容量，因而可行。从而我们选择移至E。此时E成为新的扩展结

9、点。162.回溯法的基本思想例1：0-1背包此时，A、B和E是活结点。在E处容量仍为14，所得价值仍为45。从E可以移至J和K。移至J会导致一个不可行解，而移向K是可行的，于是移至K，K成为新的扩展结点。由于K是一个叶结点，所以我们得到一个可行解(1,0,0),v=45。172.回溯法的基本思想例1：0-1背包由于从K已无法纵深扩展，故K成为一个死结点，所以返回（回溯）至E（离K最近的一个活结点）。而E也没有可扩展的结点，也成为了死结点。接下来，再继续回溯，返回至B处，同样B也成为死结点。再返回A，从A可扩展移至C。从A移至C，r=30,获取价值0。182.回溯法的基本思想例1：0-1背包从C

10、可移至F或G，令先移至F，则F成为新的扩展结点，此时有活结点A,C,F。在F有r=30-w2=15,获取价值25。从F向纵深移至L处，有r=0,获取价值25+25=50。L是叶结点，即获得一可行解，又获取了至今最高价值，因此记录该可行解。192.回溯法的基本思想例1：0-1背包L不可扩展，返回F处。按此方式继续搜索，可搜索遍整个解空间可搜索遍整个解空间。搜索结束后找到的最好解是相应0-1背包问题的最优解。202.回溯法的基本思想例2：旅行售货员问题旅行售货员问题：某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个一条从驻地出发，经过每个城市一次，最

11、后回到驻地的路线，使总的路城市一次，最后回到驻地的路线，使总的路程最短（或旅费最少）程最短（或旅费最少）。该问题可以用图论的语言来进行形式化描述。212.回溯法的基本思想例2：旅行售货员问题设G=(V,E)是一个带权图。图中各边的费用（权）为一正数。图中一条周游路线是包括V中每个顶点在内的一条回路。其费用就是该路线上所有边的费用总和。所谓旅行售货员问题就是要在图G中找出一条有最小费用的周游路线。222.回溯法的基本思想例2：旅行售货员问题给定一个有n个顶点的带权图G，旅行售货员问题就是要找出G的费用（权）最小的周游路线。左图是一个4顶点无向带权图。如：顶点序列1,2,4,3,1；1,3,2,4

12、,1和1,4,3,2,1是该图中3条不同的周游路线。232.回溯法的基本思想例2：旅行售货员问题该问题的解空间可以该问题的解空间可以组织成一棵树。组织成一棵树。树的第树的第i层到第层到第i+1层层的边上的标号给出的边上的标号给出xi的值（的值（城市标号）。城市标号）。从树的根结点到任一从树的根结点到任一叶结点的路径定义了叶结点的路径定义了图图G的一条周游路线。的一条周游路线。如右图为当如右图为当n=4时这时这种树结构的示例。种树结构的示例。242.回溯法的基本思想例2：旅行售货员问题从根结点A到叶结点L的路径上边的标号组成了一条周游路线1,2,3,4,1。图G的每一条周游路线都恰好对应于解空间

13、树中一条从根到叶的路径。因此，该解空间树中叶子个数为(n-1)!。（即元素2,3,4的全排列个数）252.回溯法的基本思想例2：旅行售货员问题对于图G，用回溯法找最小费用周游路线时，从A出发，搜索至B,C,F,L。在叶子L处记录找到的周游路线1,2,3,4,1,该周游路线费用为59。从L处返回最近活结点F，F已无可扩展结点，因此回到C。从C可移至G后又到达M，得到周游路线1,2,4,3,1,费用66，这个费用不比已有路线1,2,3,4,1的费用小，因此舍弃该结点。262.回溯法的基本思想例2：旅行售货员问题算法又依次返回结点G,C,B。从结点B又可以继续搜索D,H,N.在N处，相应的周游路线1

14、,3,2,4,1的费用为25。是迄今为止找到的最好的一条周游路线。依次继续搜索遍整个解空间，可找到两条最小费用周游路线：13241和14231272.回溯法的基本思想在用回溯法搜索解空间树时，通常采用两种策略来避免无效搜索，提高回溯法的搜索效率。a.用约束函数约束函数在扩展结点处剪去不满足约束的子树；b.用限界函数限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数剪枝函数。282.回溯法的基本思想如在解0-1背包问题（在有限容量内得到最多价值）的回溯法中，用剪枝函数减去导致不可行解（超出容量限制）的子树。又如，在旅行售货员问题的回溯法中，如果从根结点到当前扩展结点处的部分周游路线的费用已

15、超过当前找到的最少的周游路线费用，则可断定该结点为根的子树中不含最优解，即可减去该子树。约束约束函数函数限界限界函数函数292.回溯法的基本思想运用回溯法解题通常包含以下三个步骤：(1)定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。303、递归回溯由于回溯法对解空间作深度优先搜索，因此，在一由于回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法般情况下用递归方法实现回溯法（回溯法也是设计递归过程的一种重要方法）。voidbacktrack(intt)/形参t表示递归深度，n是问题规模if(tn)outp

16、ut(x);/搜索到一个叶结点elsefor(inti=f(n,t);i0)if(f(n,t)=g(n,t)for(int i=f(n,t);in)output(x);elsefor(inti=0;in)output(x);elsefor(inti=t;i1则其左儿子结点的载重为：则其左儿子结点的载重为：子集树子集树475.2 装载问题装载问题templateclassLoading/定义类定义类LoadingfriendMaxLoading(Type,Type,int，int);/MaxLoading负责类负责类Loading的私有变量的初始化的私有变量的初始化private:voidBac

17、ktrack(inti);/Backtrack负责计算最优载重负责计算最优载重量量intn,/集装箱数目集装箱数目*x,/当前解当前解*bestx;/当前最优解当前最优解Type*w,/集装箱重量数组集装箱重量数组c,/第一艘船的容量第一艘船的容量cw,/当前装载的重量当前装载的重量bestw;/目前最优装载的重量目前最优装载的重量;485.2装载问题voidLoading:Backtrack(inti)/搜索第搜索第i层结点层结点if(in)/到达叶结点到达叶结点if(cwbestw)bestw=cw;更新更新bestx;return;/搜索子树搜索子树if(cw+wi=c)/左子树左子树x

18、i=1;cw+=wi;backtrack(i+1);cw-=wi;xi=0;/右子树右子树backtrack(i+1);for(int j=1;j bestwr：剩余集装箱的重量：剩余集装箱的重量当前扩展结点处于第当前扩展结点处于第i层时，层时，r的初始值：的初始值：525.2装载问题void backtrack(int i)/搜索第i层结点 if(i n)/到达叶结点 if(cwbestw)更新最优解bestx,bestw;return;r-=wi;/向下一层时将物品i从r中去除if(cw+wi bestw)/搜索右子树 xi=0;backtrack(i+1);r+=wi;/回到本层时将r还

19、原 535.2装载问题试画出以下实例的解空间树：试画出以下实例的解空间树：n=3,c1=30,w=16,15,15ABCDEFG545.3批处理作业调度现在有现在有n n个作业需要处理，每个作业都是先个作业需要处理，每个作业都是先计算后打印。计算任务由中央处理器完成，计算后打印。计算任务由中央处理器完成，打印由打印机完成。打印由打印机完成。问：以什么顺序处理能使这些作业的问：以什么顺序处理能使这些作业的完成完成时间和时间和达到最小。达到最小。555.3批处理作业调度给定给定n n个作业的集合个作业的集合JJ1 1,J,J2 2,J Jn n。每个作。每个作业必须先由机器业必须先由机器1 1处理

20、，后由机器处理，后由机器2 2处理。处理。作业作业J Ji i需要机器需要机器j j的处理时间为的处理时间为t tjiji。对于一个确定的作业调度，设对于一个确定的作业调度，设F Fjiji是作业是作业i i在在机器机器j j上完成处理的时间。所有作业在机器上完成处理的时间。所有作业在机器2 2上完成处理的时间和上完成处理的时间和 称为该作业调度的完成时间和。称为该作业调度的完成时间和。565.3批处理作业调度批处理作业调度问题要求对于给定的批处理作业调度问题要求对于给定的n n个作个作业，制定业，制定最佳作业调度方案，使其完成时最佳作业调度方案，使其完成时间和达到最小间和达到最小。tji机器

21、机器1 1机器机器2 2作业作业1 12 21 1作业作业2 23 31 1作业作业3 32 23 3575.3批处理作业调度这这3 3个作业的个作业的6 6种可能的调度方案是：种可能的调度方案是：1,2,31,2,3；1,3,21,3,2；2,1,32,1,3；2,3,12,3,1；3,1,23,1,2；3,2,13,2,1；它们所相应的完成时间和分别是：它们所相应的完成时间和分别是：19 19，1818，2020，2121，1919，19 19。最佳调度方案是最佳调度方案是1,3,21,3,2，其完成时间和为，其完成时间和为1818。因此，批处理作业调度的解空间树：因此，批处理作业调度的解

22、空间树：排列树排列树585.3批处理作业调度class Flowshop friend Flow(int*,int,int);private:void Backtrack(int i);int *M,/各作业所需的处理时间各作业所需的处理时间 *x,/当前作业调度当前作业调度 *bestx,/当前最优作业调度当前最优作业调度 *f2,/机器机器2完成处理时间完成处理时间 f1,/机器机器1完成处理时间完成处理时间 f,/完成时间和完成时间和 bestf,/当前最优值当前最优值 n;/作业数作业数;595.3批处理作业调度对于实例来说：对于实例来说：x=0,1,2,3M1=0,2,3,2 M2=

23、0,1,1,3f2=0,0,0,0bestf的初值的初值32767tji机器机器1 1机器机器2 2作业作业1 12 21 1作业作业2 23 31 1作业作业3 32 23 3605.3批处理作业调度voidFlowshop:Backtrack(inti)if(in)for(intj=1;j=n;j+)bestxj=xj;bestf=f;elsefor(intj=i;jf1)?f2i-1:f1)+Mxj2;f+=f2i;if(fbestf)Swap(xi,xj);Backtrack(i+1);Swap(xi,xj);f1-=Mxj1;f-=f2i;/else,for/end615.3批处理作

24、业调度画出以下实例的解空间树：画出以下实例的解空间树：tji机器机器1 1机器机器2 2作业作业1 12 21 1作业作业2 23 31 1作业作业3 32 23 3625.5n后问题n n后问题：在后问题：在nnnn格的棋盘上放置彼此不受攻格的棋盘上放置彼此不受攻击的击的n n个皇后。个皇后。1234567812345678QQQQQQQQ635.5n后问题按照国际象棋的规则，皇后可以攻击与之处在同一按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。行或同一列或同一斜线上的棋子。n n后问题等价于在后问题等价于在nnnn格的棋盘上放置格的棋盘上放置n n个皇后，任个皇

25、后，任何何2 2个皇后不放在同一行或同一列或同一斜线上。个皇后不放在同一行或同一列或同一斜线上。1234567812345678QQQQQQQQ645.5n后问题解向量：解向量：(x1,x2,xn)xi表示皇后表示皇后i放在棋盘的第放在棋盘的第xi列列显约束：显约束：xi=1,2,n隐约束：隐约束：1)不同列：不同列：xi xj 2)不处于同一正、反对角线：不处于同一正、反对角线：|i-j|xi-xj|另外，另外，n是偶数时才有可行解，是偶数时才有可行解，n是奇数时无解。是奇数时无解。655.5n后问题bool Queen:Place(int k)/place函数测试皇后互不攻击函数测试皇后互

26、不攻击 for(int j=1;jn)sum+;/sum为可行方案数为可行方案数 else for(int i=1;i=n;i+)xt=i;if(Place(t)Backtrack(t+1);665.60-1背包问题解空间：解空间：可行性约束函数：可行性约束函数：上界函数：上界函数：r是尚未考虑的剩余物品价值总和。是尚未考虑的剩余物品价值总和。子集树子集树cp+rbestp67VoidKnap:backtrack(inti)/搜索第搜索第i层结点层结点if(in)/到达叶结点到达叶结点bestp=cp;return;if(cw+wibestp)/搜索右子树搜索右子树,xi=0backtrack

27、(i+1);685.60-1背包问题-上界函数上界函数templateTypep Knap:Bound(int i)/计算上界计算上界 Typew cleft=c-cw;/剩余容量剩余容量 Typep b=cp;/当前价值当前价值 while(i=n&wi=cleft)/以物品单位重量价值递减序装入物品以物品单位重量价值递减序装入物品 /为了方便计算上界函数，可先将物品按单位重量价值从大到小排序为了方便计算上界函数，可先将物品按单位重量价值从大到小排序 cleft-=wi;b+=pi;i+;if(i bestpBound(4)=23+7=30,30bestpcw+w4=19 c,剪枝剪枝F72

28、cw=0cp=0解空间树ABCDEcw=6cp=18Bound(2)=0+5+8+7=2016,剪枝剪枝Bound(5)=cpbestp,剪枝剪枝Bound(4)=18+7=25bestp,剪枝剪枝W=6,2,4,8V=18,5,8,7C=1673解空间树ABCDEFG从解空间树知最优值为从解空间树知最优值为3131，最优解向量最优解向量X=1,1,1,0X=1,1,1,0W=6,2,4,8V=18,5,8,7C=1674最终结果S=3,4,1,2(对应的原物品序号对应的原物品序号)最优解向量最优解向量X=1,1,1,0可知最大价值可知最大价值31对应的物品选择是：对应的物品选择是：1,3,4

29、。75动态规划法解答过程W=4,8,6,2 V=8,7,18,5从上表可知最优值为从上表可知最优值为31。0 1 2 3 4 5 67891011 1213 141516310 0 5 5 5 5 18 1823 23 2323 2323 2323300 0 5 5 5 5 18 1823 23 2323 2323 2323230 0 5 5 5 5 55555555555m116!=m216 x1=1m212=m312 x2=0m312!=m212 x3=1m46!=0 x4=1最优解为最优解为(1,0,1,1)(1,0,1,1)对应物品对应物品1,3,41,3,4。76生成问题状态的基本方

30、法生成问题状态的基本方法深度优先的问题状态生成法：如果对一个扩深度优先的问题状态生成法：如果对一个扩展结点展结点R，一旦产生了它的一个儿子，一旦产生了它的一个儿子C，就，就把把C当做新的扩展结点。在完成对子树当做新的扩展结点。在完成对子树C（以（以C为根的子树）的穷尽搜索之后，将为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成重新变成扩展结点，继续生成R的下一个儿的下一个儿子（如果存在）。子（如果存在）。宽度优先的问题状态生成法：在一个扩展结宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点。点变成死结点之前，它一直是扩展结点。77回溯法回溯法回溯法：为了避免生

31、成那些不可能产生最回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际来处死那些实际上不可能产生所需解的活结点，以减少问上不可能产生所需解的活结点，以减少问题的计算量。题的计算量。因此，因此，具有限界函数的深度优先生成法称具有限界函数的深度优先生成法称为回溯法为回溯法。78第3章习题的回溯法解法2、设有、设有0/1背包实例，有四件物品，其重量分别为背包实例，有四件物品，其重量分别为5,7,3,4，价值分别为，价值分别为2,5,8,1，且背包最大容量为，且背包最大容量为16。问：背包内装入

32、哪些物品可以不超重并且达到最大价问：背包内装入哪些物品可以不超重并且达到最大价值。值。解：设物品序号为解：设物品序号为0,1,2,3，W=w0,w1,w2,w3=5,7,3,4表示四件物品的重量，表示四件物品的重量，V=v0,v1,v2,v3=2,5,8,1表示表示四件物品的价值四件物品的价值,C=16表示背包的最大容量。表示背包的最大容量。按单位重量价值排序，新的按单位重量价值排序，新的W和和V 如下：如下：W=3,7,5,4 V=8,5,2,179cw=10cp=13cw=0cp=0解空间树W=3,7,5,4V=8,5,2,1C=16ABCDcw=3cp=8cw=15cp=15Bound(3)=8+2+1=11bestp,剪枝剪枝Bound(4)=13+1=14,14bestp,bestp=0cw+w4=19 c,剪枝剪枝cw=15cp=15Bestp=15Bound(2)=0+5+2+1=8bestp,剪枝剪枝最优解向量最优解向量X=1,1,1,0最大价值：最大价值：15对应的物品选择是：对应的物品选择是：0,1,2。80