算法分析与设计第6章详解.ppt

1、1,第6章 分支限界法 Branch and Bound,2,主要内容,6.1分支限界法的基本思想 6.2 单源最短路径问题 6.3 装载问题 6.4 0-1背包问题,3,6.1分支限界法的基本思想,Breadth-first search 分支限界法与回溯法 （1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,6.1分支限界法的基本思想,4,分支限界法的

2、搜索策略,在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。 为了有效的选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值，并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解 。,6.1分支限界法的基本思想,5,w = 16,15,15,v = 45, 25, 25, c = 30,6.1分支限界法的基本思想,6,分支限界法的基本思想,分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。,此后，从活结点表中取下一结点成为当前

3、扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。,6.1分支限界法的基本思想,7,常见的两种分支限界法,队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 优先队列式(priority queue)分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。,6.1分支限界法的基本思想,8,例：考虑n =3

4、 时0-1背包问题的一个实例如下： w =16,15,15, p= 45, 25,25,c = 30。其子集树,6.1分支限界法的基本思想,9,用队列式分支限界法解此问题,队列式分支限界法搜索解空间树的方式与解空间树的广度优先遍历算法极为相似，唯一的不同之处是队列式分支限界法不搜索以不可行结点为根的子树。,6.1分支限界法的基本思想,10,队列式,0,活结点队列,B ，C,16,0,C，E,16,F，G,15,0,45,16,G,30,50,15,25,15,25,0,0,E，F，G,6.1分支限界法的基本思想,w =16,15,15, p= 45, 25,25,c = 30,11,用优先队列

5、式分支限界法解此问题,也是从根结点A开始搜索解空间树，用一个极大堆来表示活结点表的优先队列，该优先队列的优先级定义为活结点所获得的价值。初始时堆为空。,0,45,0,45,25,0,45,50,25,25,0,0,45,45,45,0,25,50,25,0,25,0,6.1分支限界法的基本思想,w =16,15,15, p= 45, 25,25,c = 30,12,优先队列中规定的结点优先级常用一个与该结点相关的数值p来表示，结点优先级的高低与p值的大小相关，最大优先队列规定p值较大的结点优先级较高，用大堆来实现。 小优先队列规定p值较小的结点优先级较高，用小堆来实现。,6.1分支限界法的基本

6、思想,13,当寻求问题的一个最优解时，可以用剪枝函数来加速搜索，该函数给出每一个可行结点相应的子树可能获得的最大价值的上界。如果这个上界不会比当前最优值更大，则说明相应的子树中不含问题的最优解，因而可以剪去， 另一方面，我们也可以将上界函数确定的每个结点的上界值作为优先级，以该优先级的非增序抽取当前扩展结点，这种策略有时可以更迅速地找到最优解。,6.1分支限界法的基本思想,14,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,1,2,3,4,3,4,4,3,2,4,4,2,2,3,3,2,B,C,D,E,D,E,F,G,E,F,G,H,I,F,G,H,I,J,K,G,H,I

7、,J,K,59,H,I,J,K,66,I,J,K,25,J,K,K,队列,6.1分支限界法的基本思想,15,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,1,2,3,4,3,4,4,3,2,4,4,2,2,3,3,2,B，0,C,30,D,6,优先队列,E,4,J,14,K,24,H,11,I, 26,25,6.1分支限界法的基本思想,16,6.2单源最短路径,算法思想,解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。,算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。 此后，算法从堆中取出

8、具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。 如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。 这个结点的扩展过程一直继续到活结点优先队列为空时为止。,6.2单源最短路径,17,剪枝策略,在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。 在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪

9、去。,6.2单源最短路径,18,6.2单源最短路径,19,template class Graph friend void main(void); public: void ShortestPaths( int ); private: int n, *prev; /前驱顶点数组 Type *c, /图G的邻接矩阵 *dist; /最短距离数组 ;,template class MinHeapNode friend Graph; public: operator int () const return length; private: int i; /顶点编号 Type length; /当前路

10、长 ;,6.2单源最短路径,20,template void Graph: ShortestPaths( int v ) /单源最短路径问题的优先队列式分支限界法 /定义最小堆的容量为1000 MinHeap H(1000); /定义源为初始扩展结点 MinHeapNode E; E.i = v; E.length = 0; dist v =0; /搜索问题的解空间,6.2单源最短路径,21,while (true) for (int j = 1; j N; N.i=j; N.length=distj; H.Insert(N); try H.DeleteMin(E); / 取下一扩展结点，距源

11、点最近 catch (OutOfBounds) break; / 优先队列空 ,6.2单源最短路径,22,while 循环体完成对解空间内部结点的扩展，对于当前节结点，算法依次检查与当前扩展节点相邻的所有顶点。 如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到j的所有相应的路径长度小于当前最优路径长度，则将点j插入到活结点优先队列中。,23,6.2装载问题,1. 问题描述,有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为Wi，且,装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这2艘轮船。如果有，找出一种装载方案。,容易证明：如果一个给定

12、装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。,6.3装载问题,24,0,16,31,16,31,16,0,15,30,0,15,15,0,6.3装载问题,25,1,1,1,16,0,1,16,0,16,31,16,31,16,0,15,30,0,15,15,0,15,0,16,0,1,1,16,15,0,活结点队列,扩展结点,2. 队列式分支限界法,6.3装载问题,26,算法思想,用一个队列Q来存放活结点表，Q中weight表示每个活结点所相应的当前载重量。当weight1时，表示队列已达到解空间树同一层结点的尾部

13、。 算法首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。,6.3装载问题,27,该算法包含两个函数 MaxLoading函数具体实施对解空间的分支限界搜索。 EnQueue用于将活结点加入到活结点队列中，该函

14、数首先检查i是否等于n，如果i=n，则表示当前活结点为一个叶结点，由于叶结点不会被进一步扩展，因此不必加入到活结点，如果该叶结点表示的可行解优于当前最优解，更新最优解。当in时，当前活结点是一个内部结点，加入到活结点队列中。,6.3装载问题,28,template T MaxLoading(T w, T c, int n) / 返回最优装载值 / 为层次1 初始化 Queue Q; / 活结点队列 Q.Add(-1); /标记本层的尾部 int i = 1; / 当前扩展结点的层 T Ew = 0, / 当前扩展结点的权值 bestw = 0; / 目前的最优值,while (true) /

15、检查左孩子结点 if (Ew + wi = c) / xi = 1 EnQueue( Q, Ew + wi, bestw, i, n); / 右孩子总是可行的 EnQueue(Q, Ew, bestw, i, n); / xi = 0 Q.Delete(Ew); / 取下一个扩展结点 if (Ew = -1) / 到达层的尾部 if (Q.IsEmpty( ) return bestw; Q.Add(-1); / 同层结点的尾部 Q.Delete(Ew); / 取下一扩展结点 i+; / 进入下一层 ,29,template void EnQueue( Queue / 不是叶子 ,6.3装载问

16、题,30,3. 算法的改进,节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；Ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当Ew+rbestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。,算法MaxLoading初始时将bestw置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶结点之前，总有bestw0，r0，故Ew+rbestw总是成立，也就是说，此时右子树测试不起作用。,算法中结点相应的重量仅在搜索进入左子树时增加，因此，可以在算法每一次进入左子树时更新bestw的值。,6.2装载问题,

17、31,1,1,16,0,1,16,0,16,31,16,31,16,0,15,30,0,15,15,0,15,16,0,1,1,16,15,1,6.3装载问题,32,使用限界函数进行改进 T MaxLoading( T w , T c, int n ) Queue Q; / 活节点队列 Q.Add (-1) ; /标记本层的尾部 int i = 1; / 当前扩展节点的层 T Ew = 0, /当前扩展节点的重量 bestw = 0; / 目前的最优值 r = 0; / 当前扩展节点中余下的重量 for (int j = 2; j = n; j+) r + = wi;,6.3装载问题,33,w

18、hile (true) / 检查扩展结点的左孩子 T wt = Ew + wi; / 左孩子的权值 if (wt bestw) bestw = wt; / 若不是叶子，则添加到队列 if (i n) Q.Add(wt); ,6.3装载问题,34,/ 检查右孩子 if ( Ew + r bestw ,6.3装载问题,35,为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。,template class QNode QNode *parent; / 指向父结点的指针 bool L

19、Child; / 左儿子标志 Type weight; / 结点所相应的载重量 ;,4. 构造最优解,6.3装载问题,36,0,16,31,16,31,16,0,15,30,0,15,15,0,0,0 false,16 false,0,15 true,0,16 true,6.3装载问题,37,优先队列式分支限界法,存储活结点的方式: 最大优先队列存储活结点表。 活结点x在优先队列中的优先级定义: 从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。 扩展结点的选择： 优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级x.u

20、weight。子集树中叶结点所相应的载重量与其优先级相同。 算法终止条件： 子集树中叶结点所相应的载重量与其优先级相同，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。,6.3装载问题,如何证明？,38,可以用两种不同方式来实现,在结点优先队列的每一个活结点中保存从解空间树的根结点到该活结点的路径，在算法确定了达到最优值的叶结点时，就在该叶结点处同时得到相应的最优解。 在算法的搜索进程中保存当前已构造出的部分解空间树，这样在算法确定了达到最优值的叶结点时，就可以在解空间树中从该叶结点开始向根结点回溯，构造出相应的最优解。,6.2装载问题,39,优先队列

21、,解空间树,w = 16, 15, 15 ,r3= 0, r2=15, r1 = 30,两种结构：子集树结点结构，大堆结点结构,46 2,i=1 E=0,true,false,30 2,i=2 Ew=16,E,false,31 3,i=3 Ew=16,E,false,16 4,E,i=2 Ew=0,true,30 3,E,i=3 Ew=15,true,30 4,15 4,false,i=4 Ew=30,E,6.3装载问题,找到最优解 30,40,用一个元素类型为HeapNode的最大堆来表示活结点优先队列。解空间树中结点类型为bbnode。 template class HeapNode; c

22、lass bbnode friend void AddLiveNode( MaxHeap ,41,用一个元素类型为HeapNode的最大堆来表示活结点优先队列。解空间树中结点类型为bbnode template class HeapNode friend void AddLiveNode( MaxHeap /活结点在子集树中所处的层序号 ；,42,函数AddLiveNode以结点元素类型bbnode将一个新产生的活结点加入到子集树中，并以结点元素类型HeapNode将这个新结点插入到表示活结点优先队列的最大堆中。 template void AddLiveNode(MaxHeap ,向子集树中

23、添加结点,向活结点优先队列插入新结点,43,函数MaxLoading具体实施对解空间的优先队列式分支限界搜索，在函数中，定义最大堆的容量为1000，即在运行期间，最多容纳1000个结点。 第i+1层结点的剩余重量ri定义为第i+1到第n个物品重量的和。 变量E指向子集树中当前扩展结点，Ew是相应的重量。算法开始时，i=1, Ew =0，子集树的根结点为扩展结点。,6.2装载问题,44,template Type MaxLoading(Type w , Type c, int n, int bestx ) /优先队列式分支限界法，返回最优载重量，bestx返回最优解 /定义最大堆的容量为1000

24、 MaxHeap H( 1000 ); /定义剩余重量数组r Type * r = new Type n + 1 ; r n = 0; for( int j = n -1; j 0; j - -) r j = r j+1 + w j + 1 ; /初始化 int i = 1; / 当前扩展结点所处的层 bbnode * E =0; /当前扩展结点 Type Ew = 0; /扩展结点所相应的载重量,45,while( i ! = n + 1 ) /非叶结点 /检查当前扩展结点的儿子结点 if( Ew + w i N; H.DeletMax(N); /非空 i = N.level; E = N.

25、ptr; Ew = N. uweight r i -1 ; /优先权uweight = Ew + r i - 1; /end while for( int j = n ; j 0; j - - ) /构造当前最优解 bestx j = E - LChild; E = E - parent; /end for return Ew; ,46,优先队列,解空间树,w = 16, 15, 15 ,r n = 0; for( int j = n -1; j 0; j - -) r j = r j+1 + w j + 1 ;,r3= 0, r2=15, r1 = 30,if( Ew + w i N; H.

26、DeletMax(N); i = N.level; E = N.ptr; Ew = N. uweight r i -1 ;,46 2,i=1 E=0,true,false,30 2,i=2 Ew=16,E,false,31 3,i=3 Ew=16,E,false,16 4,E,i=2 Ew=0,true,30 3,E,i=3 Ew=15,true,30 4,15 4,false,i=4 Ew=30,E,6.2装载问题,47,true,false,false,false,true,true,false,for( int j = n ; j 0; j - - ) /构造当前最优解 bestx j

27、= E - LChild; E = E - parent; ,bestx3 = true,bestx2 = true,bestx1 = false,6.3装载问题,48,0-1背包问题,6.4 0-1背包问题,49,采用优先队列式分支限界,活结点优先队列中结点元素N的优先级由该结点的上界函数Bound计算出的值uprofit给出。 以结点N为根的子树中任一结点的价值不超过N.profit。,6.4 0-1背包问题,50,class Object : 描述物品 class bbnode: 子集树结点 class HeapNode: 优先队列结点 class Knap: 对整个问题的初始化及调用其

28、它函数解决问题 Knap: Bound(i) :计算第i层结点相应价值的上界 Knap: AddLiveNode(Typep up, Typep cp, Typew cw, bool ch, int level); ) 将一个新的活结点插入到子集树和最大堆H中 Knap: MaxKnapsack() :优先队列式分支限界法,6.4 0-1背包问题,51,class Object friend int Knapsack( int *, int *, int, int, int *); public: int operator = a.d); private: int ID; float d; /

29、单位重量价值 ,template class Knap; class bbnode /子集空间树中结点类型 friend Knap ; friend int Knapsack(int *, int *, int, int, int *); private: bbnode *parent; /指向父结点的指针 bool LChild; /左儿子结点标志 ;,6.4 0-1背包问题,52,template class HeapNode friend Knap ; public: operator Typep() const return uprofit; private: Typep uprofi

30、t, /结点的价值上界 profit; /结点所相应的价值 Typew weight; /结点所相应的重量 int level; /活结点在子集树中所处的层序号 bbnode * ptr; /指向活结点在子集树中相应结点的指针 ;,6.4 0-1背包问题,53,template class Knap friend Typep Knapsack(Typep *, Typew *, Typew, int, int *); public: Typep MaxKnapsack(); private: MaxHeap *H; Typep Bound( int i); void AddLiveNode(

31、Typep up, Typep cp, Typew cw, bool ch, int level); bbnode * E; /指向扩展结点的指针 Typew c; /背包容量 int n; /物品总数 Typew * w; /物品重量数组 Typep * p; /物品价值数组 Typew cw; /当前装包重量 Typep cp; /当前装包价值 int *bestx; /最优解 ；,6.4 0-1背包问题,54,函数MaxKnapsack实施对于子集树的优先队列式分支限界搜索,template Typep Knap: MaxKnapsack() /优先队列式分支限界法，返回最大价值，bestx返回最优解 /定义最大堆的容量为1000 H = new MaxHeap (1000); /为bestx分配存储空间 bestx = new int n+1 ; / 初始化 int i = 1; E = 0; cw = cp = 0; Typep bestp = 0; /当前最优值 Typep up = Boun