第七章分支限界法

第七章分支限界法第一页，共二十七页，2022年，8月28日第七章分支限界法★分支限界法的基本思想★单源最短路径问题★布线问题NorthChinaElectricPowerUniversity★方格调整问题第二页，共二十七页，2022年，8月28日§1分支限界法的基本思想分支限界法类似于回溯算法，也是一种在问题的解空间树T上搜索问题的解的算法。和回溯法的区别：1.求解目标不同：回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。2.结点的扩展方式不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或最小耗费优先的方式搜索解空间树，在扩展结点处，先生成所有的儿子结点，然后再从当前的扩展结点表中选择下一个扩展结点。3.活结点成为扩展结点的机会不同：在回溯法中每个结点可能有多次机会成为扩展结点，而分支限界法中每个活结点只有一次机会成为扩展结点。第三页，共二十七页，2022年，8月28日NorthChinaElectricPowerUniversity分支限界法以广度优先或最小耗费优先的方式搜索问题的解空间树。在搜索问题的解空间树时，每一个活结点只有一次机会称为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有的儿子结点。在这些儿子结点中，那些导致不可行解或非最优解的儿子结点被舍弃，其余的儿子结点被加入活结点表中。此后，从活结点表中选择下一个结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

分支限界法的搜索策略：第四页，共二十七页，2022年，8月28日NorthChinaElectricPowerUniversity根据从活结点表中选择下一结点的不同方式，分支限界法分为两类：1)队列式分支限界法队列式分支限界法将活结点表组织成一个队列，并按照队列的先进先出的原则选取下一个结点称为当前结点。2)优先队列式分支限界法优先队列式分支限界法将活结点表组织成一个优先队列，并按照优先队列中规定的优先级选取优先级最高的下一结点成为当前扩展结点。在算法实现时，通常用一个最大堆来实现最大优先队列，用最小堆来实现最小优先队列。用优先队列法解具体问题时，应根据具体问题的特点选用最大优先队列活最小优先队列来表示解空间的活结点表。第五页，共二十七页，2022年，8月28日ABCDEFGHIJLKMNOx1=1x1=0x2=1x2=0x3=1x3=0x3=1x3=0x2=1x2=0x3=1x3=0x3=1x3=0例：0-1背包问题n=3，C=20，(p1,p2,p3)=(20,15,25)(w1,w2,w3)=(10,5,15)，求X=(x1,x2,x3)使背包价值最大？(10,20)(15,35)(15,35)(10,20)(10,20)(5,15)(20,40)(15,35)(5,15)(20,40)(0,0)(0,0)(15,25)(20,40)(20,40)(0,0)(20,40)当前最优解可行解中间计算结果第六页，共二十七页，2022年，8月28日ABCDEFGHIJLKMNO10101010101010解空间树T例：0-1背包问题n=3，C=20，(p1,p2,p3)=(20,15,25)(w1,w2,w3)=(10,5,15)，求X=(x1,x2,x3)使背包价值最大？B1020C00D1535E1020F515G00I1535当前最优解K1020M515N1525O00L2040当前最优解(10,20)(15,35)(10,20)(5,15)(0,0)(0,0)第七页，共二十七页，2022年，8月28日堆是满足下列性质的数列{R1,R2,…，Rn}：或若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左、右子树不空时，根结点的值小于(或大于)左、右子树根结点的值。堆的补充知识1.堆的定义第八页，共二十七页，2022年，8月28日2.最小堆的C++描述template<classObject>classMinHeap{Array<Object*>array;intcount;public:MinHeap(unsignedintn);~MinHeap();EnQueue(Object&object);Object&DeleteMin();}

第九页，共二十七页，2022年，8月28日3.最小堆的插入和删除1)插入34675插入23467534675346752第十页，共二十七页，2022年，8月28日voidMinHeap::EnQueue(Object&object){if(count==array.Length())throwdomain_error(“priorityqueueisfull”);++count;unsignedinti=count;while((i>1)&&(array[i/2]>object){array[i]=array[i/2];i=i/2;}array[i]=&object;}第十一页，共二十七页，2022年，8月28日2)删除34675删除2436754367523475634756第十二页，共二十七页，2022年，8月28日Object&MinHeap::DeleteMin(){if(count==0)throwdomain_error(“priorityqueueisemtpy”);Object&result=*array[1];Object&last=*array[count];--count;unsignedinti=1;while(2*i<count+1){unsignedintchild=2*i;if((child+1<count+1)&&(*array[child+1]<*array[child]))child+=1;if(last<=*array[child])break;array[i]=array[child];i=child;}array[i]=&last;returnresult;}第十三页，共二十七页，2022年，8月28日NorthChinaElectricPowerUniversity2.单源最短路径问题

1.问题描述1234301020645给定一个带权有向图G=(V,E)，其中每条边的权是一个非负实数。另外，还给定V中的一个顶点，称为源。计算从源到所有其他各顶点的最短路径长度。这里路径的长度是指路上各边权之和。这个问题称为单源最短路径问题。例：下图为一包含4个顶点的无向图，其中顶点1为源，求顶点1到其它各顶点的最短路径及其长度。s第十四页，共二十七页，2022年，8月28日2.算法思想

单源最短路径问题可用分支限界法求解。由于要找的是从源到各顶点的最短路径，所以选用最小堆来表示优先队列。其优先级是结点所对应的当前路长。从图G的源s和空优先队列开始。结点s被扩展后，它的儿子结点依次被插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点邻接的所有顶点。如果从当前扩展顶点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j所相应的路径长度小于当前最优路径长度,则将该顶点作为活结点插入到活结点优先队列中。这个结点扩展过程一直重复到活结点优先队列为空时为止。在具体实现算法时，用邻接矩阵表示所给的图G。用数组dist记录从源到各顶点的距离；用数组prev记录从源到各顶点的路径上的前驱顶点。第十五页，共二十七页，2022年，8月28日3.算法描述template<classType>classGraph{friendvoidmain(void);public:voidShortestPaths(int);private:intn;//图G的顶点数int*prev;//前驱顶点数组Type**c;//图G的邻接矩阵Type*dist;//最短距离数组};template<classType>classMinHeapNode{friendGraph<Type>;public:operatorint()const{returnlength};private:inti;//顶点编号Typelength;//当前路长};第十六页，共二十七页，2022年，8月28日template<classType>voidGraph<Type>::ShortestPaths(intv){MinHeap<MinHeapNode<Type>>H(1000);MinHeapNode<Type>E;E.i=v;E.length=0;dist[v]=0;while(true){for(intj=1;j<=n;j++)if((c[E.i][j]<inf)&&(E.length+c[E.i][j]<dist[j])){dist[j]=E.length+c[E.i][j];prev[j]=E.i;MinHeapNode<Type>N;N.i=j;N.length=dist[j];H.Insert(N);}try{H.DeleteMin(E);}catch(OutOfBounds){break;}}}第十七页，共二十七页，2022年，8月28日12343010206451,0,0dist[1]=∞,0dist[2]=∞,30,14,11dist[3]=∞,6dist[4]=∞,42,1,303,1,64,1,43,1,62,1,30EH4,1,42,1,303,1,62,1,303,1,62,1,302,4,143,1,62,4,142,1,302,3,112,4,14prev[1]=0prev[2]=1,4,3prev[3]=1prev[4]=12,3,112,1,302,4,142,4,142,1,302,1,30第十八页，共二十七页，2022年，8月28日3.布线问题

1.问题描述印刷电路板将布线区域分成n*m个方格阵列。精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角进行。为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。如下图所示，在一个7*7的方格阵列中布线，其中起始位置a=(3,2),目标位置b=(4,6)，阴影方格表示被封锁的方格。第十九页，共二十七页，2022年，8月28日从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并将这些方格标记为1，即从起始方格a到这些方格的距离为1。接着，从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直持续到算法搜索到目标方格b或活结点队列为空时为止。在实现上述算法时，首先定义一个表示电路板上方格位置的类Position，它的2个私有成员row和col分别表示方格所在的行和列。在电路板的任何一个方格处，布线可沿右、下、左、上四个方向进行。沿这4个方向的移动分别记为移动0,1,2,3。在下面的表格中，offset[i].row和offset[i].col(i=0,1,2,3)分别给出沿这4个方向前进1步相对于当前方格的相对位置。2.算法思想第二十页，共二十七页，2022年，8月28日移动方向的相对位移移动i方向offset[i].rowoffset[i].col0右011下102左0-13上-10在实现上述算法时，用一个二维数组grid表示所给的方格阵列。grid[i][j]=0方格[i][j]允许布线1方格[i][j]不允许布线算法将起始位置的距离标记为2，因为0，1用于表示方格的开放或封锁状态，实际距离应为标记距离减2。算法从起始位置start开始，标记所有标记距离为3的方格并存入活结点队列，然后依次标记所有标记距离为4,5,…的方格，直到达到目标方格finish或活结点队列为空时为止。第二十一页，共二十七页，2022年，8月28日对于前面的例子，计算过程过程和结果如下：由于每个方格成为活结点进入活结点队列最多1次，因此活结点队列中最多只处理O(mn)。每个扩展结点需O(1)时间，因此算法共耗时O(mn)。构造相应的最短距离需要O(L)时间，其中L是最短布线路径的长度。299第二十二页，共二十七页，2022年，8月28日boolFindPath(Positionstart,Positionfinish,int&Pathlen,Position*&path){if((start.row==finish.row)&&(start.col==finish.col)){Pathlen=0;return;}//设置方格阵列“围墙”for(inti=0;i<=m+1;i++)grid[0][i]=grid[n+1][i]=1;//顶部和底部for(i=0;i<=n+1;i++)grid[i][0]=grid[i][m+1]=1;//左翼和右翼Positionoffset[4];offset[0].row=0;offset[0].col=1;//右offset[1].row=1;offset[0].col=0;//下offset[2].row=0;offset[0].col=-1;//左offset[3].row=-1;offset[0].col=0;//上intNumOfNbrs=4;//相邻方格数Positionhere,nbr;here.row=start.row;here.col=start.col;第二十三页，共二十七页，2022年，8月28日grid[start.row][start.col]=2;LinkQueue<Position>Q;do{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.Add(nbr);}}if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//完成布线if(Q.IsEmpt())returnfalse;//无解Q.Delete(here);//取下一扩展结点}while(true);第二十四页，共二十七页，2022年，8月28日//构造最短布线路径PathLen=grid[finish.row][finish.col]-2;path=newPosition[PathLen];//从目标位置finish开始向起始位置回溯here=finish;for(intj=PathLen-1;j>=0;j--){path[j]=here;//找前驱位置