《计算机算法设计与分析-第6章 分支限界法》由会员分享，可在线阅读，更多相关《计算机算法设计与分析-第6章 分支限界法（80页珍藏版）》请在金锄头文库上搜索。
1、计算机算法设计与分析 Design and Analysis of Computer Algorithms,第六章 分支限界法 Branch-and-Bound Algorithm,2019年1月20日,2,理解分支限界法的剪枝搜索策略。 掌握分支限界法的算法框架 队列式(FIFO)分支限界法 优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。 单源最短路径问题 装载问题； 布线问题 0-1背包问题； 最大团问题； 旅行售货员问题 电路板排列问题 批处理作业调度问题,学习要点,2019年1月20日,3,提纲,一、分支限界法的基本思想 二、单源最短路径问题 三、装载问题 四、0-1背包
2、问题 五、最大团问题 六、旅行售货员问题,2019年1月20日,4,提纲,一、分支限界法的基本思想 二、单源最短路径问题 三、装载问题 四、0-1背包问题 五、最大团问题 六、旅行售货员问题,2019年1月20日,5,分支限界法同回溯法类似，它也是在解空间中搜索问题的可行解或最优解，但搜索的方式不同。回溯法采用深度优先的方式，朝纵深方向搜索，直至达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的结点。从该结点出发朝新的方向纵深搜索。分支定界法则采用宽度优先的方式搜索解空间树，它将活结点存放在一个特殊的表中。其策略是：在扩
3、展结点处，先生成其所有的儿子结点,将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。此后，从活结点表中取出一个结点作为当前扩展结点。并重复上述结点扩展过程。所以，分支限界法与回溯法的本质区别在于搜索方式的不同。回溯法更适于处理那些求所有可行解的问题，而分支限界法更适于处理那些只确定一个可行解，特别是最优化问题。,2019年1月20日,6,1.1 分支限界法与回溯法的比较,分支限界法类似于回溯法，也是一种在问题的解空间树T中搜索问题解的算法。 分支限界法与回溯法的求解目标（适用范围）不同： 回溯法适用于找出满足约束条件的所有解的情况； 分支限界法发誓找出满足条件的一个解，或某种
4、意义下的最优解。 搜索方式不同 回溯法：深度优先 分支限界法：广度优先,2019年1月20日,7,1.2 分支限界法的基本思想,分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,2019年1月20日,8,1.3 常见的两种分支限界法,从活结点表中选
5、择下一扩展结点的不同方式导致不同的分支限界法： 队列式(FIFO)分支限界法：将活结点表组织成一个队列，按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 优先队列式分支限界法：将活结点表组织成一个优先队列，按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 最大优先队列：使用最大堆，体现最大效益优先 最小优先队列：使用最小堆，体现最小费用优先,2019年1月20日,9,队列式分支限界法的搜索解空间树的方式类似于解空间树的宽度优先搜索，不同的是队列式分支限界法不搜索以不可行结点（已经被判定不能导致可行解或不能导致最优解的结点）为根的子树。这是因为，按照规则，这样的结点未被
6、列入活结点表。,2019年1月20日,10,优先队列式分支限界法的搜索方式是根据活结点的优先级确定下一个扩展结点。结点的优先级常用一个与该结点有关的数值p 来表示。 最大优先队列规定p 值较大的结点点的优先级较高。在算法实现时通常用一个最大堆来实现最大优先队列，用最大堆的Deletemax 运算抽取堆中的下一个结点作为当前扩展结点，体现最大效益优先的原则。 类似地，最小优先队列规定p 值较小的结点的优先级较高。在算法实现时，常用一个最小堆来实现，用最小堆的Deletemin 运算抽取堆中下一个结点作为当前扩展结点，体现最小优先的原则。,2019年1月20日,11,采用优先队列式分支定界算法解决
7、具体问题时，应根据问题的特点选用最大优先或最小优先队列，确定各个结点的p 值。,2019年1月20日,12,1.4 实例0-1背包问题,n=3, c=30, w=16,15,15, p=45,25,25,2019年1月20日,13,实例分析0-1背包问题,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) 不搜索以不
8、可行结点为根的子树 优先队列式分支限界法： 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) 可用剪枝函数加速搜索,2019年1月20日,14,1.5 实例TSP问题,问题描述：某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。,2019年1月20日,15,实例分析TSP问题,队列式分支
9、限界法： 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,1 G, H, I, J, K M(66) H, I, J, K N(25) 1, 3, 2, 4,1 I, J, K 1-3-4(26) J, K P(25) K Q(59) 优先队列式分支限界法： B C, D, E = C(30), D(6), E(4) E, D, C J, K = J(14), K(24) D, J, K, C H, I = H(11), I(26) H, J, K, I, C N
10、= N(25) 1, 3, 2, 4,1 J, K, I, C P = P(25) K, I, C Q = Q(59) I, C I, C 被限界掉,2019年1月20日,16,1.6 应用分支限界法的关键,如何确定合适的限界函数？ 如何组织活结点表？ 如何确定最优解中的各个分量？,好的限界函数不仅计算简单，还要保证最优解在搜索空间中，更重要的是能在搜索的早期对超出目标函数界的结点进行丢弃，减少搜索空间，从而尽快找到问题的最优解。,通常采用最大堆或最小堆来实现优先队列式分支限界法求解问题。,可以用如下方法求得最优解中的分量：1）对每个扩展结点保存该结点到根结点的路径；2）在搜索过程中构建搜索经
11、过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。,2019年1月20日,17,提纲,一、分支限界法的基本思想 二、单源最短路径问题 三、装载问题 四、0-1背包问题 五、最大团问题 六、旅行售货员问题,2019年1月20日,18,2.1单源最短路径问题定义,在有向图G中，每一边都有一个非负边权。求图G的从源顶点s到目标顶点t之间的最短路径。,2019年1月20日,19,用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。,有向图G的单源最短路径问题产生的解空间树,2019年1月20日,20,2
12、.2单源最短路径问题算法思想,用一最小堆来存储活结点表。其优先级是结点所对应的当前路长。 算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。,2019年1月20日,21,2.3 剪枝策略,在算法扩展结点的过程中，一旦发现一个结点的下界（即结点所对应的当前路长
13、）不小于当前找到的最短路长，则算法剪去以该结点为根的子树。 在算法中，还可以利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。 例如，从源点s出发，经过边a,e,q（路长为5）和经过边c,h（路长为6）的2条路径到达图G的同一顶点。故可将后一条路径剪掉。,2019年1月20日,22,剪枝策略,下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树的剪枝情况。,2019年1月20日,23,2.4 算法描述,while (true) for (int j = 1; j N;
14、N.i=j; N.length=distj; H.Insert(N); try H.DeleteMin(E); / 取下一扩展结点 catch (OutOfBounds) break; / 优先队列空 ,顶点i和j间有边，且此路径长小于原先从源点到j的路径长,2019年1月20日,24,实例,计算从源顶点1到其它顶点间最短路径,2019年1月20日,25,计算从源顶点V0 到其它顶点间最短路径,练习,2019年1月20日,26,提纲,一、分支限界法的基本思想 二、单源最短路径问题 三、装载问题 四、0-1背包问题 五、最大团问题 六、旅行售货员问题,2019年1月20日,27,3.1 问题定义
15、,有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为wi，且wiC1+C2 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。,2019年1月20日,28,解装载问题的队列式分支限界法只求出所要求的最优值，稍后将进一步讨论求出最优解。函数MaxLoading具体实施对解空间的分支限界搜索。其中队列Q用于存放活结点表。在队列Q的元素值表示每个活结点所相应的当前载重量。 当其值为1
16、时，表示队列已到达解空间树同一层结点的尾部。,3.2 队列式分支限界法,2019年1月20日,29,函数EnQueue用于将活结点加入到活结点队列中。该函数首先检查i是否等于n。如果in，则表示当前活结点为一个叶结点。由于叶结点不会被进一步扩展，因此不必加入到活结点队列中。此时只要检查该叶结点表示的可行解是否优于当前最优解，并适时更新当前最优解。当in时，当前活结点是一个内部结点，应加入到活结点队列中。,2019年1月20日,30,void EnQueue( / 不是叶子 ,2019年1月20日,31,函数MaxLoading在开始时将i初始化为1，bestw初始化为0。此时活结点队列为空。将同层结点尾部标志1加入到活结点队列中，表示此时位于第1层结点的尾部。Ew存储当前扩展结点所相应的重量。,2019年1月20日,32,队列式分支限界法,在算法的while循环中，
