算法讲稿5分枝定界法

第六章分支限界法1学习要点理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架1.队列式(FIFO)分支限界法2.优先队列式分支限界法通过应用范例学习分支限界法的设计策略。1.单源最短路径问题2.装载问题；3.布线问题4.0-1背包问题；5.最大团问题；6.旅行售货员问题7.电路板排列问题8.批处理作业调度问题引言2分支限界法类似于回溯法，也是一种在问题的解空间树T中搜索问题解的算法。分支限界法与回溯法的求解目标不同：回溯法是找出满足约束条件的所有解分支限界法是找出满足条件的一个解，或某种意义下的最优解搜索方式不同回溯法：深度优先分支限界法：广度优先或最小耗费优先6.1分支限界法的基本思想3一、基本思想二、常见的两种分支限界法三、0-1背包问题四、旅行售货员问题一、基本思想4分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。二、常见的两种分支限界法5从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法：队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。最大优先队列：使用最大堆，体现最大效益优先最小优先队列：使用最小堆，体现最小费用优先三、0-1背包问题6考虑如下0-1背包问题的实例：n=3,c=30,w=[16,15,15],p=[45,25,25]队列式分支限界法：[A]B,C=B,C[B,C]D,E=E[C,E]F,G=F,G[E,F,G]J,K=K(45)[1,0,0][F,G]L,M=L(50)[0,1,1]M(25)[G]N,0=N(25),O(0)不搜索一不可行结点为根的子树优先队列式分支限界法：[A]B,C=B(45),C(0)[B,C]D,E=E(45)[E,C]J,K=K(45)[1,0,0][C]F,G=F(25),G(0)[F,G]L,M=L(50),[0,1,1]M(25)[G]N,O=N(25),O(0)可用剪枝函数加速搜索ABCDEFGHIJKLMNO10四、旅行售货员问题7队列式分支限界法：[A]B,C,D[B,C,D]E,F[C,D,E,F]G,H[D,E,F,G,H]I,J[E,F,G,H,I,J]K(59)[1,2,3,4][F,G,H,I,J]L(66)[G,H,I,J]M(25)[1,3,2,4][H,I,J]1-3-4(26)[I,J]O(25)[J]P(59)优先队列式分支限界法：[A]B,C,D=B(30),C(6),D(4)[D,C,B]I,J=I(14),J(24)[C,I,J,B]G,H=G(11),H(26)[G,I,J,B,H]M=M(25)[1,3,2,4][I,J,B,H]O=O(25)[J,B,H]P=P(59)[B,H]B,H限界掉1234643020510ABCDEFGHIJKLMNOP12343424234342326.2单源最短路径问题8一、问题描述二、算法思想三、剪枝策略四、算法描述一、问题描述9下面以一个例子来说明单源最短路径问题：在右上图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。右下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。二、算法思想10解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。三、剪枝策略11在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。四、算法描述12while(true){for(intj=1;j=n;j++)if((c[E.i][j]inf)&&(E.length+c[E.i][j]dist[j])){//顶点i到顶点j可达，且满足控制约束dist[j]=E.length+c[E.i][j];prev[j]=E.i;//加入活结点优先队列MinHeapNodeTypeN;N.i=j;N.length=dist[j];H.Insert(N);}try{H.DeleteMin(E);}//取下一扩展结点catch(OutOfBounds){break;}//优先队列空}}顶点I和j间有边，且此路径长小于原先从原点到j的路径长6.3装载问题13一、问题描述二、队列式分支限界法三、算法的改进四、构造最优解五、优先队列式分支限界法一、问题描述14有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为wi，且∑wi≤C1+C2装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。二、队列式分支限界法15在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。while(true){//检查左儿子结点if(Ew+w[i]=c)//x[i]=1EnQueue(Q,Ew+w[i],bestw,i,n);//右儿子结点总是可行的EnQueue(Q,Ew,bestw,i,n);//x[i]=0Q.Delete(Ew);//取下一扩展结点if(Ew==-1){//同层结点尾部if(Q.IsEmpty())returnbestw;Q.Add(-1);//同层结点尾部标志Q.Delete(Ew);//取下一扩展结点i++;}//进入下一层}}三、算法的改进16节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+rbestw时，可将其右子树剪去。另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。//检查左儿子结点Typewt=Ew+w[i];//左儿子结点的重量if(wt=c){//可行结点if(wtbestw)bestw=wt;//加入活结点队列if(in)Q.Add(wt);}//检查右儿子结点if(Ew+rbestw&&in)Q.Add(Ew);//可能含最优解Q.Delete(Ew);//取下一扩展结点四、构造最优解17为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。找到最优值后，可以根据parent回溯到根节点，找到最优解。classQNode{QNode*parent;//指向父结点的指针boolLChild;//左儿子标志Typeweight;//结点所相应的载重量}//构造当前最优解for(intj=n-1;j0;j--){bestx[j]=bestE-LChild;bestE=bestE-parent;}五、优先队列式分支限界法18解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。6.4布线问题19一、问题描述二、算法思想三、算法描述四、实例一、问题描述印刷电路板将布线区域划分为n×m个方格阵列，如图所示。精确的电路板布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。布线时电路只能沿直线或直角布线。为避免线路相交，已布线方格做上封闭标记，其他线路布线不允许穿过封闭区域。为讨论方便，我们假定电路板外面的区域为已加封闭标记的方格。ab20二、算法思想21解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。即加入剪枝的广度优先搜索。三、算法描述22Positionoffset[4];offset[0].row=0;offset[0].col=1;//右offset[1].row=1;offset[1].col=0;//下offset[2].row=0;offset[2].col=-1;//左offset[3].row=-1;offset[3].col=0;//上for(inti=0;i=m+1;i++)grid[0][i]=grid[n+1][i]=1;//顶部和底部for(inti=0;i=n+1;i++)grid[i][0]=grid[i][m+1]=1;//左翼和右翼for(inti=0;iNumOfNbrs;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.Add(nbr);}}找到目标位置后，可以通过回溯方法找到这条最短路径。复杂性：O(mn)定义移动方向的相对位移设置边界的围墙四、实例2332211A12212b23485678678ab6.50-1背包问题24一、问题描述二、算法思想三、上界函数四、算法描述一、问题描述250-1背包问题略二、算法思想26首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。