算法设计与分析讲义-中科院-陈玉福ch8

《算法设计与分析讲义-中科院-陈玉福ch8》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、154第八章分枝－限界法§1算法基本思想分枝限界法同回溯法类似，它也是在解空间中搜索问题的可行解或最优解，但搜索的方式不同。回溯法采用深度优先的方式，朝纵深方向搜索，直至达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点。然后，从该节点出发朝新的方向纵深搜索。分枝限界法则采用宽度优先的方式搜索解空间树，它将活节点存放在一个特殊的表中。其策略是：在扩展节点处，首先生成其所有的儿子节点,将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活节点表中。然后，从活节点表中取出一个节点作

2、为当前扩展节点，重复上述节点扩展过程。分枝限界法与回溯法的本质区别在于搜索方式的不同。回溯法更适于处理那些寻求所有可行解的问题，而分枝限界法更适于处理求最优解的问题。从活节点表中选择下一扩展节点的不同方式导致不同的分枝限界法。最常见的有以下两种方式：1).队列式（FIFO）分枝限界法：这种方式是将活节点表组织成一个队列，并按队列的先进先出原则选取下一个节点作为当前扩展节点。2).优先队列式分枝限界法：这种方式是将活节点表组织成一个优先队列，并按优先队列给节点规定的优先级选取优先级最高的下一个节点作为当前扩展节点。队列式分枝限界法搜索解空间树的方式类似于解空间

3、树的宽度优先搜索，不同的是队列式分枝限界法不搜索不可行节点（已经被判定不可能导致可行解或不可能导致最优解的节点）为根的子树。为达此目的，算法不把这样的节点列入活节点表。优先队列式分枝限界法的搜索方式是根据活节点表中节点的优先级确定下一个扩展节点。节点的优先级常用一个与该节点有关的数值p来表示。最大优先队列规定p值较大的节点的优先级较高。在算法实现时通常用一个最大堆来实现最大优先队列，用最大堆的Deletemax运算抽取堆中的下一个节点作为当前扩展节点，体现最大效益优先的原则。类似地，最小优先队列规定p值较小的节点的优先级较高。在算法实现时，常用一个最小堆来实

4、现，用最小堆的Deletemin运算抽取堆中下一个节点作为当前扩展节点，体现最小优先的原则。采用优先队列式分枝限界算法解决具体问题时，应根据问题的特点选用最大优先或最小优先队列，确定各个节点的p值。155例1.1旅行商问题，n=4，其解空间树是一棵排列树。如文档“旅行商搜索树”。赋权图G给出如下：30125求赋权图G的6具有最小权的410Hamilton圈2043图8-1-1一个表示旅行商问题的赋权图采用队列式分枝限界法以排列树中的节点B作为初始扩展节点，此时，活节点队列为空。由于从图G的顶点1到顶点2、3和4均有边相连，B的儿子C、D和E都是可行节点，它们

5、被依次加入到活节点队列中。当前活节点队列中的队首节点C成为下一个扩展节点。由于图G的顶点2到顶点3和4有边相连，故节点C的二个儿子F和G均为可行节点，可以加入活节点队列。接下来，节点D和节点E相继成为扩展节点。此时活节点队列中的节点依次为F、G、H、I、J、K。节点F成为下一个扩展节点，但其儿子L是解空间树的叶节点，我们找到了一条Hamilton圈（1，2，3，4，1），其费用为59。此时记录这个目标函数值f=59。下一个扩展节点G的儿子M也是叶节点，得到另一条Hamilton圈（1，2，4，3，1），其费用为66。节点H成为当前扩展节点，其儿子N也是叶节点

6、，得到第三条Hamilton圈，其费用为25，因为它比记录中的目标函数值还小，所以修改目标函数值记录：f=25。下一个扩展节点是I，由于从根节点到节点I的费用26已经超过目标函数的当前值，故没有必要扩展I，以I为根的子树被剪掉。最后J和K被依次扩展，活节点队列成为空集，算法终止。算法搜索到的最优值是25，相应的最优解是从根节点到节点N的路径（1，3，2，4，1）。采用优先队列式分枝限界法，用一个最小堆存储活节点表，优先级函数值是节点的当前费用。算法还是从排列树的节点B和空队列开始。节点B被扩展后，它的3个儿子C、D和E被依次插入堆中。此时，由于E是堆中具有最

7、小当前费用（为4）的节点，所以处于堆顶的位置，它自然成为下一个扩展节点。节点E被扩展后，其儿子J和K被插入当前堆中，它们的费用分别为14和24。此时，堆顶元素是D，它成为下一个扩展节点。它的2个儿子H和I被插入堆中。此时，堆中元素是节点C、H、I、J、K。在这些节点中，H具有最小费用，成为下一个扩展节点。扩展节点H后得到一条Hamilton圈（1，3，2，4，1），相应的费用为25。接下来，节点J成为扩展节点，并由此得到一条Hamilton圈（1，4，2，1563，1），费用仍为25。此后的两个扩展节点是K和I。由节点K得到的Hamilton圈的费用高于当前

8、所知最小费用，节点I当前的费用已经高于当前所知最小费