单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,学习要点,理解分支限界法的剪枝搜寻策略。,把握分支限界法的算法框架,1队列式(FIFO)分支限界法,2优先队列式分支限界法,通过应用范例学习分支限界法的设计策略。,1单源最短路径问题,2装载问题；,3布线问题,40-1背包问题；,5最大团问题；,6旅行售货员问题,7电路板排列问题,8批处理作业调度问题,1,6.1分支限界法的根本思想,分支限界法与回溯法,1求解目标：回溯法的求解目标是找出解空间树中满足约束条件的全部解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。,2搜寻方式的不同：回溯法以深度优先的方式搜寻解空间树，而分支限界法则以广度优先或以最小消耗优先的方式搜寻解空间树。,2,6.1分支限界法的根本思想,分支限界法常以广度优先或以最小消耗最大效益优先的方式搜寻问题的解空间树。,此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程始终持续到找到所需的解或活结点表为空时为止。,在分支限界法中，每一个活结点只有一次时机成为扩展结点。活结点一旦成为扩展结点，就一次性产生其全部儿子结点。在这些儿子结点中，导致不行行解或导致非最优解的儿子结点被舍弃，其余儿子结点被参加活结点表中。,3,6.1分支限界法的根本思想,常见的两种分支限界法,1队列式(FIFO)分支限界法,依据队列先进先出FIFO原则选取下一个节点为扩展节点。,2优先队列式分支限界法,依据优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。,4,6.2,单源最短路径问题,1.问题描述,下面以一个例子来说明单源最短路径问题：在以下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。,5,6.2,单源最短路径问题,1.问题描述,以下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。,6,6.2,单源最短路径问题,2.算法思想,解单源最短路径问题的优先队列式分支限界法用一微小堆来存储活结点表。其优先级是结点所对应的当前路长。,算法从图G的源顶点s和空优先队列开头。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的全部顶点。假设从当前扩展结点i到顶点j有边可达，且从源动身，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程始终连续到活结点优先队列为空时为止。,7,6.2,单源最短路径问题,3.剪枝策略,在算法扩展结点的过程中，一旦觉察一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。,在算法中，利用结点间的掌握关系进展剪枝。从源顶点s动身，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。,8,6.2,单源最短路径问题,while(true),for(int j=1;j=n;j+),if(cE.ijinf)&(E.length+cE.ijdistj),/顶点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的路径长,9,6.3,装载问题,1.问题描述,有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集,装箱i的重量为Wi，且,装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。假设有，找出一种装载方案。,简洁证明：假设一个给定装载问题有解，则承受下面的策略可得到最优装载方案。,(1)首先将第一艘轮船尽可能装满；,(2)将剩余的集装箱装上其次艘轮船。,10,6.3,装载问题,2.队列式分支限界法,在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。假设是则将其参加到活结点队列中。然后将其右儿子结点参加到活结点队列中(右儿子结点肯定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。,活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列肯定不空。当取出的元素是-1时，再推断当前队列是否为空。假设队列非空，则将尾部标记-1参加活结点队列，算法开头处理下一层的活结点。,11,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+;/进入下一层 ,12,6.3,装载问题,3.算法的改进,节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+rbestw时，可将其右子树剪去，由于此时假设要船装最多集装箱，就应当把此箱装上船。,另外，为了确保右子树成功剪枝，应当在算法每一次进入左子树的时候更新bestw的值。,13,6.3,装载问题,3.算法的改进,/检查左儿子结点,Type wt=Ew+wi;/左儿子结点的重量,if(wt bestw)bestw=wt;,/参加活结点队列,if(i bestw&i 0;j-),bestxj=bestE-LChild;,bestE=bestE-parent;,16,6.3,装载问题,5.优先队列式分支限界法,解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。,优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中全部结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级一样。,在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。,17,6.4,布线问题,1.算法思想,解此问题的队列式分支限界法从起始位置a开头将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被参加到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。,接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程始终连续到算法搜寻到目标方格b或活结点队列为空时为止。即参加剪枝的广度优先搜寻。,18,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;/左翼和右翼,设置边界的围墙,19,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);,找到目标位置后，可以通过回溯方法找到这条最短路径。,20,6.5 0-1,背包问题,算法的思想,首先，要对输入数据进展预处理，将各物品依其单位重量价值从大到小进展排列。,在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。,算法首先检查当前扩展结点的左儿子结点的可行性。假设该左儿子结点是可行结点，则将它参加到子集树和活结点优先队列中。当前扩展结点的右儿子结点肯定是可行结点，仅当右儿子结点满足上界约束时才将它参加子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。,21,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,为上界函数,22,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);,/取下一个扩展节点略,分支限界搜寻过程,23,6.6,最大团问题,给定无向图G=(V，E)。假设UV，且对任意u，vU有(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.问题描述,24,6.6,最大团问题,2.上界函数,用变量cliqueSize表示与该结点相应的团的顶点数；level表示结点在子集空间树中所处的层次；用cliqueSize+n-level+1作为顶点数上界upperSize的值。,在此优先队列式分支限界法中，upperSize实际上也是优先队列中元素的优先级。算法总是从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩展元素。,25,6.6,最大团问题,3.算法思想,子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0。,算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i参加到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。当顶点i与当前团中全部顶点之间都有边相连，则相应的左儿子结点是可行结点，将它参加到子集树中并插入活结点优先队列，否则就不是可行结点。,接着连续考察当前扩展结点的右儿子结点。当upperSizebestn时，右子树中可能含有最优解，此时将右儿子结点参加到子集树中并插入到活结点优先队列中。,26,6.6,最大团问题,3.算法思想,算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。,对于子集