第6章_分支限界法

1、智能信息处理研究中心（RCIIP）1第第6 6章章 分支限界法分支限界法马志强马志强智能信息处理研究中心（RCIIP）2r分支限界法的算法框架m队列式（FIFO）分支限界法m优先队列式分支限界法堆式分支限界法r应用分支限界法解决单源最短路径问题装载问题；0-1背包问题；旅行售货员问题批处理作业调度问题智能信息处理研究中心（RCIIP）3分支限界法的背景分支限界法的背景理查德理查德.卡普卡普在在IBMIBM期间，深入研究了与实际应用有密切联系的一系列数学问题，如期间，深入研究了与实际应用有密切联系的一系列数学问题，如路径问题路径问题、背包问题背包问题、覆盖问题覆盖问题、匹配问题匹配问题、分区问题

2、分区问题、调度问题调度问题等，取得了许多出色的成等，取得了许多出色的成果。这些问题有一个共同的特点，即如果用图来表示问题，那么当图中增加一个果。这些问题有一个共同的特点，即如果用图来表示问题，那么当图中增加一个结点时，需要考察的可能的解的数目就急剧增加，形成所谓结点时，需要考察的可能的解的数目就急剧增加，形成所谓“组合爆炸组合爆炸” (combinatorial explosion)(combinatorial explosion)，使计算机的计算工作量大大增加，到一定程度就，使计算机的计算工作量大大增加，到一定程度就根本无法实现。根本无法实现。以路径问题中最著名的以路径问题中最著名的旅行商问

3、题为例旅行商问题为例，在卡普以前，最好的结果是，在卡普以前，最好的结果是RandRand公司的公司的丹齐格丹齐格(George Benard Dantzig)(George Benard Dantzig)、福格森、福格森(R(RFulkerson)Fulkerson)和约翰逊和约翰逊(S(SJohnson)Johnson)用手工和计算机相结合的办法，求出了包含用手工和计算机相结合的办法，求出了包含4949个城市个城市的旅行商的最佳路的旅行商的最佳路线。卡普和他的同事海尔特线。卡普和他的同事海尔特(M(MHeld)Held)经过反复研究，终于提出了一种称为经过反复研究，终于提出了一种称为“分支分

4、支限界法限界法”(branch(branchandandbound method)bound method)的新方法，用这种新方法实现的算法使的新方法，用这种新方法实现的算法使旅行推销员能周游的城市数达到旅行推销员能周游的城市数达到6565个个，从而打破了由，从而打破了由RandRand公司保持的记录。公司保持的记录。 1955 1955年年文学学士学位文学学士学位 19561956年年理科硕士学位理科硕士学位 19591959年年应用数学博士学位应用数学博士学位( (哈佛大学哈佛大学) ) Yorktown Heights Yorktown Heights的的IBMIBM沃森研究中心沃森研究

5、中心 1985年获得年获得ACM的图灵奖的图灵奖智能信息处理研究中心（RCIIP）4分支限界法基础分支限界法基础r8-Puzzle问题m输入: 具有8个编号小方块的魔方 m输出: 移动序列, 经过这些移动, 魔方达目标状态1284567321 8 45673智能信息处理研究中心（RCIIP）5分支限界法基础分支限界法基础r队列式（FIFO）分支限界法m广度优先搜索解空间树218 45673218 45673218 4567321845673218 45673218 4567321845673ABCDEFGA BCDEFG智能信息处理研究中心（RCIIP）6分支限界法基础分支限界法基础r优先队列

6、式分支限界法堆式分支限界m为解空间树中的每个节点指定一个优先级测度函数m每次扩展树中优先级最高的节点m用最大（最小）堆来保存待搜索节点r8-Puzzle问题m测度函数 f (v) =节点v中处于错误位置的方块数m每次扩展 f (v) 值最小的节点智能信息处理研究中心（RCIIP）7218456732184567321 8 4567321 8 45673218 4567321845673218 45673218456732184567321 8 45673B(3)C(3)D(4)E(4)F(2)G(4)H(1)I(0)J(2)AAB CDEF GH最小堆最小堆智能信息处理研究中心（RCIIP）8

7、分支限界法基础分支限界法基础r思想m广度优先广度优先或者优先级优先优先级优先搜索解空间树r实现m每个节点只有一次机会成为扩展节点m一旦节点v成为扩展节点 将 v 的所有孩子加入到队列或者堆中 接着选取队列顶队列顶或堆顶堆顶节点作为下一个扩展节点r效率m耗时比回溯法少m需要空间比回溯法多智能信息处理研究中心（RCIIP）9 常见的两种分支限界法常见的两种分支限界法（1 1）队列式分支限界法）队列式分支限界法 按照队列先进先出（按照队列先进先出（FIFOFIFO）或者后进先出（）或者后进先出（LIFOLIFO）原则选取下一个结点为扩展结点。）原则选取下一个结点为扩展结点。 （2 2）优先队列式分支

8、限界法）优先队列式分支限界法 队列式分支限界法队列式分支限界法对结点的选择规则相当死板，具对结点的选择规则相当死板，具有一定的有一定的 “ “盲目盲目”性。这种选择规则不利于快速检索到性。这种选择规则不利于快速检索到一个能够到达答案的结点。一个能够到达答案的结点。 对活结点使用一个对活结点使用一个“有智能有智能”的的排序函数排序函数C()C()来选取下来选取下一个结点，往往可以加快获取答案的速度。一个结点，往往可以加快获取答案的速度。 按照优先队列中规定的优先级选取优先级最高的结点按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。常用方法是成为当前扩展结点。常用方法是LC(Lea

9、st Cost)LC(Least Cost)方法方法。分支限界法基础分支限界法基础智能信息处理研究中心（RCIIP）10r画出下图的解题过程（按优先队列方式）28316475初始状态12384765目标状态智能信息处理研究中心（RCIIP）11源最短路径问题源最短路径问题r输入m有向带权图G=(V, E)m图中顶点sr输出ms到图中其它顶点的最短路径智能信息处理研究中心（RCIIP）12源最短路径问题源最短路径问题r解空间树智能信息处理研究中心（RCIIP）13源最短路径问题源最短路径问题r优先队列式分支限界法m优先级测度：当前路径长度 （最小堆）vprevdistva-INFb-INFc-I

10、NFd-INFas10ds100cs30ba60bc50dc90db60智能信息处理研究中心（RCIIP）14源最短路径问题源最短路径问题r剪枝策略m节点b:50控制b:60m将b:60 及其子树剪去m当前扩展节点有儿子v: x 如果x=distv，不扩展v 如果xdistv，扩展v，将v的孩子加入堆中智能信息处理研究中心（RCIIP）150-1背包问题背包问题r输入：m, , 和Cr输出：m (x1, x2, , xn)，xi0, 1满足r优化目标：niiixv1max智能信息处理研究中心（RCIIP）160-1背包问题背包问题r解空间树w=16，15，15v=45，25，25背包容量30智

11、能信息处理研究中心（RCIIP）170-1背包问题背包问题rFIFO队列式分支限界法FIFO队列A, BD, E, FJ, K, L, M, N节点C对应：x1=1, x2=1节点K对应：x1=0, x2=1, x3=1智能信息处理研究中心（RCIIP）180-1背包问题背包问题r对于树中的第i层节点Vm已经完成了对物品1, i的取舍，剩余物品为i+1, ., nm设已选择的物品价值为p，背包剩余容量为Cr限界函数bound(V) = p + qm其中q是针对输入i+1, ., n和C的一般背包问题的最优解m可以按价重比顺序依次向背包中装入物品得到qr以以V为根的子树中节点的价值不会超过为根的

12、子树中节点的价值不会超过bound(V)物品按价重比排序为1, , n智能信息处理研究中心（RCIIP）190-1背包问题背包问题r优先队列式分支限界法m优先级测度：bound(V) 最大堆m直到某个叶节点x成为扩展节点结束 叶节点x的bound(x)等于拿走物品的总价值 堆中剩余节点及其子树的价值不会超过bound(x)智能信息处理研究中心（RCIIP）200-1背包问题背包问题r优先队列式分支限界法m优先级测度：bound(V) 最大堆w=16，15，15v=45，25，25背包容量30最优解：K (0, 1, 1)总价值：50最大堆A, BD, BB, JE, J, FK, J, L,

13、F智能信息处理研究中心（RCIIP）210-1背包问题背包问题r队列（堆）中的每个元素m存储已经获得的部分解 D入队列：存储x1=1, x2=0 K入队列：存储x1=0, x2=1, x3=1m存储已构造的解空间树 B入队列：存储B的父亲为，B是其右孩子 E入队列：存储E的父亲为B，E是其左孩子 K入队列：存储K的父亲为E，K是其左孩子 K对应的解：x3=1, x2=1, x1=0智能信息处理研究中心（RCIIP）220-1背包问题背包问题r分支限界法优化m限界函数：bound(v)m当前的最优值：bestpm如果bound(v)bestp 剪去v及其子树智能信息处理研究中心（RCIIP）23

14、装载问题装载问题r输入mn个集装箱，其中集装箱i的重量为wim载重量分别为C1和C2的轮船r输出m（是否有）合理的装载方案将所有集装箱装上船r等价于211CCwniiniiixw1maxnixCxwiniii1,1 , 011s.t.特殊的0-1背包问题：每种物品的价值等于重量智能信息处理研究中心（RCIIP）24装载问题装载问题r解空间树w=16，15，15C1载重量30智能信息处理研究中心（RCIIP）25装载问题装载问题rFIFO队列式分支限界法w=16，15，15C1载重量30智能信息处理研究中心（RCIIP）26装载问题装载问题r解空间树的第i层节点vm已经完成了对集装箱1, i的取

15、舍，剩余集装箱为i+1, ., nm已经装上第一艘船的集装箱重量和为pm剩余集装箱的重量和为rm限界函数bound(v)=p+rr以v为根的子树中的解的总重量不会超过bound(v)智能信息处理研究中心（RCIIP）27装载问题装载问题r优先队列式分支限界法m优先级测度：bound(v) 最大堆m直到某个叶节点x成为扩展节点结束 叶节点x的bound(x)等于拿走物品的总重量 堆中剩余节点及其子树的总重量不会超过bound(x)智能信息处理研究中心（RCIIP）28装载问题装载问题r优先队列式分支限界法w=16，15，15C1载重量30最大堆最大堆A, BD, BB, JE, J, FK, J

16、, F, L最优解：K (0, 1, 1)总重量：30智能信息处理研究中心（RCIIP）29 旅行售货员问题旅行售货员问题r输入m完全无向带权图G=(V, E) |V|=n, |E|=m 对于E中的某条边e，其长度为c(e)r输出m最短的哈密尔顿回路哈密尔顿回路 经过每个节点一次且仅一次的回路NP难问题智能信息处理研究中心（RCIIP）30 旅行售货员问题旅行售货员问题 实例FIFO队列式AB1C2F3L4G4M3DH2N4I4O2EJ2P3K3Q2341342306105420C,D,EC,D,EF,G,H,I,J,KF,G,H,I,J,KB BL,M,N,P,QL,M,N,P,Q59596

17、66625252626智能信息处理研究中心（RCIIP）31 旅行售货员问题旅行售货员问题r堆式分支限界法1m优先级测度：当前路径长度（最小堆）mbestp：当前最优值m剪去当前代价大于等于bestp的节点及其子树智能信息处理研究中心（RCIIP）32 旅行售货员问题旅行售货员问题 实例优先队列式(1)AB1C2DH2N4EJ2K3341342306105420E E,D,C,D,CB B2525J J,K,K,N N,I,C,I,CK K, ,N N,I,C,I,CN N,I,C,I,CI4D D,J,K,J,K,CH H,J,K,I,C,J,K,I,C智能信息处理研究中心（RCIIP）33

18、 旅行售货员问题旅行售货员问题r对于树中的第 i 层节点Wm路径上已选顶点为v1, v2, , vi 当前路径的长度为 Pm剩余顶点为vi+1, , vn 连接 vj 的最短出边的长度为Minout(vj)rbound(W)=P+m以W为根的子树中的解的代价不少于bound(W)nijjv )(Minout智能信息处理研究中心（RCIIP）34 旅行售货员问题旅行售货员问题r堆式分支限界法2m优先级测度：bound(W) 最小堆m直到某个叶节点Y成为扩展节点 bound(Y)等于Y的路径长度 堆中其它节点的代价都大于bound(Y)r优化mbestp：当前最优值m剪去当前代价大于等于bestp

19、的节点及其子树智能信息处理研究中心（RCIIP）35 旅行售货员问题旅行售货员问题 实例优先队列式(2)AB1C2DH2N4I4EJ2P3K3341342306105420C,D,EC,D,EC,D,J,KC,D,J,KB BC,KC,KC,J,K,H,IC,J,K,H,IC,J,K,IC,J,K,I智能信息处理研究中心（RCIIP）36批处理作业调度问题（回溯法）r输入mn个作业1, , nm两台机器（M1和M2） 作业 i 在M1和M2上的处理时间分别为 ai 和 bi 每个作业必须现由M1处理，再由M2处理r输出m作业调度方案使得总等待时间总等待时间最小 作业 i在M1和M2上的完成时间

20、分别为 Ai 和 Bi 总等待时间为niiB1智能信息处理研究中心（RCIIP）37批处理作业调度问题（回溯法）r可能的调度方案m123，132，213， 231，312，321r最佳方案是132（总等待时间：18）作业作业aibiJob 121Job 231Job 323M1M2Job 1Job 1B1=3Job 3Job 3B3=7Job 2Job 2B2=8A1=2A3=4A2=7智能信息处理研究中心（RCIIP）38批处理作业调度问题（回溯法）r计算调度J1, J2, , Jn的等待时间m计算BJi 计算AJi=AJi-1 + aJi 比较AJi和BJi1 BJi较大者 + bJi智能

21、信息处理研究中心（RCIIP）39批处理作业调度问题（回溯法）r解空间树m排列树BC1F2L3G3M2DH1N3I3O1EJ1P2K2Q123191820211919智能信息处理研究中心（RCIIP）40批处理作业调度问题（回溯法）r回溯法（搜索排列树）初始时：xn=（1,2,3,n）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(

22、n)智能信息处理研究中心（RCIIP）41批处理作业调度问题（回溯法）r剪枝m限界函数 Bound(t)：bestTixBti1智能信息处理研究中心（RCIIP）42 批处理作业调度问题批处理作业调度问题r对于树中第 i 层节点VmV已经安排了作业J1, J2, , Ji 已安排的作业的等待时间为m计算BJi方法 计算AJi=AJi-1 + aJi 比较AJi和BJi1 BJi较大者 + bJiBJxx1i智能信息处理研究中心（RCIIP）43 批处理作业调度问题批处理作业调度问题r对于树中第 i 层节点Vm设以V为根的子树中某个叶节点W的调度为 J1, , Ji ，Ji+1 , , Jn 如果从Ji+1开始机器机器1没有空闲没有空闲，则 Ji+1 , , Jn的总等待时间总等待时间不少于nixxnixxiJbJaknJAinS111) 1()(111iiiiJbJaJAJB2212iiiiiJbJaJaJAJB.21nniiinJbJaJaJaJAJB