算法分析与设计-第六章分支限界法

《算法分析与设计-第六章分支限界法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章分支限界法2学习要点理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架队列式(FIFO)分支限界法优先队列式分支限界法通过应用范例学习分支限界法的设计策略。单源最短路径问题装载问题；布线问题0-1背包问题；最大团问题；旅行售货员问题电路板排列问题批处理作业调度问题3引言分支限界法类似于回溯法，也是一种在问题的解空间树T中搜索问题解的算法。分支限界法与回溯法的求解目标不同：回溯法是找出满足约束条件的所有解分支限界法找出满足条件的一个解，或某种意义下的最优解搜索方式不同回溯法：深度优先分支限界法：广度优先或最小耗费优先4分支限界法的搜索策略在扩展结点处，先生成所有儿子结点

2、，此时所有的儿子结点都是活结点，并把这些活结点放在当前活结点表中。然后从当前活结点表中选择下一个扩展结点。为了有效地选择下一个扩展结点，以加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分之推进，以便尽快地找出一个最优解。5一、分支限界法的基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致

3、非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。6二、常见的两种分支限界法从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法：队列式(FIFO)分支限界法：活结用队列的方式存储，然后按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。最大优先队列：使用最大堆，体现最大效益优先最小优先队列：使用最小堆，体现最小费用优先7三、0-1背包问题考虑如下0-1背

4、包问题的实例：n=3,c=30,w=[16,15,15],p=[45,25,25]队列式分支限界法：[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,1]M(25)[G]N,0=>N(25),O(0)优先队列式分支限界法：[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)可用剪枝函数加速

5、搜索ABCDEFGHIJKLMNO108四、旅行售货员问题队列式分支限界法：[A]B,C,D[B,C,D]E,F[C,D,E,F]G,H[D,E,F,G,H]I,J[E,F,G,H,I,J]K(59)[1,2,3,4][F,G,H,I,J]L(66)[G,H,I,J]M(25)[1,3,2,4][H,I,J]1-3-4(26)[I,J]O(25)[J]P(59)优先队列式分支限界法：[A]B,C,D=>B(30),C(6),D(4)[D,C,B]I,J=>I(14),J(24)[C,I,J,B]G,H=>G(11),H(26)[G,I,J,B,H]M=>M(25)[1,3,2,

6、4][I,J,B,H]O=>O(25)[J,B,H]P=>P(59)[B,H]B,H限界掉1234643020510ABCDEFGHIJKLMNOP96.2单源最短路径问题1.问题描述下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。106.2单源最短路径问题1.问题描述下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。116.2单源最短路径问题2.算法思想解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表

7、。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。126.2单源最短路径问题3.剪枝策略在算法扩展结点的过程中，一旦发现