《第6章分支限界法电子教案》由会员分享，可在线阅读，更多相关《第6章分支限界法电子教案（53页珍藏版）》请在金锄头文库上搜索。
1、第6章 分支限界法,郭艺辉 广东金融学院 计算机科学与技术系 办公室：1622 电话：13503000588，37215835 mail：校内邮箱,第6章 分支限界法,学习要点 理解分支限界法的剪枝搜索策略 掌握分支限界法的算法框架： （1）队列式分支限界法 （2）优先队式分支限界法,第6章 分支限界法,分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最
2、优解。,第6章 分支限界法,由于求解目标不同，导致分支限界法与回溯法对解空间的搜索方式也不相同。回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。 分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。这种方法称为分支限界法。,6.1 分支限界法的基本思想,从活结点表中选择下一扩展结点
3、的不同方式导致不同的分支限界法。最常见的有两种方式。 （1）队列式（FIFO）分支限界法 队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。 （2）优先队列式分支限界法 优先队列式的分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。,6.1 分支限界法的基本思想,优先队列中规定的结点优先级常用一个与该结点相关的数值P来表示。结点优先级的高低与P值的大小相关。最大优先队列规定P值较大的结点优先级较高。在算法实现时通常用最大堆来实现最大优先队列，用最大堆的 Deletemax运算抽取堆中下一
4、个结点成为当前扩展结点，体现最大效益优先的原则。 类似地，最小优先队列规定P值较小的结点优先级较高。在算法实现时通常用最小堆来实现最小优先队列，用最小堆的Deletemin运算抽取堆中下一个结点成为当前扩展结点，体现最小费用优先的原则。 用优先队列式分支限界法解具体问题时，应根据具体问题的特点确定选用最大优先队列或最小优先队列来表示解空间的活结点表。,6.1 分支限界法的基本思想,0-1背包队列式分支限界法： A B, C = B, C B, C D, E = E C, E F, G = F, G E, F, G J, K = K(45) 1,0,0 F, G L, M =L(50) 0, 1
5、, 1 M(25) G N, O =N(25), O(0) ,例如，考虑n=3时0-l背包问题如下： w=16，15，15， P= 45，25，25, C=30。,6.1 分支限界法的基本思想,0-1背包优先队列式分支限界法： A B, C = B(45), C(0) B, C D, E = E(45) E, C J, K = K(45) 1, 0, 0 C F, G = F(25), G(0) F, G L, M = L(50), 0, 1, 1 M(25) G N, O = N(25), O(0) ,例如，考虑n=3时0-l背包问题如下： w=16，15，15， P= 45，25，25,
6、C=30。,6.1 分支限界法的基本思想,用队列式分支限界法解此问题时，算法从根结点A开始。初始时活结点队列为空，结点A是当前扩展结点。结点A的2个儿子结点B和C均为可行结点，故将这2个儿子结点按从左到右的顺序加入活结点队列，并且舍弃当前扩展结点A。依先进先出原则，下一个扩展结点是活结点队列的队首结点B。扩展结点B得到其儿子结点D和E。由于D是不可行结点，故被舍去。E是可行结点，被加入活结点队列。接下来，C成为当前扩展结点，它的2个儿子结点F和G均为可行结点，因此被加入到活结点队列中。扩展下一个结点E得到结点J和K。J是不可行结点，因而被舍去。K是可行的叶结点，表示所求问题的一个可行解，其价值
7、为45。,6.1 分支限界法的基本思想,当前活结点队列的队首结点F成为下一个扩展结点。它的2个儿子结点L和M均为叶结点。L表示获得价值为50的可行解；M表示获得价值为25的可行解。G是最后的一个扩展结点，其儿子结点N和O均为可行叶结点。最后，活结点队列已空，算法终止。算法搜索得到最优值为50。,6.1 分支限界法的基本思想,优先队列式分支限界法从根结点A开始搜索解空间树。用一个极大堆表示活结点表的优先队列。初始时堆为空，扩展结点A得到它的2个儿子结点B和C。这2个结点均为可行结点，因此被加入到堆中，结点A被舍弃。结点B获得的当前价值是45，而结点C的当前价值为0。由于结点B的价值大于结点C的价
8、值，所以结点B是堆中最大元素，从而成为下一个扩展结点扩展结点B得到结点D和E。D不是可行结点，因而被舍去。E是可行结点被加入到堆中。E的价值为45，成为当前堆中最大元素，从而成为下一个扩展结点。扩展结点E得到2个叶结点J和 K。J是不可行结点，被舍弃。K是可行叶结点，表示所求问题的一个可行解，其价值为 45。,6.1 分支限界法的基本思想,此时，堆中仅剩下一个活结点C，它成为当前扩展结点。它的2个儿子结点F和G均为可行结点，因此被插入到当前堆中。结点F的价值为25，是堆中最大元素，成为下一个扩展结点。结点F的2个儿子结点L和M均为叶结点。叶结点L相应于价值为50的可行解。叶结点M相应于价值为2
9、5的可行解。叶结点L所相应的解成为当前最优解。最后，结点G成为扩展结点，其儿子结点N和O均为叶结点，它们的价值分别为25和0。接下来，存储活结点的堆已空，算法终止。算法搜索得到最优值为 50。相应的最优解是从根结点 A到结点L的路径（0，1，1）。,6.1 分支限界法的基本思想,在寻求问题的最优解时，与讨论回溯法时类似，可以用剪枝函数加速搜索。该函数给出每一个可行结点相应的子树可能获得的最大价值的上界。如果这个上界不会比当前最优值更大，则说明相应的子树中不含问题的最优解，因而可以剪去。另一方面，也可以将上界函数确定的每个结点的上界值作为优先级，以该优先级的非增序抽取当前扩展结点。这种策略有时可
10、以更迅速地找到最优解。,6.1 分支限界法的基本思想,旅行售货员问题,问题描述：某售货员要到若干城市去推销商品，已知各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。,6.1 分支限界法的基本思想,旅行售货员问题 队列式分支限界法： A B, B C, D,E C, D,E F,G D, E, F,G H,I E, F, G, H,I J,K F, G, H, I, J,K L(59) 1,2,3,4 G, H, I, J,K M(66) H, I, J,K N(25) 1, 3, 2, 4 I, J,K 1-3-4(限界掉) /I(26) J,K
11、 (限界掉) /P(25) K (限界掉) /Q(59),例旅行售货员问题,6.1 分支限界法的基本思想,旅行售货员问题 优先队列式分支限界法： A B B C, D ,E= C(30), D(6),E(4) E, D, C J,K= D(6),C(30),J(14),K(24) D, J,K,C H,I =J(14),K(24), C(30),H(11),I(26) H,J,K,I,C N = N(25) 1, 3, 2, 4 J, K,I,C P(25)限界掉 K,I,C Q(59)限界掉 I,C I(26),C(30)限界掉,6.1 分支限界法的基本思想,解此问题的队列式分支限界法以排列
12、树中结点B作为初始扩展结点。此时，活结点队列为空。由于从图G的顶点1到顶点2，3和4均有边相连，所以结点B的儿子结点C，D，E均为可行结点，它们被加入到活结点队列中，并舍去当前扩展结点B。当前活结点队列中的队首结点C成为下一个扩展结点。由于图G的顶点2到顶点3和4有边相连，故结点C的2个儿子结点F和G均为可行结点，从而被加入到活结点队列中。接下来，结点D和结点E相继成为扩展结点而被扩展。此时，活结点队列中的结点依次为F，G，H，I，J，K。,6.1 分支限界法的基本思想,结点F成为下一个扩展结点，其儿子结点L是叶结点。此时找到了一条旅行售货员回路，其费用为59。从下一个扩展结点G得到叶结点M，
13、它相应的旅行售货员回路的费用为66。结点H依次成为扩展结点，得到结点N相应的旅行售货员回路，其费用为25，这是当前最好的一条回路。下一个扩展结点是结点I，由于从根结点到叶结点I的费用26已超过了当前最优值，故没有必要扩展结点I，以结点I为根的子树被剪去。最后，结点J和K被依次扩展，活结点队列成为空，算法终止。算法搜索得到最优值为25，相应的最忧解是从根结点到结点N的路径（1，3，2，4，1）。,6.1 分支限界法的基本思想,解同一问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点的当前费用。算法还是从排列树的结点B和空优先队列开始。结点B被扩展后，它的3个儿子结点C，D和E被依
14、次插入堆中。此时，由于E是堆中具有最小当前费用（4）的结点，所以处于堆顶的位置，它自然成为下一个扩展结点。结点E被扩展后，其儿子结点J和K被插入当前堆中，它们的费用分别为14和24。此时，堆顶元素是结点D，它成为下一个扩展结点。它的2个儿子结点H和I被插入堆中。此时堆中含有结点C，H，I，J，K。在这些结点中，结点H具有最小费用，从而它成为下一个扩展结点。扩展结点H后得到一条旅行售货员回路（l，3，2，4，1），相应的费用为25。接下来，结点J成为扩展结点，由此得到另一条费用为25的回路门，4，2，3，1）。此后的2个扩展结点是结点K和I。由结点K得到的可行解费用高于当前最优解，结点I本身的费
15、用已高于当前最优解，从而它们都不能得到更好的解。最后，优先队列为空，算法终止。,6.1 分支限界法的基本思想,与0-1背包问题的例子类似，可以用一个限界函数在搜索过程中裁剪子树，以减少产生的活结点。此时剪枝函数是当前结点扩展后得到的最小费用的下界。如果在当前扩展结点处，这个下界不比当前最优值更小，则剪去以该结点为根的子树。另一方面，也可以把每个结点的下界作为优先级，依非减序从活结点优先队列中抽取下一个扩展结点。,6.3 装载问题,1.问题描述 有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为wi，且wiC1+C2 装载问题要求确定是否有一个合理的装载方案可将这n个
16、集装箱装上这2艘轮船。如果有，找出一种装载方案。 容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案： (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。,6.3 装载问题,将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近C1。由此可知，装载问题等价于以下特殊的0-1背包问题。,6.3 装载问题,6.3 装载问题：n=3, C1=C2=30, w=16, 15, 15,6.3 装载问题,用一个队列Q来存放活结点表，Q中weight表示每个活结点所相应的当前载重量。当weight1时，表示队列已达到解空间树同一层结点的尾部。 算法首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点 取出元素不是-1时，活结
