第七章分支限界法优秀PPT.ppt

《第七章分支限界法优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第七章分支限界法优秀PPT.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章分支限界法现在学习的是第1页，共27页第七章第七章 分支限界法分支限界法 分支限界法的基本思想分支限界法的基本思想 单源最短路径问题单源最短路径问题 布线问题布线问题North China Electric Power University 方格调整问题方格调整问题现在学习的是第2页，共27页1 1 分支限界法的基本思想分支限界法的基本思想 分支限界法类似于回溯算法，也是一种在问题的解空间树分支限界法类似于回溯算法，也是一种在问题的解空间树T上上搜索问题的解的算法。搜索问题的解的算法。和回溯法的区别：和回溯法的区别：1.求解目标不同：回溯法的求解目标是找出求解目标不同：回溯法的求解目标是

2、找出T中满足约束条件的所中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。的解，即在某种意义下的最优解。2.结点的扩展方式不同：回溯法以深度优先的方式搜索解空间树，而分支结点的扩展方式不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或最小耗费优先的方式搜索解空间树，在扩展结点限界法则以广度优先或最小耗费优先的方式搜索解空间树，在扩展结点处，先生成所有

3、的儿子结点，然后再从当前的扩展结点表中选择下一个处，先生成所有的儿子结点，然后再从当前的扩展结点表中选择下一个扩展结点。扩展结点。3.活结点成为扩展结点的机会不同：在回溯法中每个结点可能有多次机会活结点成为扩展结点的机会不同：在回溯法中每个结点可能有多次机会成为扩展结点，而分支限界法中每个活结点只有一次机会成为扩展结点。成为扩展结点，而分支限界法中每个活结点只有一次机会成为扩展结点。现在学习的是第3页，共27页North China Electric Power University 分支限界法以广度优先或最小耗费优先的方式搜索问题分支限界法以广度优先或最小耗费优先的方式搜索问题的解空间树。在

4、搜索问题的解空间树时，每一个活结点只有的解空间树。在搜索问题的解空间树时，每一个活结点只有一次机会称为扩展结点。活结点一旦成为扩展结点，就一次一次机会称为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有的儿子结点。在这些儿子结点中，那些导致不性产生其所有的儿子结点。在这些儿子结点中，那些导致不可行解或非最优解的儿子结点被舍弃，其余的儿子结点被加可行解或非最优解的儿子结点被舍弃，其余的儿子结点被加入活结点表中。此后，从活结点表中选择下一个结点成为当入活结点表中。此后，从活结点表中选择下一个结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续前扩展结点，并重复上述结点扩展过程。这个过

5、程一直持续到找到所需的解或活结点表为空时为止。到找到所需的解或活结点表为空时为止。分支限界法的搜索策略：分支限界法的搜索策略：现在学习的是第4页，共27页North China Electric Power University 根据从活结点表中选择下一结点的不同方式，分根据从活结点表中选择下一结点的不同方式，分支限界法分为两类：支限界法分为两类：1)1)队列式分支限界法队列式分支限界法 队列式分支限界法将活结点表组织成一个队列，并按队列式分支限界法将活结点表组织成一个队列，并按照队列的先进先出的原则选取下一个结点称为当前结点。照队列的先进先出的原则选取下一个结点称为当前结点。2)2)优先队列

6、式分支限界法优先队列式分支限界法 优先队列式分支限界法将活结点表组织成一个优先队列，优先队列式分支限界法将活结点表组织成一个优先队列，并按照优先队列中规定的优先级选取优先级最高的下一结点并按照优先队列中规定的优先级选取优先级最高的下一结点成为当前扩展结点。在算法实现时，通常用一个最大堆来实成为当前扩展结点。在算法实现时，通常用一个最大堆来实现最大优先队列，用最小堆来实现最小优先队列。用优先队现最大优先队列，用最小堆来实现最小优先队列。用优先队列法解具体问题时，应根据具体问题的特点选用最大优先队列法解具体问题时，应根据具体问题的特点选用最大优先队列活最小优先队列来表示解空间的活结点表。列活最小优

7、先队列来表示解空间的活结点表。现在学习的是第5页，共27页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,4

8、0)(0,0)(20,40)当前最优解当前最优解可行解可行解中间计算结果中间计算结果现在学习的是第6页，共27页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,

9、0)现在学习的是第7页，共27页堆是满足下列性质的数列堆是满足下列性质的数列RR1 1,R,R2 2,，R Rn n：或或若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左、右子树特性的完全二叉树：其左、右子树分别是堆，并且当左、右子树不空时，根结点的值小于不空时，根结点的值小于(或大于或大于)左、右子树根结点的值。左、右子树根结点的值。堆的补充知识堆的补充知识1.堆的定义堆的定义现在学习的是第8页，共27页2.最小堆的最小堆的C+描述描述template class MinHeap

10、Array array;int count;public:MinHeap(unsigned int n);MinHeap();EnQueue(Object&object);Object&DeleteMin();现在学习的是第9页，共27页3.最小堆的插入和删除最小堆的插入和删除1)插入插入34675插入插入2 23467534675346752现在学习的是第10页，共27页void MinHeap:EnQueue(Object&object)if(count=array.Length()throw domain_error(“priority queue is full”);+count;un

11、signed int i=count;while(i1)&(arrayi/2object)arrayi=arrayi/2;i=i/2;arrayi=&object;现在学习的是第11页，共27页2)删除删除34675删除删除2 2436754367523475634756现在学习的是第12页，共27页Object&MinHeap:DeleteMin()if(count=0)throw domain_error(“priority queue is emtpy”);Object&result=*array1;Object&last=*arraycount;-count;unsigned int

12、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;现在学习的是第13页，共27页North China Electric Power University2.2.单源最短路径问题单源最短路径问题 1.1.问题描述问题描述1234301020645 给定一个带权有向图给定一个带权有向图G=(V,E

13、)，其中每条边的权是一个非负实数。，其中每条边的权是一个非负实数。另外，还给定另外，还给定V中的一个顶点，称为中的一个顶点，称为源源。计算从源到所有其他各顶点的。计算从源到所有其他各顶点的最短路径长度。这里路径的长度是指路上各边权之和。这个问题称为最短路径长度。这里路径的长度是指路上各边权之和。这个问题称为单单源最短路径问题源最短路径问题。例：例：下图为一包含下图为一包含4个顶点的无向图，其中顶点个顶点的无向图，其中顶点1为源，求顶为源，求顶点点1到其它各顶点的最短路径及其长度。到其它各顶点的最短路径及其长度。s现在学习的是第14页，共27页2.2.算法思想算法思想 单源最短路径问题可用分支限

14、界法求解。由于要找的是从源到单源最短路径问题可用分支限界法求解。由于要找的是从源到各顶点的最短路径，所以选用最小堆来表示优先队列。其优先级各顶点的最短路径，所以选用最小堆来表示优先队列。其优先级是结点所对应的当前路长。从图是结点所对应的当前路长。从图G的源的源s和空优先队列开始。结点和空优先队列开始。结点s被扩展后，它的儿子结点依次被插入堆中。此后，算法从堆中取被扩展后，它的儿子结点依次被插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点邻接的所有顶点。如果从当前扩展顶点前扩展结点邻接的所有顶点

15、。如果从当前扩展顶点i到顶点到顶点j有边可有边可达，且从源出发，途经顶点达，且从源出发，途经顶点i再到顶点再到顶点j所相应的路径长度小于当前所相应的路径长度小于当前最优路径长度最优路径长度,则将该顶点作为活结点插入到活结点优先队列中。则将该顶点作为活结点插入到活结点优先队列中。这个结点扩展过程一直重复到活结点优先队列为空时为止。这个结点扩展过程一直重复到活结点优先队列为空时为止。在具体实现算法时，用邻接矩阵表示所给的图在具体实现算法时，用邻接矩阵表示所给的图G。用数组。用数组dist记录从源到各顶点的距离；用数组记录从源到各顶点的距离；用数组prev记录从源到各顶点的记录从源到各顶点的路径上的

16、前驱顶点。路径上的前驱顶点。现在学习的是第15页，共27页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

17、:int i;/顶点编号顶点编号 Type length;/当前路长当前路长;现在学习的是第16页，共27页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(

18、N);try H.DeleteMin(E);catch(OutOfBounds)break;现在学习的是第17页，共27页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现在学习的是第18页，共2

19、7页3.3.布线问题布线问题 1.1.问题描述问题描述 印刷电路板将布线区域分成印刷电路板将布线区域分成n*m个方格阵列。精确的电路布线问题个方格阵列。精确的电路布线问题要求确定连接方格要求确定连接方格a的中点到方格的中点到方格b的中点的最短布线方案。在布线时，的中点的最短布线方案。在布线时，电路只能沿直线或直角进行。为了避免线路相交，已布了线的方格做电路只能沿直线或直角进行。为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。如下图所示，在一了封锁标记，其他线路不允许穿过被封锁的方格。如下图所示，在一个个7*7的方格阵列中布线，其中起始位置的方格阵列中布线，其中起始

20、位置a=(3,2),目标位置目标位置b=(4,6)，阴，阴影方格表示被封锁的方格。影方格表示被封锁的方格。现在学习的是第19页，共27页 从起始位置从起始位置a开始将它作为第一个扩展结点。与该扩展结点开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并将相邻并且可达的方格成为可行结点被加入到活结点队列中，并将这些方格标记为这些方格标记为1，即从起始方格，即从起始方格a到这些方格的距离为到这些方格的距离为1。接着，。接着，从活结点队列中取出队首结点作为下一个扩展结点，并将与当前从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过

21、的方格标记为扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。，并存入活结点队列。这个过程一直持续到算法搜索到目标方格这个过程一直持续到算法搜索到目标方格b或活结点队列为空时或活结点队列为空时为止。为止。在实现上述算法时，首先定义一个表示电路板上方格位置的类在实现上述算法时，首先定义一个表示电路板上方格位置的类Position，它的，它的2个私有成员个私有成员row和和col分别表示方格所在的行和列。在分别表示方格所在的行和列。在电路板的任何一个方格处，布线可沿右、下、左、上四个方向进行。电路板的任何一个方格处，布线可沿右、下、左、上四个方向进行。沿这沿这4个方向的移动分别记为移动个方向

22、的移动分别记为移动0,1,2,3。在下面的表格中，。在下面的表格中，offseti.row和和offseti.col(i=0,1,2,3)分别给出沿这分别给出沿这4个方向前进个方向前进1步相对步相对于当前方格的相对位置。于当前方格的相对位置。2.2.算法思想算法思想现在学习的是第20页，共27页移动方向的相对位移移动方向的相对位移移动移动i方向方向offseti.rowoffseti.col0右右011下下102左左0-13上上-10 在实现上述算法时，用一个二维数组在实现上述算法时，用一个二维数组grid表示所给的方格阵列。表示所给的方格阵列。gridij=0 方格方格ij允许布线允许布线1

23、 方格方格ij不允许布线不允许布线 算法将起始位置的距离标记为算法将起始位置的距离标记为2，因为，因为0，1用于表示方格的开放用于表示方格的开放或封锁状态，实际距离应为标记距离减或封锁状态，实际距离应为标记距离减2。算法从起始位置。算法从起始位置start开开始，标记所有标记距离为始，标记所有标记距离为3的方格并存入活结点队列，然后依次标的方格并存入活结点队列，然后依次标记所有标记距离为记所有标记距离为4,5,的方格，直到达到目标方格的方格，直到达到目标方格finish或活结点或活结点队列为空时为止。队列为空时为止。现在学习的是第21页，共27页对于前面的例子，计算过程过程和结果如下：对于前面

24、的例子，计算过程过程和结果如下：由于每个方格成为活结点进入活结点队列最多由于每个方格成为活结点进入活结点队列最多1次，因此活结点次，因此活结点队列中最多只处理队列中最多只处理O(mn)。每个扩展结点需。每个扩展结点需O(1)时间，因此算法共耗时间，因此算法共耗时时O(mn)。构造相应的最短距离需要。构造相应的最短距离需要O(L)时间，其中时间，其中L是最短布线路是最短布线路径的长度。径的长度。299现在学习的是第22页，共27页bool FindPath(Position start,Position finish,int&Pathlen,Position*&path)if(start.row

25、=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;of

26、fset0.col=0;/上上 int NumOfNbrs=4;/相邻方格数相邻方格数 Position here,nbr;here.row=start.row;here.col=start.col;现在学习的是第23页，共27页 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.

27、col=j+2)break;here=nbr;/向前移动向前移动 return true;现在学习的是第25页，共27页问题：问题：已知已知3*3的格子上的布局如图的格子上的布局如图(a)所示，试将它调为如图所示，试将它调为如图(b)所示，每所示，每一步只能将空格周围的字符与空格换位。一步只能将空格周围的字符与空格换位。BHCAFDGEABCHFDGE图图(a)(a)图图(b)(b)BHCAFDGEBHCAFDGEF进空格进空格12344.4.方格调整问题方格调整问题 现在学习的是第26页，共27页BHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEBHCAFDGEFBCAHDGEBCFAHDEFHCBADEBHCGADEBHCADEFBHFADCGEGHCBFDEBHCFGDEBHEAFCDBHCAFEDCCFGAACGABCHFGEABCHDGEFD1234567891011121314151617181932现在学习的是第27页，共27页