算法课件2015第6章分支限界法

《算法课件2015第6章分支限界法》由会员分享，可在线阅读，更多相关《算法课件2015第6章分支限界法（47页珍藏版）》请在金锄头文库上搜索。

1、1,第6章 分支限界法,马志强,2,学习要点,分支限界法的算法框架 队列式（FIFO）分支限界法 优先队列式分支限界法堆式分支限界法 应用分支限界法解决 单源最短路径问题 装载问题； 0-1背包问题； 旅行售货员问题 批处理作业调度问题,3,分支限界法的背景理查德.卡普,在IBM期间，深入研究了与实际应用有密切联系的一系列数学问题，如路径问题、背包问题、覆盖问题、匹配问题、分区问题、调度问题等，取得了许多出色的成果。这些问题有一个共同的特点，即如果用图来表示问题，那么当图中增加一个结点时，需要考察的可能的解的数目就急剧增加，形成所谓“组合爆炸” (combinatorial explosion

2、)，使计算机的计算工作量大大增加，到一定程度就根本无法实现。 以路径问题中最著名的旅行商问题为例，在卡普以前，最好的结果是Rand公司的丹齐格(George Benard Dantzig)、福格森(RFulkerson)和约翰逊(SJohnson)用手工和计算机相结合的办法，求出了包含49个城市的旅行商的最佳路线。卡普和他的同事海尔特(MHeld)经过反复研究，终于提出了一种称为“分支限界法”(branchandbound method)的新方法，用这种新方法实现的算法使旅行推销员能周游的城市数达到65个，从而打破了由Rand公司保持的记录。,1955年文学学士学位 1956年理科硕士学位 1

3、959年应用数学博士学位(哈佛大学) Yorktown Heights的IBM沃森研究中心 1985年获得ACM的图灵奖,4,分支限界法基础,8-Puzzle问题 输入: 具有8个编号小方块的魔方 输出: 移动序列, 经过这些移动, 魔方达目标状态,5,分支限界法基础,队列式（FIFO）分支限界法 广度优先搜索解空间树,A,B,C,D,E,F,G,A,B,C,D,E,F,G,6,分支限界法基础,优先队列式分支限界法堆式分支限界 为解空间树中的每个节点指定一个优先级测度函数 每次扩展树中优先级最高的节点 用最大（最小）堆来保存待搜索节点 8-Puzzle问题 测度函数 f (v) =节点v中处于

4、错误位置的方块数 每次扩展 f (v) 值最小的节点,7,B(3),C(3),D(4),E(4),F(2),G(4),H(1),I(0),J(2),A,A,B,C,D,E,F,G,H,最小堆,8,分支限界法基础,思想 广度优先或者优先级优先搜索解空间树 实现 每个节点只有一次机会成为扩展节点 一旦节点v成为扩展节点 将 v 的所有孩子加入到队列或者堆中 接着选取队列顶或堆顶节点作为下一个扩展节点 效率 耗时比回溯法少 需要空间比回溯法多,9,常见的两种分支限界法,（1）队列式分支限界法 按照队列先进先出（FIFO）或者后进先出（LIFO）原则选取下一个结点为扩展结点。,（2）优先队列式分支限界

5、法 队列式分支限界法对结点的选择规则相当死板，具有一定的 “盲目”性。这种选择规则不利于快速检索到一个能够到达答案的结点。 对活结点使用一个“有智能”的排序函数C()来选取下一个结点，往往可以加快获取答案的速度。 按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。常用方法是LC(Least Cost)方法。,分支限界法基础,10,画出下图的解题过程（按优先队列方式）,11,源最短路径问题,输入 有向带权图G=(V, E) 图中顶点s 输出 s到图中其它顶点的最短路径,12,源最短路径问题,解空间树,13,源最短路径问题,优先队列式分支限界法 优先级测度：当前路径长度 （最小堆）,

6、14,源最短路径问题,剪枝策略 节点b:50控制b:60 将b:60 及其子树剪去 当前扩展节点有儿子v: x 如果x=distv，不扩展v 如果xdistv，扩展v，将v的孩子加入堆中,15,0-1背包问题,输入： , , 和C 输出： (x1, x2, , xn)，xi0, 1满足 优化目标：,16,0-1背包问题,解空间树,w=16，15，15 v=45，25，25 背包容量30,17,0-1背包问题,FIFO队列式分支限界法,FIFO队列,A, B,D, E, F,J, K, L, M, N,节点C对应：x1=1, x2=1 节点K对应：x1=0, x2=1, x3=1,18,0-1背

7、包问题,对于树中的第i层节点V 已经完成了对物品1, i的取舍，剩余物品为i+1, ., n 设已选择的物品价值为p，背包剩余容量为C 限界函数bound(V) = p + q 其中q是针对输入i+1, ., n和C的一般背包问题的最优解 可以按价重比顺序依次向背包中装入物品得到q 以V为根的子树中节点的价值不会超过bound(V),物品按价重比排序为1, , n,19,0-1背包问题,优先队列式分支限界法 优先级测度：bound(V) 最大堆 直到某个叶节点x成为扩展节点结束 叶节点x的bound(x)等于拿走物品的总价值 堆中剩余节点及其子树的价值不会超过bound(x),20,0-1背包

8、问题,优先队列式分支限界法 优先级测度：bound(V) 最大堆,w=16，15，15 v=45，25，25 背包容量30,最优解：K (0, 1, 1) 总价值：50,最大堆,A, B,D, B,B, J,E, J, F,K, J, L, F,21,0-1背包问题,队列（堆）中的每个元素 存储已经获得的部分解 D入队列：存储x1=1, x2=0 K入队列：存储x1=0, x2=1, x3=1 存储已构造的解空间树 B入队列：存储B的父亲为，B是其右孩子 E入队列：存储E的父亲为B，E是其左孩子 K入队列：存储K的父亲为E，K是其左孩子 K对应的解：x3=1, x2=1, x1=0,22,0-

9、1背包问题,分支限界法优化 限界函数：bound(v) 当前的最优值：bestp 如果bound(v)bestp 剪去v及其子树,23,装载问题,输入 n个集装箱，其中集装箱i的重量为wi 载重量分别为C1和C2的轮船 输出 （是否有）合理的装载方案将所有集装箱装上船 等价于,s.t.,特殊的0-1背包问题：每种物品的价值等于重量,24,装载问题,解空间树,w=16，15，15 C1载重量30,25,装载问题,FIFO队列式分支限界法,w=16，15，15 C1载重量30,26,装载问题,解空间树的第i层节点v 已经完成了对集装箱1, i的取舍，剩余集装箱为i+1, ., n 已经装上第一艘船

10、的集装箱重量和为p 剩余集装箱的重量和为r 限界函数bound(v)=p+r 以v为根的子树中的解的总重量不会超过bound(v),27,装载问题,优先队列式分支限界法 优先级测度：bound(v) 最大堆 直到某个叶节点x成为扩展节点结束 叶节点x的bound(x)等于拿走物品的总重量 堆中剩余节点及其子树的总重量不会超过bound(x),28,装载问题,优先队列式分支限界法,w=16，15，15 C1载重量30,最大堆,A, B,D, B,B, J,E, J, F,K, J, F, L,最优解：K (0, 1, 1) 总重量：30,29,旅行售货员问题,输入 完全无向带权图G=(V, E)

11、 |V|=n, |E|=m 对于E中的某条边e，其长度为c(e) 输出 最短的哈密尔顿回路 经过每个节点一次且仅一次的回路,NP难问题,30,旅行售货员问题,实例FIFO队列式,A,B,1,C,2,F,3,L,4,G,4,M,3,D,H,2,N,4,I,4,O,2,E,J,2,P,3,K,3,Q,2,3,4,C,D,E,F,G,H,I,J,K,B,L,M,N,P,Q,59,66,25,26,31,旅行售货员问题,堆式分支限界法1 优先级测度：当前路径长度（最小堆） bestp：当前最优值 剪去当前代价大于等于bestp的节点及其子树,32,旅行售货员问题,实例优先队列式(1),A,B,1,C,

12、2,D,H,2,N,4,E,J,2,K,3,3,4,E,D,C,B,25,J,K,N,I,C,K,N,I,C,N,I,C,I,4,D,J,K,C,H,J,K,I,C,33,旅行售货员问题,对于树中的第 i 层节点W 路径上已选顶点为v1, v2, , vi 当前路径的长度为 P 剩余顶点为vi+1, , vn 连接 vj 的最短出边的长度为Minout(vj) bound(W)=P+ 以W为根的子树中的解的代价不少于bound(W),34,旅行售货员问题,堆式分支限界法2 优先级测度：bound(W) 最小堆 直到某个叶节点Y成为扩展节点 bound(Y)等于Y的路径长度 堆中其它节点的代价都

13、大于bound(Y) 优化 bestp：当前最优值 剪去当前代价大于等于bestp的节点及其子树,35,旅行售货员问题,实例优先队列式(2),A,B,1,C,2,D,H,2,N,4,I,4,E,J,2,P,3,K,3,3,4,C,D,E,C,D,J,K,B,C,K,C,J,K,H,I,C,J,K,I,36,批处理作业调度问题（回溯法）,输入 n个作业1, , n 两台机器（M1和M2） 作业 i 在M1和M2上的处理时间分别为 ai 和 bi 每个作业必须现由M1处理，再由M2处理 输出 作业调度方案使得总等待时间最小 作业 i在M1和M2上的完成时间分别为 Ai 和 Bi 总等待时间为,37

14、,批处理作业调度问题（回溯法）,可能的调度方案 123，132，213， 231，312，321 最佳方案是132（总等待时间：18）,M1,M2,Job 1,Job 1,B1=3,Job 3,Job 3,B3=7,Job 2,Job 2,B2=8,A1=2,A3=4,A2=7,38,批处理作业调度问题（回溯法）,计算调度J1, J2, , Jn的等待时间 计算BJi 计算AJi=AJi-1 + aJi 比较AJi和BJi1 BJi较大者 + bJi,39,批处理作业调度问题（回溯法）,解空间树 排列树,40,批处理作业调度问题（回溯法）,回溯法（搜索排列树）,初始时：xn=（1,2,3,n）

15、 void Backtrack(int t) if (tn) 输出x； else for(i=t; i=n; i+) Swap(xt, xi); if (Bound(t) /如果当前的部分解可行 且 可能产生最优解 Backtrack(t+1) ； Swap(xt, xi); ,时间复杂性：O(n!) 空间复杂性：O(n),41,批处理作业调度问题（回溯法）,剪枝 限界函数 Bound(t)：,42,批处理作业调度问题,对于树中第 i 层节点V V已经安排了作业J1, J2, , Ji 已安排的作业的等待时间为 计算BJi方法 计算AJi=AJi-1 + aJi 比较AJi和BJi1 BJi较大者 + bJi,43,批处理作业调度问题,对于树中第 i 层节点V 设以V为根的子树中某个叶节点W的调度为 J1, , Ji ，Ji+1 , , Jn 如果从Ji+1开始机器1没有空闲，则 Ji+1 , , Jn的总等待时间不少于,如果aJx在xi+1时按非递减序排列 S1取得极小值S1 Ji+1 , , Jn的总等待时间 S1,44,批处理作业调度问题,对于树中第 i 层节点V 设以V为根