第10讲分支限界法.ppt

1、1,第10讲 分支限界法,2,10.1分支限界法的基本思想,分支限界法与回溯法 （1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,3,分支限界法的搜索策略,在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。 为了有效的选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值，并根据这些已计算出的函数值，从

2、当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解,4,5,10.1分支限界法的基本思想,分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。,此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。,6,常见的两种分支限界法,队列式(FIFO)分

3、支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。,7,例：考虑n =3 时0-1背包问题的一个实例如下：w =16,15,15, p= 45, 25,25,c = 30。其子集树,8,用队列式分支限界法解此问题,队列式分支限界法搜索解空间树的方式与解空间树的广度优先遍历算法极为相似，唯一的不同之处是队列式分支限界法不搜索以不可行结点为根的子树。,9,队列式,0,活结点队列,B ，C,16,0,C，E,16,F，G,15,0,45,16,G,30,50,15,25,15,25,0,0,E，

4、F，G,10,用优先队列式分支限界法解此问题,也是从根结点A开始搜索解空间树，用一个极大堆来表示活结点表的优先队列，该优先队列的优先级定义为活结点所获得的价值。初始时堆为空。,0,45,0,45,25,0,45,50,25,25,0,0,45,45,45,0,25,50,25,0,25,0,11,优先队列中规定的结点优先级常用一个与该结点相关的数值p来表示，结点优先级的高低与p值的大小相关，最大优先队列规定p值较大的结点优先级较高，用大堆来实现。 小优先队列规定p值较小的结点优先级较高，用小堆来实现。,12,当寻求问题的一个最优解时，可以用剪枝函数来加速搜索，该函数给出每一个可行结点相应的子树

5、可能获得的最大价值的上界。如果这个上界不会比当前最优值更大，则说明相应的子树中不含问题的最优解，因而可以剪去， 另一方面，我们也可以将上界函数确定的每个结点的上界值作为优先级，以该优先级的非增序抽取当前扩展结点，这种策略有时可以更迅速地找到最优解。,13,10.2 装载问题,1. 问题描述,有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且,装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。,容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满； (2)将剩余的

6、集装箱装上第二艘轮船。,14,算法思想,用一个队列Q来存放活结点表，Q中weight表示每个活结点所相应的当前载重量。当weight1时，表示队列已达到解空间树同一层结点的尾部。,算法首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。,活结点队列中的队首元素被取出作为当前扩展结点 取出元素不是-1时，活结点队列一定不空。由于队列中每一层结点之后都有一个尾部标记-1。 取出的元素是-1时，判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法

7、开始处理下一层的活结点。,2. 队列式分支限界法,15,0,16,31,16,31,16,0,15,30,0,15,15,0,16,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,1,活结点队列,扩展结点,17,算法包含两个函数 MaxLoading函数具体实施对解空间的分支限界搜索。 EnQueue用于将活结点加入到活结点队列中，该函数首先检查i是否等于n，如果i=n，则表示当前活结点为一个叶结点，由于叶结点不会被进一步扩展，因此不必加入到活结点，如果该叶结点表示的可行解优于当前最优解，更新最优解。

8、当in时，当前活结点是一个内部结点，加入到活结点队列中。,18,template void EnQueue( Queue / 不是叶子 ,19,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) / 检查左孩子结点 if (Ew + wi = c) / xi = 1 EnQueue( Q, Ew +

9、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+; / 进入下一层 ,20,3. 算法的改进,节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；Ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当Ew+rbestw时，

10、可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。,算法MaxLoading初始时将bestw置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶结点之前，总有bestw0，r0，故Ew+rbestw总是成立，也就是说，此时右子树测试不起作用。,算法中结点相应的重量仅在搜索进入左子树时增加，因此，可以在算法每一次进入左子树时更新bestw的值,21,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,22,使用定界函数进行改进 T MaxLoading( T w , T

11、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;,23,while (true) / 检查扩展结点的左孩子 T wt = Ew + wi; / 左孩子的权值 if (wt bestw) bestw = wt; if (i bestw ,24,3. 优先队列式分支限界法,存储活结点的方式: 最大优先队列存储

12、活结点表。 活结点x在优先队列中的优先级定义: 从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。 扩展结点的选择： 优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级x.uweight。子集树中叶结点所相应的载重量与其优先级相同。 算法终止条件： 子集树中叶结点所相应的载重量与其优先级相同，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。,25,可以用两种不同方式来实现,在结点优先队列的每一个活结点中保存从解空间树的根结点到该活结点的路径，在算法确定了达到最优值的叶结点时，就在

13、该叶结点处同时得到相应的最优解。 在算法的搜索进程中保存当前已构造出的部分解空间树，这样在算法确定了达到最优值的叶结点时，就可以在解空间树中从该叶结点开始向根结点回溯，构造出相应的最优解。,26,用一个元素类型为HeapNode的最大堆来表示活结点优先队列。解空间树中结点类型为bbnode template class HeapNode; class bbnode friend void AddLiveNode( MaxHeap ,27,用一个元素类型为HeapNode的最大堆来表示活结点优先队列。解空间树中结点类型为bbnode template class HeapNode friend

14、void AddLiveNode( MaxHeap /活结点在子集树中所处的层序号 ；,28,函数AddLiveNode以结点元素类型bbnode将一个新产生的活结点加入到子集树中，并以结点元素类型HeapNode将这个新结点插入到表示活结点优先队列的最大堆中 template Void AddLiveNode(MaxHeap ,向子集树中添加结点,向活结点优先队列插入新结点,29,函数MaxLoading具体实施对解空间的优先队列式分支限界搜索，在函数中，定义最大堆的容量为1000，即在运行期间，最多容纳1000个结点 第i+1层结点的剩余重量ri定义为第i+1到第n个物品重量的和。 变量E

15、指向子集树中当前扩展结点，Ew是相应的重量。算法开始时，i=1, Ew =0，子集树的根结点时扩展结点。,30,template Type MaxLoading(Type w , Type c, int n, int bestx ) /优先队列式分支限界法，返回最优载重量，bestx返回最优解 /定义最大堆的容量为1000 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;

16、 / 当前扩展结点所处的层 bbnode * E =0; /当前扩展结点 Type Ew = 0; /扩展结点所相应的载重量,31,while( i ! = n + 1 ) /非叶结点 /检查当前扩展结点的儿子结点 if( Ew + w i N; H.DeletMax(N); /非空 i = N.level; E = N.ptr; Ew = N. uweight r i -1 ; /优先权uweight = Ew + r i - 1; for( int j = n ; j 0; j - - ) /构造当前最优解 bestx j = E - LChild; E = E - parent; return Ew; ,32,优先队列,解空间树,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.DeletMax(N); i = N.level; E = N.ptr; Ew = N. uweight r i -1 ;,4