算法设计与分析第6章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第,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,实际上也是优先队列中元素的优先级。算法总是从活结