第七章-分支限界法new.ppt

1、第七章 分支限界法, 分支限界法的基本思想, 单源最短路径问题, 布线问题,North China Electric Power University, 方格调整问题,1 分支限界法的基本思想,分支限界法类似于回溯算法，也是一种在问题的解空间树T上搜索问题的解的算法。,和回溯法的区别：,1.求解目标不同：回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。,2.结点的扩展方式不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或最小耗费优先的方式

2、搜索解空间树，在扩展结点处，先生成所有的儿子结点，然后再从当前的扩展结点表中选择下一个扩展结点。,3.活结点成为扩展结点的机会不同：在回溯法中每个结点可能有多次机会成为扩展结点，而分支限界法中每个活结点只有一次机会成为扩展结点。,North China Electric Power University,分支限界法以广度优先或最小耗费优先的方式搜索问题的解空间树。在搜索问题的解空间树时，每一个活结点只有一次机会称为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有的儿子结点。在这些儿子结点中，那些导致不可行解或非最优解的儿子结点被舍弃，其余的儿子结点被加入活结点表中。此后，从活结点表中选择下

3、一个结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,分支限界法的搜索策略：,North China Electric Power University,根据从活结点表中选择下一结点的不同方式，分支限界法分为两类：,1)队列式分支限界法,队列式分支限界法将活结点表组织成一个队列，并按照队列的先进先出的原则选取下一个结点称为当前结点。,2)优先队列式分支限界法,优先队列式分支限界法将活结点表组织成一个优先队列，并按照优先队列中规定的优先级选取优先级最高的下一结点成为当前扩展结点。在算法实现时，通常用一个最大堆来实现最大优先队列，用最小堆来实现最小

4、优先队列。用优先队列法解具体问题时，应根据具体问题的特点选用最大优先队列活最小优先队列来表示解空间的活结点表。,A,B,C,D,E,F,G,H,I,J,L,K,M,N,O,x1=1,x1=0,x2=1,x2=0,x3=1,x3=0,x3=1,x3= 0,x2=1,x2=0,x3=1,x3=0,x3=1,x3=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,

5、35),(5,15),(20,40),(0,0),(0,0),(15,25),(20,40),(20,40),(0,0),(20,40),当前最优解,可行解,中间计算结果,A,B,C,D,E,F,G,H,I,J,L,K,M,N,O,1,0,1,0,1,0,1,0,1,0,1,0,1,0,解空间树T,例：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),(10,20),(5,15),(0,0),(0,0),堆是满足下列性质的数列R1, R2, ，Rn：

6、,或,若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左、右子树不空时，根结点的值小于(或大于)左、右子树根结点的值。,堆的补充知识,1. 堆的定义,2. 最小堆的C+描述,template class MinHeap Array array; int count; public: MinHeap(unsigned int n); MinHeap(); EnQueue(Object ,3. 最小堆的插入和删除,1)插入,3,4,6,7,5,插入2,3,4,6,7,5,3,4,6,7,5,3,4,6,7,5,2,void MinHeap:En

7、Queue(Object ,2)删除,3,4,6,7,5,删除2,4,3,6,7,5,4,3,6,7,5,2,3,4,7,5,6,3,4,7,5,6,Object ,North China Electric Power University,2.单源最短路径问题,1.问题描述,1,2,3,4,30,10,20,6,4,5,给定一个带权有向图G=(V,E)，其中每条边的权是一个非负实数。另外，还给定V中的一个顶点，称为源。计算从源到所有其他各顶点的最短路径长度。这里路径的长度是指路上各边权之和。这个问题称为单源最短路径问题。,例：下图为一包含4个顶点的无向图，其中顶点1为源，求顶点1到其它各顶点

8、的最短路径及其长度。,s,2.算法思想,单源最短路径问题可用分支限界法求解。由于要找的是从源到各顶点的最短路径，所以选用最小堆来表示优先队列。其优先级是结点所对应的当前路长。从图G的源s和空优先队列开始。结点s被扩展后，它的儿子结点依次被插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点邻接的所有顶点。如果从当前扩展顶点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j所相应的路径长度小于当前最优路径长度,则将该顶点作为活结点插入到活结点优先队列中。这个结点扩展过程一直重复到活结点优先队列为空时为止。,在具体实现算法时，用邻接矩阵表示所给的图G。用

9、数组dist记录从源到各顶点的距离；用数组prev记录从源到各顶点的路径上的前驱顶点。,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 ; pr

10、ivate: int i; /顶点编号 Type length; /当前路长 ;,template void Graph:ShortestPaths(int v) MinHeap H(1000); MinHeapNode E; E.i=v; E.length=0; distv=0; while(true) for(int j=1;j N; N.i=j; N.length=distj; H.Insert(N); try H.DeleteMin(E); catch(OutOfBounds) break; ,1,2,3,4,30,10,20,6,4,5,1, 0 , 0,dist1= ,0 dist

11、2=,30,14,11 dist3= ,6 dist4= ,4,2, 1, 30,3, 1, 6,4, 1, 4,3, 1, 6,2, 1, 30,E,H,4, 1, 4,2, 1, 30,3, 1, 6,2, 1, 30,3, 1, 6,2, 1, 30,2, 4, 14,3, 1, 6,2, 4, 14,2, 1, 30,2, 3, 11,2, 4, 14,prev1=0 prev2=1, 4 ,3 prev3=1 prev4=1,2, 3, 11,2, 1, 30,2, 4, 14,2, 4, 14,2, 1, 30,2, 1, 30,3.布线问题,1.问题描述,印刷电路板将布线区域分成

12、n*m个方格阵列。精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角进行。为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。如下图所示，在一个7*7的方格阵列中布线，其中起始位置a=(3,2),目标位置b=(4,6)，阴影方格表示被封锁的方格。,从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并将这些方格标记为1，即从起始方格a到这些方格的距离为1。接着，从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点

13、队列。这个过程一直持续到算法搜索到目标方格b或活结点队列为空时为止。,在实现上述算法时，首先定义一个表示电路板上方格位置的类Position，它的2个私有成员row和col分别表示方格所在的行和列。在电路板的任何一个方格处，布线可沿右、下、左、上四个方向进行。沿这4个方向的移动分别记为移动0,1,2,3。在下面的表格中，offseti.row和offseti.col(i=0,1,2,3)分别给出沿这4个方向前进1步相对于当前方格的相对位置。,2.算法思想,移动方向的相对位移,移动i,方向,offseti.row,offseti.col,0,右,0,1,1,下,1,0,2,左,0,-1,3,上,

14、-1,0,在实现上述算法时，用一个二维数组grid表示所给的方格阵列。,gridij=,0 方格ij允许布线,1 方格ij不允许布线,算法将起始位置的距离标记为2，因为0，1用于表示方格的开放或封锁状态，实际距离应为标记距离减2。算法从起始位置start开始，标记所有标记距离为3的方格并存入活结点队列，然后依次标记所有标记距离为4,5,的方格，直到达到目标方格finish或活结点队列为空时为止。,对于前面的例子，计算过程过程和结果如下：,由于每个方格成为活结点进入活结点队列最多1次，因此活结点队列中最多只处理O(mn)。每个扩展结点需O(1)时间，因此算法共耗时O(mn)。构造相应的最短距离需

15、要O(L)时间，其中L是最短布线路径的长度。,2,9,9,bool FindPath(Position start,Position finish,int ,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)所示，每一步只能将空格周围的字符与空格换位。,B,H,C,A,F,D,G,E,A,B,C,H,F,D,G,E,图(a),图(b),B,H,C,A,F,D,G,E,B,H,C,A,F,D,G,E,F进空格,1,2,3,4,4.方格调整问题,B,H,C,A,F,D,G,E,B,H,C,A,F,D,G,E,B,H,C,A,F,D,G,E,B,H,C,A,F,D,G,E,B,H,C,A,F,D,G,E,B,H,C,A,F,D,G,E,B,H,C,A,F,D,G,E,B,H,C,A,F,D,G,E,B,H,C,A