第10讲分支限界法

《第10讲分支限界法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

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

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

7、前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。2.队列式分支限界法14016311631160153001515015－1－1160－1160163116311601530015150150160－1－116150－1活结点队列扩展结点16算法包含两个函数MaxLoading函数具体实施对解空间的分支限界搜索。EnQueue用于将活结点加入到活结点队列中，该函数首先检查i是否等于n，如果i=n，则表示当前活结点为一个叶结点，由于叶结点不会被进一步扩展，因此不必加入到活结点，如果该叶结点表示的可行解优于当前

8、最优解，更新最优解。当ivoid