分支限界法市公开课一等奖省赛课获奖课件

算法分析与设计清华大学出版社王晓东等

编著任课教师：向金海联络电话：62193562，87282492（O）Email:jimmy_xiang@

jimmy_xiang@163.com分支限界法第1页第六章分支限界法

华中农业大学理学院，37分支限界法第2页主要内容:了解分支限界法剪枝搜索策略。掌握分支限界法算法框架队列式(FIFO)分支限界法优先队列式分支限界法经过应用范例学习分支限界法设计策略。单源最短路径问题装载问题；布线问题0-1背包问题；最大团问题；旅行售货员问题电路板排列问题批处理作业调度问题分支限界法第3页6.1 分支限界法基本思想1.分支限界法与回溯法不一样（1）求解目标：回溯法求解目标是找出解空间树中满足约束条件全部解，而分支限界法求解目标则是找出满足约束条件一个解，或是在满足约束条件解中找出在某种意义下最优解。（2）搜索方式不一样：回溯法以深度优先方式搜索解空间树，而分支限界法则以广度优先或以最小花费优先方式搜索解空间树。

分支限界法第4页6.1 分支限界法基本思想2.分支限界法基本思想分支限界法常以广度优先或以最小花费（最大效益）优先方式搜索问题解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其全部儿子结点。在这些儿子结点中，造成不可行解或造成非最优解儿子结点被舍弃，其余儿子结点被加入活结点表中。今后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直连续到找到所需解或活结点表为空时为止。分支限界法第5页6.1 分支限界法基本思想3.常见两种分支限界法（1）队列式(FIFO)分支限界法按照队列先进先出（FIFO）标准选取下一个节点为扩展节点。

（2）优先队列式分支限界法按照优先队列中要求优先级选取优先级最高节点成为当前扩展节点。分支限界法第6页6.2 单源最短路径问题1.问题描述下面以一个例子来说明单源最短路径问题：在下列图所给有向图G中，每一边都有一个非负边权。要求图G从源顶点s到目标顶点t之间最短路径。分支限界法第7页6.2 单源最短路径问题下列图是用优先队列式分支限界法解有向图G单源最短路径问题产生解空间树。其中，每一个结点旁边数字表示该结点所对应当前路长。分支限界法第8页6.2 单源最短路径问题2.算法思想解单源最短路径问题优先队列式分支限界法用一极小堆来存放活结点表。其优先级是结点所对应当前路长。算法从图G源顶点s和空优先队列开始。结点s被扩展后，它儿子结点被依次插入堆中。今后，算法从堆中取出含有最小当前路长结点作为当前扩展结点，并依次检验与当前扩展结点相邻全部顶点。假如从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j所对应路径长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点扩展过程一直继续到活结点优先队列为空时为止。分支限界法第9页6.2 单源最短路径问题3.剪枝策略在算法扩展结点过程中，一旦发觉一个结点下界大于当前找到最短路长，则算法剪去以该结点为根子树。在算法中，利用结点间控制关系进行剪枝。从源顶点s出发，2条不一样路径抵达图G同一顶点。因为两条路径路长不一样，所以能够将路长长路径所对应树中结点为根子树剪去。

分支限界法第10页6.2 单源最短路径问题

while(true){//搜索问题解空间for(intj=1;j<=n;j++)if(a[enode.i][j]<Float.MAX_VALUE&&enode.length+a[enode.i][j]<dist[j]){//顶点i到顶点j可达，且满足控制约束dist[j]=enode.length+a[enode.i][j];p[j]=enode.i;HeapNodenode=newHeapNode(j,dist[j]);heap.put(node);//加入活结点优先队列}

if(heap.isEmpty())break;elseenode=(HeapNode)heap.removeMin();}顶点I和j间有边，且此路径长小于原先从原点到j路径长

分支限界法第11页6.2多段图问题1.问题描述

●在多段图中求从s到t一条最小成本路径，能够看作是在k-2个段作出某种决议结果。

●第i次决议决定Vi+1中哪个结点在这条路径上，这里1≤i≤k-2；

●最优性原理对多段图问题成立分支限界法第12页2.向前处理策略求解设P(i,j)是一条从Vi中结点j到汇点t最小成本路径，COST(i,j)是这条路径成本。1)向前递推式2)递推过程

★第k-1段c(j,t)<j,t>∈ECOST(k-1,j)=

∞分支限界法第13页l1l2...lpi+1t…jViVi+1分支限界法第14页12345678910111297324227111181456356425V1V2V3V4V55段图分支限界法第15页★各递推结果第4段COST(4,9)=c(9,12)=4

COST(4,10)=c(10,12)=2COST(4,11)=c(11,12)=5第3段COST(3,6)=min{6+COST(4,9),5+COST(4,10)}=7COST(3,7)=min{4+COST(4,9),3+COST(4,10)}=5COST(3,8)=min{5+COST(4,10),6+COST(4,11)}=7第2段COST(2,2)=min{4+COST(3,6),2+COST(3,7),1+COST(3,8)}=7COST(2,3)=9COST(2,4)=18COST(2,5)=15第1段COST(1,1)=min{9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)}=16S到t最小成本路径成本＝16分支限界法第16页★最小成本路径求取

记D(i,j)＝每一COST(i,j)决议即，使c(j,l)+COST(i+1,l)取得最小值l值。例：D(3,6)=10,D(3,7)=10D(3,8)=10D(2,2)=7,D(2,3)=6,D(2,4)=8,D(2,5)=8D(1,1)=2依据D(1,1)决议值向后递推求取最小成本路径：●v2=D(1,1)=2●v3=D(2,D(1,1))=7●v4=D(3,D(2,D(1,1)))=D(3,7)=10故由s到t最小成本路径是：1→2→7→10→12

分支限界法第17页3)算法描述★结点编号规则源点s编号为1,然后依次对V2、V3…Vk-1中结点编号，汇点t编号为n。目标：使对COST和D计算仅按n-1,n-2,…,1次序计算即可，无需考虑标示结点所在段第一个下标。★算法描述分支限界法第18页算法4.1多段图向前处理算法procedureFGRAPH(E,k,n,P)//输入是按段次序给结点编号，有n个结点k段图。E是边集，c(i,j)是边<i,j>成本。P(1:k)带出最小成本路径//realCOST(n);integerD(n-1),P(k),r,j,k,nCOST(n)←0forj←n-1to1by-1do//计算COST(j)//设r是含有性质：<j,r>∈E且使c(j,r)+COST(r)取最小值结点COST(j)←c(j,r)+COST(r)D(j)←r//统计决议值//repeatP(1)←1;P(k)←nforj←2tok-1do//找路径上第j个结点//P(j)←D(P(j-1))//回溯求出该路径//repeatendFGRAPH分支限界法第19页算法时间复杂度若G采取邻接表表示，总计算时间为：分支限界法第20页3.向后处理策略求解设BP(i,j)是一条从源点s到Vi中结点j最小成本路径，BCOST(i,j)是这条路径成本。1)向后递推式2)递推过程

★第2段c(1,j)<1,j>∈ECOST(2,j)=

∞分支限界法第21页12345678910111297324227111181456356425V1V2V3V4V55段图分支限界法第22页★各递推结果第2段BCOST(2,2)=9BCOST(2,3)=7BCOST(2,4)=3BCOST(2,5)=2第3段BCOST(3,6)=min{BCOST(2,2)+4,BCOST(2,3)+2}=9BCOST(3,7)=min{BCOST(2,2)+2,BCOST(2,3)+7,BCOST(2,5)+11}=11BCOST(3,8)=min{BCOST(2,4)+11,BCOST(2,5)+8}=10第4段BCOST(4,9)=min{BCOST(3,6)+6,BCOST(3,7)+4}=15BCOST(4,10)=min{BCOST(3,6)+5,BCOST(3,7)+3,BCOST(3,8)+5}=14BCOST(4,11)=min{BCOST(3,8)+6}=16第5段BCOST(5,12)=min{BCOST(4,9)+4,BCOST(4,10)+2,BCOST(4,11)+5}=16S到t最小成本路径成本＝16分支限界法第23页★最小成本路径求取记BD(i,j)＝每一COST(i,j)决议即，使COST(i-1,l)+c(l,j)取得最小值l值。例：BD(3,6)=3,BD(3,7)=2,BD(3,8)=5BD(4,9)=6,BD(4,10)=7,BD(4,11)=8BD(5,12)=10依据D(5,12)决议值向前递推求取最小成本路径：●v4=BD(5,12)=10●v3=BD(4,BD(5,12))=7●v2=BD(3,BD(4,BD(5,12)))=BD(3,7)=2故由s到t最小成本路径是：1→2→7→10→12

分支限界法第24页算法4.2多段图向后处理算法procedureBGRAPH(E,k,n,P)//输入是按段次序给结点编号，有n个结点k段图。E是边集，c(i,j)是边<i,j>成本。P(1:k)带出最小成本路径//realBCOST(n);integerBD(n-1),P(k),r,j,k,nBCOST(1)←0forj←2tondo//计算BCOST(j)//设r是含有<r,j>∈E且使BCOST(r)+c(r,j)取最小值性质结点BCOST(j)←BCOST(r)+c(r,j)BD(j)←r//统计决议值//repeatP(1)←1;P(k)←nforj←k-1to2by-1do//找路径上第j个结点//P(j)←D(P(j+1))//回溯求出该路径//repeatendBGRAPH分支限界法第25页4.多段图问题应用实例－资源分配问题将n个资源分配给r个项目标问题：假如把j个资源，0≤j≤n，分配给项目i，能够取得N(i,j)净利。问题：怎样将这n个资源分配给r个项目才能使各项目取得净利之和到达最大。转换成一个多段图问题求解。分支限界法第26页用r＋1段图描述该问题：

段：1到r之间每个段i表示项目i。

结点：i=1时，只有一个结点——源点s=V(1,0)当2≤i≤r时，每段有n+1个结点，每个结点含有形式

V(i,j)：表示到项目i之前为止，共把j个资源分配给了前i-1个项目，j=0,1,…,n。

汇点t=V(r+1,n)

边普通形式：<V(i,j),V(i+1,l)>,j≤l,1≤i≤r

成本：★当j≤l且1≤i≤r时，边<V(i,j),V(i+1,l)>赋予成本N(i,l-j),表示给项目i分配l-j个资源所可能取得净利。★当j≤n且i=r时，此时边为：<V(r,j),V(r+1,n)>,该边赋予成本：指向汇点边注，并不是分给资源越多，得到净利就越大分支限界法第27页实例：将4个资源分配给3个项目。组成一个4段图。问题解：资源最优分配方案由一条s到t最大成本路径给出——改变边成本符号，从而将问题转换成为求取最小成本路径问题。分支限界法第28页6.3装载问题1.问题描述有一批共个集装箱要装上2艘载重量分别为C1和C2轮船，其中集装箱i重量为Wi，且装载问题要求确定是否有一个合理装载方案可将这个集装箱装上这2艘轮船。假如有，找出一个装载方案。轻易证实：假如一个给定装载问题有解，则采取下面策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩下集装箱装上第二艘轮船。

分支限界法第29页6.3装载问题2.队列式分支限界法在算法while循环中，首先检测当前扩展结点左儿子结点是否为可行结点。假如是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。活结点队列中队首元素被取出作为当前扩展结点，因为队列中每一层结点之后都有一个尾部标识-1，故在取队首元素时，活结点队列一定不空。当取出元素是-1时，再判断当前队列是否为空。假如队列非空，则将尾部标识-1加入活结点队列，算法开始处理下一层活结点。分支限界法第30页6.3装载问题2.队列式分支限界法while(true){if(ew+w[i]<=c)enQueue(ew+w[i],i);//检验左儿子结点enQueue(ew,i);//右儿子结点总是可行ew=((Integer)queue.remove()).intValue();//取下一扩展结点if(ew==-1){if(queue.isEmpty())returnbestw;queue.put(newInteger(-1));//同层结点尾部标志ew=((Integer)queue.remove()).intValue();//取下一扩展结点i++;//进入下一层}}分支限界法第31页6.3装载问题3.算法改进节点左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所对应重量；r是剩下集装箱重量。则当ew+rbestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树时候更新bestw值。分支限界法第32页6.3装载问题3.算法改进//检验左儿子结点intwt=ew+w[i];if(wt<=c){//可行结点if(wt>bestw)bestw=wt;

//加入活结点队列if(i<n)queue.put(newInteger(wt));}提前更新bestw

//检验右儿子结点

if(ew+r>bestw&&i<n)//可能含最优解queue.put(newInteger(ew));

ew=((Integer)queue.remove()).intValue();//取下一扩展结点

右儿子剪枝

分支限界法第33页6.3装载问题4.结构最优解

为了在算法结束后能方便地结构出与最优值对应最优解，算法必须存放对应子集树中从活结点到根结点路径。为此目标，可在每个结点处设置指向其父结点指针，并设置左、右儿子标志。

privatestaticclassQNode{QNodeparent;//父结点booleanleftChild;//左儿子标志intweight;//结点所对应载重量分支限界法第34页6.3装载问题找到最优值后，能够依据parent回溯到根节点，找到最优解。//结构当前最优解for(intj=n;j>0;j--){bestx[j]=(e.leftChild)?1:0;e=e.parent;}分支限界法第35页6.3装载问题5.优先队列式分支限界法解装载问题优先队列式分支限界法用最大优先队列存放活结点表。活结点x在优先队列中优先级定义为从根结点到结点x路径所对应载重量再加上剩下集装箱重量之和。优先队列中优先级最大活结点成为下一个扩展结点。以结点x为根子树中全部结点对应路径载重量不超出它优先级。子集树中叶结点所对应载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则能够断言该叶结点所对应解即为最优解。此时可终止算法。分支限界法第36页6.4布线问题算法思想解此问题队列式分支限界法从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻而且可达方格成为可行结点被加入到活结点队列中，而且将这些方格标识为1，即从起始方格a到这些方格距离为1。接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标识过方格标识为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。即加入剪枝广度优先搜索。分支限界法第37页6.4布线问题Position[]offset=newPosition[4];offset[0]=newPosition(0,1);//右offset[1]=newPosition(1,0);//下offset[2]=newPosition(0,-1);//左offset[3]=newPosition(-1,0);//上

定义移动方向相对位移for(inti=0;i<=size+1;i++){grid[0][i]=grid[size+1][i]=1;//顶部和底部grid[i][0]=grid[i][size+1]=1;//左翼和右翼}设置边界围墙分支限界法第38页6.4布线问题for(inti=0;i<numOfNbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==0){//该方格未标识grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;if((nbr.row==finish.row)&&(nbr.col==finish.col))break;q.put(newPosition(nbr.row,nbr.col));}}找到目标位置后，能够经过回溯方法找到这条最短路径。分支限界法第39页6.50-1背包问题算法思想首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述优先队列分支限界法中，节点优先级由已装袋物品价值加上剩下最大单位重量价值物品装满剩下容量价值和。算法首先检验当前扩展结点左儿子结点可行性。假如该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题最优值。分支限界法第40页6.50-1背包问题上界函数while(i<=n&&w[i]<=cleft)//n表示物品总数，cleft为剩下空间{cleft-=w[i];//w[i]表示i所占空间b+=p[i];//p[i]表示i价值i++;}if(i<=n)b+=p[i]/w[i]*cleft;//装填剩下容量装满背包returnb;

//b为上界函数分支限界法第41页6.50-1背包问题while(i!=n+1){//

非叶结点doublewt=cw+w[i];if(wt<=c){//左儿子结点为可行结点if(cp+p[i]>bestp)bestp=cp+p[i];addLiveNode(up,cp+p[i],cw+w[i],i+1,enode,true);}up=bound(i+1);if(up>=bestp)//检验右儿子节点addLiveNode(up,cp,cw,i+1,enode,false);

//取下一个扩展节点（略）}分支限界搜索过程分支限界法第42页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最大团。分支限界法第43页6.6最大团问题2.上界函数用变量cliqueSize表示与该结点对应团顶点数；level表示结点在子集空间树中所处层次；用cliqueSize+n-level+1作为顶点数上界upperSize值。在此优先队列式分支限界法中，upperSize实际上也是优先队列中元素优先级。算法总是从活结点优先队列中抽取含有最大upperSize值元素作为下一个扩展元素。

分支限界法第44页6.6最大团问题3.算法思想子集树根结点是初始扩展结点，对于这个特殊扩展结点，其cliqueSize值为0。算法在扩展内部结点时，首先考查其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检验该顶点与当前团中其它顶点之间是否有边相连。当顶点i与当前团中全部顶点之间都有边相连，则对应左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，不然就不是可行结点。接着继续考查当前扩展结点右儿子结点。当upperSize>bestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。分支限界法第45页6.6最大团问题算法while循环终止条件是碰到子集树中一个叶结点(即n+1层结点)成为当前扩展结点。对于子集树中叶结点，有upperSize＝cliqueSize。此时活结点优先队列中剩下结点upperSize值均不超出当前扩展结点upperSize值，从而深入搜索不可能得到更大团，此时算法已找到一个最优解。分支限界法第46页6.7旅行售货员问题1.问题描述某售货员要到若干城市去推销商品，已知各城市之间旅程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最终回到驻地路线，使总旅程(或总旅费)最小。路线是一个带权图。图中各边费用（权）为正数。图一条周游路线是包含V中每个顶点在内一条回路。周游路线费用是这条路线上全部边费用之和。旅行售货员问题解空间能够组织成一棵树，从树根结点到任一叶结点路径定义了图一条周游路线。旅行售货员问题要在图G中找出费用最小周游路线。分支限界法第47页6.7旅行售货员问题2.算法描述算法开始时创建一个最小堆，用于表示活结点优先队列。堆中每个结点子树费用下界lcost值是优先队列优先级。接着算法计算出图中每个顶点最小费用出边并用minout统计。假如所给有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。假如每个顶点都有出边，则依据计算出minout作算法初始化。算法while循环体完成对排列树内部结点扩展。对于当前扩展结点，算法分2种情况进行处理：分支限界法第48页6.7旅行售货员问题1、首先考虑s=n-2情形，此时当前扩展结点是排列树中某个叶结点父结点。假如该叶结点对应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，不然舍去该叶结点。2、当s<n-2时，算法依次产生当前扩展结点全部儿子结点。因为当前扩展结点所对应路径是x[0:s]，其可行儿子结点是从剩下顶点x[s+1:n-1]中选取顶点x[i]，且(x[s]，x[i])是所给有向图G中一条边。对于当前扩展结点每一个可行儿子结点，计算出其前缀(x[0:s]，x[i])费用cc和对应下界lcost。当lcost<bestc时，将这个可行儿子结点插入到活结点优先队列中。分支限界法第49页6.7旅行售货员问题算法中while循环终止条件是排列树一个叶结点成为当前扩展结点。当s=n-1时，已找到回路前缀是x[0:n-1]，它已包含图G全部n个顶点。所以，当s=n-1时，对应扩展结点表示一个叶结点。此时该叶结点所对应回路费用等于cc和lcost值。剩下活结点lcost值大于已找到回路费用。它们都不可能造成费用更小回路。所以已找到叶结点所对应回路是一个最小费用旅行售货员回路，算法能够结束。算法结束时返回找到最小费用，对应最优解由数组v给出。分支限界法第50页6.8电路板排列问题算法描述

算法开始时，将排列树根结点置为当前扩展结点。在do-while循环体内算法依次从活结点优先队列中取出含有最小cd值结点作为当前扩展结点，并加以扩展。首先考虑s=n-1情形，当前扩展结点是排列树中一个叶结点父结点。x表示对应于该叶结点电路板排列。计算出与x对应密度并在必要时更新当前最优值和对应当前最优解。当s<n-1时，算法依次产生当前扩展结点全部儿子结点。对于当前扩展结点每一个儿子结点node，计算出其对应密度node.cd。当node.cd<bestd时，将该儿子结点N插入到活结点优先队列中。分支限界法第51页6.8电路板排列问题算法描述doif(enode.s==n-1){//仅一个儿子结点intld=0;//最终一块电路板密度for(intj=1;j<=m;j++)ld+=board[enode.x[n]][j];if(ld<bestd){//找到密度更小电路板排列x=enode.x;bestd=Math.max(ld,enode.cd);

}}S=n-1情况，计算出此时密度和bestd进行比较。分支限界法第52页6.8电路板排列问题算法描述else{//产生当前扩展结点全部儿子结点for(inti=enode.s+1;i<=n;i++){HeapNodenode=newHeapNode(0,newint[m+1],0,newint[n+1]);for(intj=1;j<=m;j++)

//新插入电路板node.now[j]=enode.now[j]+board[enode.x[i]][j];分支限界法第53页6.8电路板排列问题intld=0;//新插入电路板密度for(intj=1;j<=m;j++)if(node.now[j]>0&&total[j]!=node.now[j])ld++;node.cd=Math.max(ld,enode.cd);if(node.cd<bestd){//可能产生更加好叶结点node.s=enode.s+1;for(intj=1;j<=n;j++)node.x[j]=enode.x[j];node.x[node.s]=enode.x[i];node.x[i]=enode.x[node.s];heap.put(node);}