第七章-分支限界法new优秀PPT.ppt
North China Electric Power University第七章第七章 分支限界法分支限界法 分支限界法的基本思想分支限界法的基本思想 单源最短路径问题单源最短路径问题 布线问题布线问题North China Electric Power University 方格调整问题方格调整问题North China Electric Power University1 1 分支限界法的基本思想分支限界法的基本思想 分支限界法类似于回溯算法，也是一种在问题的解空间分支限界法类似于回溯算法，也是一种在问题的解空间树树T上搜寻问题的解的算法。上搜寻问题的解的算法。和回溯法的区分：和回溯法的区分：1.求解目标不同：回溯法的求解目标是找出求解目标不同：回溯法的求解目标是找出T中满足约束条件中满足约束条件的全部解，而分支限界法的求解目标则是找出满足约束条件的全部解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出访某一目标函数的一个解，或是在满足约束条件的解中找出访某一目标函数值达到极大或微小的解，即在某种意义下的最优解。值达到极大或微小的解，即在某种意义下的最优解。2.结点的扩展方式不同：回溯法以深度优先的方式搜寻解空间结点的扩展方式不同：回溯法以深度优先的方式搜寻解空间树，而分支限界法则以广度优先或最小耗费优先的方式搜寻树，而分支限界法则以广度优先或最小耗费优先的方式搜寻解空间树，在扩展结点处，先生成全部的儿子结点，然后再解空间树，在扩展结点处，先生成全部的儿子结点，然后再从当前的扩展结点表中选择下一个扩展结点。从当前的扩展结点表中选择下一个扩展结点。3.活结点成为扩展结点的机会不同：在回溯法中每个结点可能活结点成为扩展结点的机会不同：在回溯法中每个结点可能有多次机会成为扩展结点，而分支限界法中每个活结点只有有多次机会成为扩展结点，而分支限界法中每个活结点只有一次机会成为扩展结点。一次机会成为扩展结点。North China Electric Power UniversityNorth China Electric Power University 分支限界法以广度优先或最小耗费优先的方式分支限界法以广度优先或最小耗费优先的方式搜寻问题的解空间树。在搜寻问题的解空间树时，搜寻问题的解空间树。在搜寻问题的解空间树时，每一个活结点只有一次机会称为扩展结点。活结点每一个活结点只有一次机会称为扩展结点。活结点一旦成为扩展结点，就一次性产生其全部的儿子结一旦成为扩展结点，就一次性产生其全部的儿子结点。在这些儿子结点中，那些导致不行行解或非最点。在这些儿子结点中，那些导致不行行解或非最优解的儿子结点被舍弃，其余的儿子结点被加入活优解的儿子结点被舍弃，其余的儿子结点被加入活结点表中。此后，从活结点表中选择下一个结点成结点表中。此后，从活结点表中选择下一个结点成为当前扩展结点，并重复上述结点扩展过程。这个为当前扩展结点，并重复上述结点扩展过程。这个过程始终持续到找到所需的解或活结点表为空时为过程始终持续到找到所需的解或活结点表为空时为止。止。分支限界法的搜寻策略：分支限界法的搜寻策略：North China Electric Power UniversityNorth China Electric Power University 依据从活结点表中选择下一结点的不同方式，依据从活结点表中选择下一结点的不同方式，分支限界法分为两类：分支限界法分为两类：1)1)队列式分支限界法队列式分支限界法 队列式分支限界法将活结点表组织成一个队列，并队列式分支限界法将活结点表组织成一个队列，并依据队列的先进先出的原则选取下一个结点称为当前结依据队列的先进先出的原则选取下一个结点称为当前结点。点。2)2)优先队列式分支限界法优先队列式分支限界法 优先队列式分支限界法将活结点表组织成一个优先优先队列式分支限界法将活结点表组织成一个优先队列，并依据优先队列中规定的优先级选取优先级最高队列，并依据优先队列中规定的优先级选取优先级最高的下一结点成为当前扩展结点。在算法实现时，通常用的下一结点成为当前扩展结点。在算法实现时，通常用一个最大堆来实现最大优先队列，用最小堆来实现最小一个最大堆来实现最大优先队列，用最小堆来实现最小优先队列。用优先队列法解具体问题时，应依据具体问优先队列。用优先队列法解具体问题时，应依据具体问题的特点选用最大优先队列活最小优先队列来表示解空题的特点选用最大优先队列活最小优先队列来表示解空间的活结点表。间的活结点表。North China Electric Power UniversityABCDEFGHIJLKMNOx1=1x1=0 x2=1x2=0 x3=1x3=0 x3=1x3=0 x2=1x2=0 x3=1x3=0 x3=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)当前最优解当前最优解可行解可行解中间计算结果中间计算结果North China Electric Power UniversityABCDEFGHIJLKMNO10101010101010解空间树解空间树T 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)North China Electric Power University堆是满足下列性质的数列堆是满足下列性质的数列R1,R2,R1,R2,，RnRn：或或若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左、右列特性的完全二叉树：其左、右子树分别是堆，并且当左、右子树不空时，根结点的值小于子树不空时，根结点的值小于(或大于或大于)左、右子树根结点的值。左、右子树根结点的值。堆的补充学问堆的补充学问1.堆的定义堆的定义North China Electric Power University2.最小堆的最小堆的C+描述描述template class MinHeap Array array;int count;public:MinHeap(unsigned int n);MinHeap();EnQueue(Object&object);Object&DeleteMin();North China Electric Power University3.最小堆的插入和删除最小堆的插入和删除1)插入插入34675插入插入2 23467534675346752North China Electric Power Universityvoid MinHeap:EnQueue(Object&object)if(count=array.Length()throw domain_error(“priority queue is full”);+count;unsigned int i=count;while(i1)&(arrayi/2object)arrayi=arrayi/2;i=i/2;arrayi=&object;North China Electric Power University2)删除删除34675删除删除2 2436754367523475634756North China Electric Power UniversityObject&MinHeap:DeleteMin()if(count=0)throw domain_error(“priority queue is emtpy”);Object&result=*array1;Object&last=*arraycount;-count;unsigned int i=1;while(2*icount+1)unsigned int child=2*i;if(child+1count+1)&(*arraychild+1*arraychild)child+=1;if(last=*arraychild)break;arrayi=arraychild;i=child;arrayi=&last;return result;North China Electric Power UniversityNorth China Electric Power University2.2.单源最短路径问题单源最短路径问题 1.1.问题描述问题描述1234301020645 给定一个带权有向图给定一个带权有向图G=(V,E)，其中每条边的权是一个非，其中每条边的权是一个非负实数。另外，还给定负实数。另外，还给定V中的一个顶点，称为源。计算从源中的一个顶点，称为源。计算从源到全部其他各顶点的最短路径长度。这里路径的长度是指路到全部其他各顶点的最短路径长度。这里路径的长度是指路上各边权之和。这个问题称为单源最短路径问题。上各边权之和。这个问题称为单源最短路径问题。例：例：下图为一包含下图为一包含4个顶点的无向图，其中顶点个顶点的无向图，其中顶点1为源，求为源，求顶点顶点1到其它各顶点的最短路径及其长度。到其它各顶点的最短路径及其长度。sNorth China Electric Power University2.2.算法思想算法思想 单源最短路径问题可用分支限界法求解。由于要找的是单源最短路径问题可用分支限界法求解。由于要找的是从源到各顶点的最短路径，所以选用最小堆来表示优先队列。从源到各顶点的最短路径，所以选用最小堆来表示优先队列。其优先级是结点所对应的当前路长。从图其优先级是结点所对应的当前路长。从图G的源的源s和空优先队和空优先队列起先。结点列起先。结点s被扩展后，它的儿子结点依次被插入堆中。此被扩展后，它的儿子结点依次被插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点邻接的全部顶点。假如从结点，并依次检查与当前扩展结点邻接的全部顶点。假如从当前扩展顶点当前扩展顶点i到顶点到顶点j有边可达，且从源动身，途经顶点有边可达，且从源动身，途经顶点i再再到顶点到顶点j所相应的路径长度小于当前最优路径长度所相应的路径长度小于当前最优路径长度,则将该顶则将该顶点作为活结点插入到活结点优先队列中。这个结点扩展过程点作为活结点插入到活结点优先队列中。这个结点扩展过程始终重复到活结点优先队列为空时为止。始终重复到活结点优先队列为空时为止。在具体实现算法时，用邻接矩阵表示所给的图在具体实现算法时，用邻接矩阵表示所给的图G。用数。用数组组dist记录从源到各顶点的距离；用数组记录从源到各顶点的距离；用数组prev记录从源到各记录从源到各顶点的路径上的前驱顶点。顶点的路径上的前驱顶点。North China Electric Power University3.3.算法描述算法描述template class Graph friend void main(void);public:void ShortestPaths(int);private:int n;/图图G的顶点数的顶点数 int*prev;/前驱顶点数组前驱顶点数组 Type*c;/图图G的邻接矩阵的邻接矩阵 Type*dist;/最短距离数组最短距离数组;template class MinHeapNode friend Graph;public:operator int()const return length;private:int i;/顶点编号顶点编号 Type length;/当前路长当前路长;North China Electric Power Universitytemplate void Graph:ShortestPaths(int v)MinHeap MinHeapNode H(1000);MinHeapNode E;E.i=v;E.length=0;distv=0;while(true)for(int j=1;j=n;j+)if(cE.ijinf)&(E.length+cE.ijdistj)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;North China Electric Power University12343010206451,0,0dist1=,0dist2=,30,30,14,11 dist3=,6dist4=,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,14prev1=0prev2=1,4,3prev3=1prev4=12,3,112,1,302,4,142,4,142,1,302,1,30North China Electric Power University3.3.布线问题布线问题 1.1.问题描述问题描述 印刷电路板将布线区域分成印刷电路板将布线区域分成n*m个方格阵列。精确的电路个方格阵列。精确的电路布线问题要求确定连接方格布线问题要求确定连接方格a的中点到方格的中点到方格b的中点的最短布线的中点的最短布线方案。在布线时，电路只能沿直线或直角进行。为了避开线路方案。在布线时，电路只能沿直线或直角进行。为了避开线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。如下图所示，在一个封锁的方格。如下图所示，在一个7*7的方格阵列中布线，其的方格阵列中布线，其中起始位置中起始位置a=(3,2),目标位置目标位置b=(4,6)，阴影方格表示被封锁的，阴影方格表示被封锁的方格。方格。North China Electric Power University 从起始位置从起始位置a起先将它作为第一个扩展结点。与该扩展结起先将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，点相邻并且可达的方格成为可行结点被加入到活结点队列中，并将这些方格标记为并将这些方格标记为1，即从起始方格，即从起始方格a到这些方格的距离为到这些方格的距离为1。接着，从活结点队列中取出队首结点作为下一个扩展结点，并接着，从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为将与当前扩展结点相邻且未标记过的方格标记为2，并存入活，并存入活结点队列。这个过程始终持续到算法搜寻到目标方格结点队列。这个过程始终持续到算法搜寻到目标方格b或活结或活结点队列为空时为止。点队列为空时为止。在实现上述算法时，首先定义一个表示电路板上方格位置在实现上述算法时，首先定义一个表示电路板上方格位置的类的类Position，它的，它的2个私有成员个私有成员row和和col分别表示方格所在的分别表示方格所在的行和列。在电路板的任何一个方格处，布线可沿右、下、左、行和列。在电路板的任何一个方格处，布线可沿右、下、左、上四个方向进行。沿这上四个方向进行。沿这4个方向的移动分别记为移动个方向的移动分别记为移动0,1,2,3。在下面的表格中，在下面的表格中，offseti.row和和offseti.col(i=0,1,2,3)分别给分别给出沿这出沿这4个方向前进个方向前进1步相对于当前方格的相对位置。步相对于当前方格的相对位置。2.2.算法思想算法思想North China Electric Power University移动方向的相对位移移动方向的相对位移移动移动i方向方向offseti.rowoffseti.col0右右011下下102左左0-13上上-10 在实现上述算法时，用一个二维数组在实现上述算法时，用一个二维数组grid表示所给的方格阵表示所给的方格阵列。列。gridij=0 方格方格ij允许布线允许布线1 方格方格ij不允许布线不允许布线 算法将起始位置的距离标记为算法将起始位置的距离标记为2，因为，因为0，1用于表示方格用于表示方格的开放或封锁状态，实际距离应为标记距离减的开放或封锁状态，实际距离应为标记距离减2。算法从起始。算法从起始位置位置start起先，标记全部标记距离为起先，标记全部标记距离为3的方格并存入活结点队的方格并存入活结点队列，然后依次标记全部标记距离为列，然后依次标记全部标记距离为4,5,的方格，直到达到目的方格，直到达到目标方格标方格finish或活结点队列为空时为止。或活结点队列为空时为止。North China Electric Power University对于前面的例子，计算过程过程和结果如下：对于前面的例子，计算过程过程和结果如下：由于每个方格成为活结点进入活结点队列最多由于每个方格成为活结点进入活结点队列最多1次，因此次，因此活结点队列中最多只处理活结点队列中最多只处理O(mn)。每个扩展结点需。每个扩展结点需O(1)时间，时间，因此算法共耗时因此算法共耗时O(mn)。构造相应的最短距离须要。构造相应的最短距离须要O(L)时间，时间，其中其中L是最短布线路径的长度。是最短布线路径的长度。299North China Electric Power Universitybool FindPath(Position start,Position finish,int&Pathlen,Position*&path)if(start.row=finish.row)&(start.col=finish.col)Pathlen=0;return;/设置方格阵列设置方格阵列“围墙围墙”for(int i=0;i=m+1;i+)grid0i=gridn+1i=1;/顶部和底部顶部和底部 for(i=0;i=n+1;i+)gridi0=gridim+1=1;/左翼和右翼左翼和右翼 Position offset4;offset0.row=0;offset0.col=1;/右右 offset1.row=1;offset0.col=0;/下下 offset2.row=0;offset0.col=-1;/左左 offset3.row=-1;offset0.col=0;/上上 int NumOfNbrs=4;/相邻方格数相邻方格数 Position here,nbr;here.row=start.row;here.col=start.col;North China Electric Power University gridstart.rowstart.col=2;LinkQueue Q;do for(int i=0;i=0;j-)pathj=here;/找前驱位置找前驱位置 for(int i=0;iNumOfNbrs;i+)nbr.row=here.row+offseti.row;nbr.col=here.col+offseti.col;if(gridnbr.rownbr.col=j+2)break;here=nbr;/向前移动向前移动 return true;North China Electric Power University问题：问题：已知已知3*3的格子上的布局如图的格子上的布局如图(a)所示，试将它调为如图所示，试将它调为如图(b)所示，每一步只能将空格四周的字符与空格换位。所示，每一步只能将空格四周的字符与空格换位。BHCAFDGEABCHFDGE图图(a)(a)图图(b)(b)BHCAFDGEBHCAFDGEF进空格进空格12344.4.方格调整问题方格调整问题 North China Electric Power UniversityBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEFBCA HDGEBCFAH DEFHCBA DEBHCG A DEBHCAD EFBHFADCGEGHCBFDEBHCFGDEBHEAFCDBHCAFEDCCFGAACGA BCHFGEA BCHDGEFD1234567891011121314151617181932
