第七章分支限界法精选文档.ppt
第七章分支限界法本讲稿第一页，共二十七页第七章第七章 分支限界法分支限界法 分支限界法的基本思想分支限界法的基本思想 单源最短路径问题单源最短路径问题 布线问题布线问题North China Electric Power University 方格调整问题方格调整问题本讲稿第二页，共二十七页1 1 分支限界法的基本思想分支限界法的基本思想 分支限界法类似于回溯算法，也是一种在问题的解空间树分支限界法类似于回溯算法，也是一种在问题的解空间树T上搜索上搜索问题的解的算法。问题的解的算法。和回溯法的区别：和回溯法的区别：1.求解目标不同：回溯法的求解目标是找出求解目标不同：回溯法的求解目标是找出T中满足约束条件的所中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。的解，即在某种意义下的最优解。2.结点的扩展方式不同：回溯法以深度优先的方式搜索解空间树，而分支结点的扩展方式不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或最小耗费优先的方式搜索解空间树，在扩展结点限界法则以广度优先或最小耗费优先的方式搜索解空间树，在扩展结点处，先生成所有的儿子结点，然后再从当前的扩展结点表中选择下一个处，先生成所有的儿子结点，然后再从当前的扩展结点表中选择下一个扩展结点。扩展结点。3.活结点成为扩展结点的机会不同：在回溯法中每个结点可能有多活结点成为扩展结点的机会不同：在回溯法中每个结点可能有多次机会成为扩展结点，而分支限界法中每个活结点只有一次机会成次机会成为扩展结点，而分支限界法中每个活结点只有一次机会成为扩展结点。为扩展结点。本讲稿第三页，共二十七页North China Electric Power University 分支限界法以广度优先或最小耗费优先的方式搜分支限界法以广度优先或最小耗费优先的方式搜索问题的解空间树。在搜索问题的解空间树时，每一索问题的解空间树。在搜索问题的解空间树时，每一个活结点只有一次机会称为扩展结点。活结点一旦成个活结点只有一次机会称为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有的儿子结点。在这为扩展结点，就一次性产生其所有的儿子结点。在这些儿子结点中，那些导致不可行解或非最优解的儿子些儿子结点中，那些导致不可行解或非最优解的儿子结点被舍弃，其余的儿子结点被加入活结点表中。此结点被舍弃，其余的儿子结点被加入活结点表中。此后，从活结点表中选择下一个结点成为当前扩展结点，后，从活结点表中选择下一个结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。所需的解或活结点表为空时为止。分支限界法的搜索策略：分支限界法的搜索策略：本讲稿第四页，共二十七页North China Electric Power University 根据从活结点表中选择下一结点的不同方式，分支限界根据从活结点表中选择下一结点的不同方式，分支限界法分为两类：法分为两类：1)1)队列式分支限界法队列式分支限界法 队列式分支限界法将活结点表组织成一个队列，并按照队列队列式分支限界法将活结点表组织成一个队列，并按照队列的先进先出的原则选取下一个结点称为当前结点。的先进先出的原则选取下一个结点称为当前结点。2)2)优先队列式分支限界法优先队列式分支限界法 优先队列式分支限界法将活结点表组织成一个优先队列，优先队列式分支限界法将活结点表组织成一个优先队列，并按照优先队列中规定的优先级选取优先级最高的下一结点并按照优先队列中规定的优先级选取优先级最高的下一结点成为当前扩展结点。在算法实现时，通常用一个最大堆来实成为当前扩展结点。在算法实现时，通常用一个最大堆来实现最大优先队列，用最小堆来实现最小优先队列。用优先队现最大优先队列，用最小堆来实现最小优先队列。用优先队列法解具体问题时，应根据具体问题的特点选用最大优先队列法解具体问题时，应根据具体问题的特点选用最大优先队列活最小优先队列来表示解空间的活结点表。列活最小优先队列来表示解空间的活结点表。本讲稿第五页，共二十七页ABCDEFGHIJLKMNOx1=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)当前最优解当前最优解可行解可行解中间计算结果中间计算结果本讲稿第六页，共二十七页ABCDEFGHIJLKMNO10101010101010解空间树解空间树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)本讲稿第七页，共二十七页堆是满足下列性质的数列堆是满足下列性质的数列RR1 1,R,R2 2,，R Rn n：或或若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左、右子树不空时，根结点的全二叉树：其左、右子树分别是堆，并且当左、右子树不空时，根结点的值小于值小于(或大于或大于)左、右子树根结点的值。左、右子树根结点的值。堆的补充知识堆的补充知识1.堆的定义堆的定义本讲稿第八页，共二十七页2.最小堆的最小堆的C+描述描述template class MinHeap Array array;int count;public:MinHeap(unsigned int n);MinHeap();EnQueue(Object&object);Object&DeleteMin();本讲稿第九页，共二十七页3.最小堆的插入和删除最小堆的插入和删除1)插入插入34675插入插入2 23467534675346752本讲稿第十页，共二十七页void 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;本讲稿第十一页，共二十七页2)删除删除34675删除删除2 2436754367523475634756本讲稿第十二页，共二十七页Object&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 University2.2.单源最短路径问题单源最短路径问题 1.1.问题描述问题描述1234301020645 给定一个带权有向图给定一个带权有向图G=(V,E)，其中每条边的权是一个非负实数。，其中每条边的权是一个非负实数。另外，还给定另外，还给定V中的一个顶点，称为中的一个顶点，称为源源。计算从源到所有其他各顶点。计算从源到所有其他各顶点的最短路径长度。这里路径的长度是指路上各边权之和。这个问的最短路径长度。这里路径的长度是指路上各边权之和。这个问题称为题称为单源最短路径问题单源最短路径问题。例：例：下图为一包含下图为一包含4个顶点的无向图，其中顶点个顶点的无向图，其中顶点1为源，求顶为源，求顶点点1到其它各顶点的最短路径及其长度。到其它各顶点的最短路径及其长度。s本讲稿第十四页，共二十七页2.2.算法思想算法思想 单源最短路径问题可用分支限界法求解。由于要找的是从源到单源最短路径问题可用分支限界法求解。由于要找的是从源到各顶点的最短路径，所以选用最小堆来表示优先队列。其优先级各顶点的最短路径，所以选用最小堆来表示优先队列。其优先级是结点所对应的当前路长。从图是结点所对应的当前路长。从图G的源的源s和空优先队列开始。结点和空优先队列开始。结点s被扩展后，它的儿子结点依次被插入堆中。此后，算法从堆中取被扩展后，它的儿子结点依次被插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点邻接的所有顶点。如果从当前扩展顶点前扩展结点邻接的所有顶点。如果从当前扩展顶点i到顶点到顶点j有边可有边可达，且从源出发，途经顶点达，且从源出发，途经顶点i再到顶点再到顶点j所相应的路径长度小于当前所相应的路径长度小于当前最优路径长度最优路径长度,则将该顶点作为活结点插入到活结点优先队列中。则将该顶点作为活结点插入到活结点优先队列中。这个结点扩展过程一直重复到活结点优先队列为空时为止。这个结点扩展过程一直重复到活结点优先队列为空时为止。在具体实现算法时，用邻接矩阵表示所给的图在具体实现算法时，用邻接矩阵表示所给的图G。用数组。用数组dist记录从源到各顶点的距离；用数组记录从源到各顶点的距离；用数组prev记录从源到各顶点的记录从源到各顶点的路径上的前驱顶点。路径上的前驱顶点。本讲稿第十五页，共二十七页3.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;/当前路长当前路长;本讲稿第十六页，共二十七页template 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;本讲稿第十七页，共二十七页12343010206451,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,30本讲稿第十八页，共二十七页3.3.布线问题布线问题 1.1.问题描述问题描述 印刷电路板将布线区域分成印刷电路板将布线区域分成n*m个方格阵列。精确的电路布线个方格阵列。精确的电路布线问题要求确定连接方格问题要求确定连接方格a的中点到方格的中点到方格b的中点的最短布线方案。在的中点的最短布线方案。在布线时，电路只能沿直线或直角进行。为了避免线路相交，已布了布线时，电路只能沿直线或直角进行。为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。如下线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。如下图所示，在一个图所示，在一个7*7的方格阵列中布线，其中起始位置的方格阵列中布线，其中起始位置a=(3,2),目标目标位置位置b=(4,6)，阴影方格表示被封锁的方格。，阴影方格表示被封锁的方格。本讲稿第十九页，共二十七页 从起始位置从起始位置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.算法思想算法思想本讲稿第二十页，共二十七页移动方向的相对位移移动方向的相对位移移动移动i方向方向offseti.rowoffseti.col0右右011下下102左左0-13上上-10 在实现上述算法时，用一个二维数组在实现上述算法时，用一个二维数组grid表示所给的方格阵列。表示所给的方格阵列。gridij=0 方格方格ij允许布线允许布线1 方格方格ij不允许布线不允许布线 算法将起始位置的距离标记为算法将起始位置的距离标记为2，因为，因为0，1用于表示方格的开放或用于表示方格的开放或封锁状态，实际距离应为标记距离减封锁状态，实际距离应为标记距离减2。算法从起始位置。算法从起始位置start开始，标开始，标记所有标记距离为记所有标记距离为3的方格并存入活结点队列，然后依次标记所有标记的方格并存入活结点队列，然后依次标记所有标记距离为距离为4,5,的方格，直到达到目标方格的方格，直到达到目标方格finish或活结点队列为空时为或活结点队列为空时为止。止。本讲稿第二十一页，共二十七页对于前面的例子，计算过程过程和结果如下：对于前面的例子，计算过程过程和结果如下：由于每个方格成为活结点进入活结点队列最多由于每个方格成为活结点进入活结点队列最多1次，因此活结点队列次，因此活结点队列中最多只处理中最多只处理O(mn)。每个扩展结点需。每个扩展结点需O(1)时间，因此算法共耗时时间，因此算法共耗时O(mn)。构造相应的最短距离需要构造相应的最短距离需要O(L)时间，其中时间，其中L是最短布线路径的长度。是最短布线路径的长度。299本讲稿第二十二页，共二十七页bool 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;本讲稿第二十三页，共二十七页 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;本讲稿第二十五页，共二十七页问题：问题：已知已知3*3的格子上的布局如图的格子上的布局如图(a)所示，试将它调为如图所示，试将它调为如图(b)所示，所示，每一步只能将空格周围的字符与空格换位。每一步只能将空格周围的字符与空格换位。BHCAFDGEABCHFDGE图图(a)(a)图图(b)(b)BHCAFDGEBHCAFDGEF进空格进空格12344.4.方格调整问题方格调整问题 本讲稿第二十六页，共二十七页BHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEFBCAHDGEBCFAHDEFHCBADEBHCGADEBHCADEFBHFADCGEGHCBFDEBHCFGDEBHEAFCDBHCAFEDCCFGAACGABCHFGEABCHDGEFD1234567891011121314151617181932本讲稿第二十七页，共二十七页
