算法设计与分析第6章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第,6,章 分支限界法,1,学习要点,理解分支限界法的剪枝搜索策略。,掌握分支限界法的算法框架,（,1,）队列式,(FIFO),分支限界法,（,2,）优先队列式分支限界法,通过应用范例学习分支限界法的设计策略。,（,1,）单源最短路径问题,（,2,）装载问题；,（,3,）布线问题,（,4,）,0-1,背包问题；,（,5,）最大团问题；,（,6,）旅行售货员问题,（,7,）电路板排列问题,（,8,）批处理作业调度问题,2,6.1分支限界法的基本思想,分支限界法与回溯法,（1）求解目标：,回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。,（2）搜索方式的不同：,回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,3,6.1分支限界法的基本思想,分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。,此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。,4,6.1分支限界法的基本思想,常见的两种分支限界法,（1）,队列式,(,FIFO),分支限界法,按照队列先进先出（,FIFO）,原则选取下一个节点为扩展节点。,（2）优先队列式分支限界法,按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。,5,6.2单源最短路径问题,1.问题描述,下面以一个例子来说明单源最短路径问题：,在下图所给的有向图,G,中，每一边都有一个非负边权。要求图,G,的从源顶点,s,到目标顶点,t,之间的最短路径。,6,6.2单源最短路径问题,1.问题描述,下图是用优先队列式分支限界法解有向图,G,的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。,7,6.2单源最短路径问题,2.算法思想,解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。,算法从图,G,的源顶点,s,和空优先队列开始。结点,s,被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点,i,到顶点,j,有边可达，且从源出发，途经顶点,i,再到顶点,j,的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。,8,6.2单源最短路径问题,3.剪枝策略,在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。,在算法中，利用结点间的控制关系进行剪枝。从源顶点,s,出发，2条不同路径到达图,G,的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。,9,6.2单源最短路径问题,while(true),for(,int,j=1;j=n;j+),if(,cE.ij,inf)&(E.length+cE.ij,distj,),/,顶点,i,到顶点,j,可达，且满足控制约束,distj,=,E.length+cE.ij,;,prevj,=,E.i,;,/,加入活结点优先队列,MinHeapNode,N;,N.i,=j;,N.length,=,distj,;,H.Insert(N,);,try,H.DeleteMin(E,);/,取下一扩展结点,catch(,OutOfBounds,)break;/,优先队列空,顶点,I,和,j,间有边，且此路径长小于原先从原点到,j,的路径长,10,6.3 装载问题,1.问题描述,有一批共个集装箱要装上,2,艘载重量分别为,C1,和,C2,的轮船，其中集,装箱,i,的重量为,Wi,，,且,装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这,2,艘轮船。如果有，找出一种装载方案。,容易证明：,如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。,(1),首先将第一艘轮船尽可能装满；,(2),将剩余的集装箱装上第二艘轮船。,11,6.3 装载问题,2.队列式分支限界法,在算法的,while,循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中,(,右儿子结点一定是可行结点,),。,2,个儿子结点都产生后，当前扩展结点被舍弃。,活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记,-1,，故在取队首元素时，活结点队列一定不空。当取出的元素是,-1,时，再判断当前队列是否为空。如果队列非空，则将尾部标记,-1,加入活结点队列，算法开始处理下一层的活结点。,12,6.3 装载问题,2.队列式分支限界法,while(true),/,检查左儿子结点,if(,Ew,+,wi,=c)/,xi,=1,EnQueue(Q,Ew,+,wi,bestw,i,n);,/,右儿子结点总是可行的,EnQueue(Q,Ew,bestw,i,n);/,xi,=0,Q.Delete(Ew,);/,取下一扩展结点,if(,Ew,=-1)/,同层结点尾部,if(,Q.IsEmpty,()return,bestw,;,Q.Add(-1);/,同层结点尾部标志,Q.Delete(Ew,);/,取下一扩展结点,i+;/,进入下一层,13,6.3 装载问题,3.算法的改进,节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设,bestw,是当前最优解；,ew,是当前扩展结点所相应的重量；,r,是剩余集装箱的重量。则当,ew+r,bestw,时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。,另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新,bestw,的值。,14,6.3 装载问题,3.算法的改进,/,检查左儿子结点,Type wt=,Ew,+,wi,;/,左儿子结点的重量,if(wt,bestw,),bestw,=wt;,/,加入活结点队列,if(i,bestw,&i 0;j-),bestxj,=,bestE,-,LChild,;,bestE,=,bestE,-parent;,17,6.3 装载问题,5.,优先队列式分支限界法,解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点,x,在优先队列中的优先级定义为从根结点到结点,x,的路径所相应的载重量再加上剩余集装箱的重量之和。,优先队列中优先级最大的活结点成为下一个扩展结点。以结点,x,为根的子树中所有结点相应的路径的载重量不超过,它的优先级,。子集树中叶结点所相应的载重量与其优先级相同。,在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。,18,6.4 布线问题,1.算法思想,解此问题的队列式分支限界法从起始位置,a,开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为,1,，即从起始方格,a,到这些方格的距离为,1,。,接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为,2,，并存入活结点队列。这个过程一直继续到算法搜索到目标方格,b,或活结点队列为空时为止。即加入剪枝的广度优先搜索。,19,6.4 布线问题,Position offset4;,offset0.row=0;offset0.col=1;/,右,offset1.row=1;offset1.col=0;/,下,offset2.row=0;offset2.col=-1;/,左,offset3.row=-1;offset3.col=0;/,上,定义移动方向的相对位移,for(,int,i=0;i=m+1;i+),grid0i=gridn+1i=1;/,顶部和底部,for(,int,i=0;i=n+1;i+),gridi0=gridim+1=1;/,左翼和右翼,设置边界的围墙,20,6.4 布线问题,for(,int,i=0;i,NumOfNbrs,;i+),nbr.row,=,here.row,+,offseti.row,;,nbr.col,=,here.col,+,offseti.col,;,if(,gridnbr.rownbr.col,=0),/,该方格未标记,gridnbr.rownbr.col,=,gridhere.rowhere.col,+1;,if(,nbr.row,=,finish.row,)&,(,nbr.col,=,finish.col,)break;/,完成布线,Q.Add(nbr,);,找到目标位置后，可以通过回溯方法找到这条最短路径。,21,6.5 0-1背包问题,算法的思想,首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。,在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。,算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。,当扩展到叶节点时为问题的最优值。,22,6.5 0-1背包问题,上界函数,while(i=n&wi=cleft),/n,表示物品总数，,cleft,为剩余空间,cleft-=wi/wi,表示,i,所占空间,b+=pi;,/p,i,表示,i,的价值,i+;,if(i=n)b+=pi/wi*cleft;,/,装填剩余容量装满背包,return b;,/b,为上界函数,23,6.5 0-1背包问题,while(i!=n+1)/,非叶结点,/,检查当前扩展结点的左儿子结点,Typew,wt=,cw,+,wi,;,if(wt,bestp,),bestp,=,cp+pi,;,AddLiveNode(up,cp+pi,cw+wi,true,i+1);,up=Bound(i+1);,/,检查当前扩展结点的右儿子结点,if(up=,bestp,)/,右子树可能含最优解,AddLiveNode(up,cp,cw,false,i+1);,/,取下一个扩展节点（略）,分支限界搜索过程,24,6.6 最大团问题,给定无向图,G=(V,，,E),。,如果,U,V,，,且对任意,u,，,v,U,有,(,u,，,v),E,，,则称,U,是,G,的完全子图。,G,的完全子图,U,是,G,的团当且仅当,U,不包含在,G,的更大的完全子图中。,G,的最大团是指,G,中所含顶点数最多的团。,下图,G,中，子集,1,，,2,是,G,的大小为,2,的完全子图。这个完全子图不是团，因为它被,G,的更大的完全子图,1,，,2,，,5,包含。,1,，,2,，,5,是,G,的最大团。,1,，,4,，,5和,2,，,3,，,5,也是,G,的最大团。,1.问题描述,25,6.6 最大团问题,2.上界函数,用变量,cliqueSize,表示与该结点相应的团的顶点数；,level,表示结点在子集空间树中所处的层次；用,cliqueSize,+n-level+1,作为顶点数上界,upperSize,的值。,在此优先队列式分支限界法中，,upperSize,实际上也是优先队列中元素的优先级。算法总是从活结点优先队列中抽取具有最大,upperSize,值的元素作为下一个扩展元素。,26,6.6 最大团问题,3.算法思想,子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其,cliqueSize,的值为,0,。,算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点,i,加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。当顶点,i,与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。,接着继续考察当前扩展结点的右儿子结点。当,upperSize,bestn,时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。,27,6.6 最大团问题,3.算法思想,算法的,while,循环的终止条件是遇到子集树中的一个叶结点,(,即,n+1,层结点,),成为当前扩展结点。,对于子集树中的叶结点，有,upperSizecliqueSize,。,此时活结点优先队列中剩余结点的,upperSize,值均不超过当前扩展结点的,upperSize,值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。,28,6.7 旅行售货员问题,1.问题描述,某售货员要到若干城市去推销商品，已知各城市之间的路程,(,或旅费,),。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程,(,或总旅费,),最小。,路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括,V,中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。,旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。,旅行售货员问题要在图,G,中找出费用最小的周游路线。,29,6.7 旅行售货员问题,2.算法描述,算法开始时创建一个最小堆，用于表示活结点优先队列。堆中每个结点的子树费用的下界,lcost,值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用,minout,记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的,minout,作算法初始化。,算法的,while,循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分,2,种情况进行处理：,30,6.7 旅行售货员问题,2.算法描述,1、首先考虑,s=n-2,的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。,2、当,sn-2,时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是,x0:s,，,其可行儿子结点是从剩余顶点,xs+1:n-1,中选取的顶点,xi,，,且,(,xs,，,xi),是所给有向图,G,中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀,(,x0:s,，,xi),的费用,cc,和相应的下界,lcost,。,当,lcost,bestc,时，将这个可行儿子结点插入到活结点优先队列中。,31,6.7 旅行售货员问题,2.算法描述,算法中,while,循环的终止条件是排列树的一个叶结点成为当前扩展结点。当,s=n-1,时，已找到的回路前缀是,x0:n-1,，,它已包含图,G,的所有,n,个顶点。因此，当,s=n-1,时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于,cc,和,lcost,的值。剩余的活结点的,lcost,值不小于已找到的回路的费用。它们都不可能导致费用更小的回路。因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可以结束。,算法结束时返回找到的最小费用，相应的最优解由数组,v,给出。,32,6.8 电路板排列问题,算法描述,算法开始时，将排列树的根结点置为当前扩展结点。在,do-while,循环体内算法依次从活结点优先队列中取出具有最小,cd,值的结点作为当前扩展结点，并加以扩展。,首先考虑,s=n-1,的情形，当前扩展结点是排列树中的一个叶结点的父结点。,x,表示相应于该叶结点的电路板排列。计算出与,x,相应的密度并在必要时更新当前最优值和相应的当前最优解,。,当,sn-1,时，算法依次产生当前扩展结点的所有儿子结点。对于当前扩展结点的每一个儿子结点,node,，,计算出其相应的密度,node.cd,。,当,node.cd,bestd,时，将该儿子结点,N,插入到活结点优先队列中。,33,6.8 电路板排列问题,算法描述,do/,结点扩展,if(,E.s,=n-1)/,仅一个儿子结点,int,ld=0;/,最后一块电路板的密度,for(,int,j=1;j=m;j+),ld+=,BE.xnj,;,if(ld,bestd,)/,密度更小的电路板排列,delete,bestx,;,bestx,=,E.x,;,bestd,=,max(ld,E.cd,);,S=n-1,的情况，计算出此时的密度和,bestd,进行比较。,34,6.8 电路板排列问题,算法描述,else,/,产生当前扩展结点的所有儿子结点,for(,int,i=,E.s,+1;i=n;i+),BoardNode,N;,N.now,=new,int,m+1;,for(,int,j=1;j=m;j+),/,新插入的电路板,N.nowj,=,E.nowj,+,BE.xij,;,35,6.8 电路板排列问题,int,ld=0;/,新插入电路板的密度,for(,int,j=1;j 0&,totalj,!=,N.nowj,)ld+;,N.cd,=,max(ld,E.cd,);,if(,N.cd,bestd,)/,可能产生更好的叶结点,N.x,=new,int,n+1;,N.s,=,E.s,+1;,for(,int,j=1;j=,r,+1,时依非减序排列，,S1,则取得极小值,。,同理如果选择,P,k,使,t,2pk,依非减序排列，则,S2,取得极小值。,这可以作为优先队列式分支限界法中的限界函数。,38,6.9 批处理作业调度问题,3.算法描述,算法的,while,循环完成对排列树内部结点的有序扩展。在,while,循环体内算法依次从活结点优先队列中取出具有最小,bb,值（完成时间和下界）的结点作为当前扩展结点，并加以扩展。,首先考虑,E,.s,=n,的情形，当前扩展结点,E,是排列树中的叶结点。,E.sf2,是相应于该叶结点的完成时间和。当,E.sf2,bestc,时更新当前最优值,bestc,和相应的当前最优解,bestx,。,当,E.s,n,时，算法依次产生当前扩展结点,E,的所有儿子结点。对于当前扩展结点的每一个儿子结点,node,，,计算出其相应的完成时间和的下界,bb,。,当,bb,bestc,时，将该儿子结点插入到活结点优先队列中。而当,bb,bestc,时，可将结点,node,舍去。,39,6.9 批处理作业调度问题,while(,E.s,=n),if(,E.s,=n)/,叶结点,if(E.sf2,bestc,),bestc,=E.sf2;,for(,int,i=0;i n;i+),bestxi,=,E.xi,;,delete,E.x,;,3.算法描述,当,E.sf2,bestc,时，更新当前最优值,bestc,和相应的最优解,bestx,40,6.9 批处理作业调度问题,3.算法描述,else/,产生当前扩展结点的儿子结点,for(,int,i=,E.s,;i n;i+),Swap(E.xE.s,E.xi,);,int,f1,f2;,int,bb=Bound(E,f1,f2,y);,if(bb,bestc,),MinHeapNode,N;,N.NewNode(E,f1,f2,bb,n);,H.Insert(N,);,Swap(E.xE.s,E.xi,);,delete,E.x,;/,完成结点扩展,当,bb,bestc,时，将儿子结点插入到活结点优先队列中,41,课后作业,习题,6-1,，,6-2,，,6-3,，,6-4,，,6-5,，,6-6,，,6-10,42,43,