算法分析与设计课件：分支限界法

1、分支限界法分支限界法 2021-9-92 of 158例：例： 非对称的货郎担问题非对称的货郎担问题n规律：规律： 1）根结点是所有路线的下界）根结点是所有路线的下从目前所有叶子中下界最小的作为）从目前所有叶子中下界最小的作为分支点，按某种分支法产生若干个子分支点，按某种分支法产生若干个子集，再分别求各自的下界。集，再分别求各自的下界。2021-9-93 of 158 首先考虑根结点，即求所有路线的下界。对首先考虑根结点，即求所有路线的下界。对D的每行减去该行的最小元素或每列减去该列的的每行减去该行的最小元素或每列减去该列的最小元素，得到一个新的矩阵，使得每行最小元素

2、，得到一个新的矩阵，使得每行和和每每列至少有一个零元素。这叫做行规约和列规约。列至少有一个零元素。这叫做行规约和列规约。 14 30 5 610 11 4 346 5 615 10 13 213 3 4 11 D =2021-9-94 of 158规定：先做行规约，再做列规约5 14 30 5 610 11 4 346 5 615 10 13 213 3 4 11 D =1 9 25 0 17 8 1 00 2 1 213 8 11 010 0 1 8 先行规约先行规约 9 24 0 17 7 1 00 2 1 213 8 10 010 0 0 8 18 (=5+3+4+2+3+1)记作记作

3、D 再列规约再列规约183423首先计算第一个首先计算第一个0所对应的边所对应的边142021-9-95 of 158 h14=20 h25=19 h31=26 h45=26 h52=20 h53=25 9 24 17 7 1 00 2 1 213 8 10 010 0 0 8 181 1 v1 v2v3v4v5v1 v2 v3 v4 v5 8 23 07 7 0 00 2 0 213 8 10 010 0 0 7 20 (=18+1+1)182631 ?312021-9-96 of 158走31的计算方法 18v1 v2v3v4v5v1 v2 v3 v4 v5 9 24 0 17 7 1 0

4、0 2 1 213 8 10 010 0 0 8 189 0 1 7 1 08 10 00 0 8 v1 v2v4v5 v2 v3 v4 v518182631312021-9-97 of 158 h14=20 h25=19 h45=26 h52=26 h53=25 26459 0 1 7 1 08 10 00 0 8 v1 v2v4v5 v2 v3 v4 v5181818263131 ? 459 1 7 1 08 10 00 0 8 v1 v2v4v5 v2 v3 v4 v5189 0 7 1 0 0 v1 v2v5 v2 v3 v4 182021-9-98 of 158 2645181826

5、313119 452528 0 0 0 v2v5 v2 v3 25141453不能选不能选选择选择23，5231，45，14，23，5214 5 2 3 1总花费是：总花费是：252021-9-99 of 158请同学们改正请同学们改正书上书上P41题题v1 v2v3v4v5 v1 v2 v3 v4 v5 25 40 31 275 17 30 2519 15 6 19 50 24 622 8 7 10 2021-9-910 of 158书上P41题的答案1 626274414123237062353562664750212145456853141464652021-9-911 of 158方法

6、概述: 基本思想n在解空间树中在解空间树中, 以广度优先以广度优先BFS或最或最佳优先方式搜索最优解佳优先方式搜索最优解, 利用部分解利用部分解的最优信息的最优信息, 裁剪那些不能得到最优裁剪那些不能得到最优解的子树以提高搜索效率。解的子树以提高搜索效率。n搜索策略是：在扩展结点处，先生成搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展从当前的活结点表中选择下一个扩展结点。结点。2021-9-912 of 158方法概述: 基本思想n为了有效地选择下一扩展结点，以加为了有效地选择下一扩展结点，以加速搜索的进程，在每

7、一活结点处，计速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最的分支推进，以便尽快地找出一个最优解。优解。 2021-9-913 of 158方法概述: 与回溯法的区别n求解目标不同求解目标不同 ： 一般而言，回溯法的求解目标是找出解空间树一般而言，回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解中满足

8、约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解；目标则是找出满足约束条件的一个解； n搜索方法不同：搜索方法不同： 回溯算法使用深度优先方法搜索，而分枝限界回溯算法使用深度优先方法搜索，而分枝限界一般用宽度优先或最小耗费方法来搜索；一般用宽度优先或最小耗费方法来搜索； 2021-9-914 of 158方法概述: 与回溯法的区别n对扩展结点的扩展方式不同：对扩展结点的扩展方式不同： 分支限界法中，每一个活结点只有一次机会成分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点；性产生

9、其所有儿子结点；n存储空间的要求不同：存储空间的要求不同： 相对而言，分枝限界法的存储空间比回溯法大相对而言，分枝限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可得多，因此当内存容量有限时，回溯法成功的可能性更大；能性更大； 2021-9-915 of 158方法概述: 求解步骤定义解空间定义解空间(对解编码对解编码);确定解空间的树结构确定解空间的树结构;按按BFS等方式搜索等方式搜索: a.每个活结点仅有一次机会变成扩展结点；每个活结点仅有一次机会变成扩展结点； b.由扩展结点生成一步可达的新结点；由扩展结点生成一步可达的新结点； c.在新结点中在新结点中, 删除不可能

10、导出最优解的结点；删除不可能导出最优解的结点； /剪枝剪枝策略策略 d.将余下的新结点加入活动表将余下的新结点加入活动表(队列队列)中；中； e.从活动表中选择结点再扩展；从活动表中选择结点再扩展； /选择策略选择策略 f.直至活动表为空；直至活动表为空；2021-9-916 of 158方法概述: 两种常见的活结点扩充方式n先进先出队列（先进先出队列（F I F O） : 即从活结点表中即从活结点表中取出结点的顺序与加入结点的顺序相同，因取出结点的顺序与加入结点的顺序相同，因此活结点表的性质与队列相同；此活结点表的性质与队列相同； n优先队列优先队列（耗费用小根堆耗费用小根堆, ,受益用大根

11、堆受益用大根堆）: 每个结点都有一个对应的耗费或收益。每个结点都有一个对应的耗费或收益。 -如果查找一个具有最小耗费的解，则活结点如果查找一个具有最小耗费的解，则活结点表可用最小堆来建立，下一个扩展结点就是表可用最小堆来建立，下一个扩展结点就是具有最小耗费的活结点；具有最小耗费的活结点； -如果希望搜索一个具有最大收益的解，则可如果希望搜索一个具有最大收益的解，则可用最大堆来构造活结点表，下一个扩展结点用最大堆来构造活结点表，下一个扩展结点是具有最大收益的活结点。是具有最大收益的活结点。 2021-9-917 of 158堆（Heap)n堆堆n给定一个序列A=A1, A2, , An, 可以按

12、如下的方式构造一棵二叉树：nA1为根n对任何一个Ai, 它的左儿子是A2i, 右儿子是A2i+1n如果2i或2i+1超过n，则Ai没有相对应的那个儿子2021-9-918 of 158堆n堆堆2021-9-919 of 158堆n堆堆n所构造的树有如下性质n所有叶子在树的最底层或倒数第二层n如果最底层的节点不能完全填满，则总是在最左边n这样的树叫左-完全二叉树2021-9-920 of 158堆n堆堆n如果一个左-完全二叉树有下列性质：n任何一个非叶节点的值都大于等于（或小于等于）它的儿子的值n则这个树称为大（小）顶堆n一个堆对应的序列显然有如下性质：122122iAiAiAiAiAiAiAi

13、A或2021-9-921 of 158堆n堆堆2021-9-922 of 158堆n堆堆堆调整堆调整n假设已经有一个现成的（大顶）堆，调整的目的是把堆顶（根）的最大元素和序列的最后一个元素交换，然后把剩下是元素继续建成堆2021-9-923 of 158堆n堆堆调整 假设已经有一个堆，把堆顶元素和最后一个元素交换0) 剩下的序列中，堆的性质被破坏，调整堆就是把剩余的序列重新建成堆2021-9-924 of 158堆n堆堆调整1) 新的堆顶元素小于它的儿子， 所以不能构成堆，调整它的 位置把它和较大的儿子交换2) 调整后，右子树的根仍小于它 的儿子，所以把它和它的大儿 子交换2021-9-925

14、 of 158堆n堆堆调整3) 新堆构成2021-9-926 of 158堆n堆堆建立n堆建立是把一个无序的序列建成一个堆的过程n它是思想是从最底层的子树进行堆调整，先将子树建成堆， 然后继续调整，直到整个树构成堆2021-9-927 of 158堆n堆堆建立n堆建立是把一个无序的序列建成一个堆的过程n它是思想是从最底层的子树进行堆调整，先将子树建成堆， 然后继续调整，直到整个树构成堆2021-9-928 of 158堆n堆堆建立n堆建立是把一个无序的序列建成一个堆的过程n它是思想是从最底层的子树进行堆调整，先将子树建成堆， 然后继续调整，直到整个树构成堆2021-9-929 of 158堆n

15、堆堆建立n最后一个非叶节点是从n/2开始的，所以从这个节点开始 向前调整2021-9-930 of 158方法概述: 示例1n示例示例1（FIFO队列分枝限界法）队列分枝限界法）n问题：问题： 0-1背包问题背包问题:物品数物品数n=3, 重量重量w=(20,15,15), 价值价值v=(40,25,25), 背包容量背包容量c=30, 试装入最大价值之和的物品试装入最大价值之和的物品?n求解：求解： 解空间解空间:(0,0,0), (0,0,1), , (1,1,1) 解空间树解空间树:DBHAIEJKFCLMGNO111111100000002021-9-931 of 158方法概述: 示

16、例1BFS搜索（FIFO队列） 扩展结点 活结点 队列(可行结点) 可行解(叶结点) 解值 A B,C BC B D,E(D死结点) CE C F,G EFG E J,K(J死结点) FG K 40 F L,M G L,M 50,25 G N,O N,O 25,0 最优解为L, 即(0,1,1); 解值为50 DBHAIEJKFCLMGN O11111110000000w=(20,15,15), v=(40,25,25), c=302021-9-932 of 158方法概述: 示例2n示例示例2（优先队列分枝限界法）（优先队列分枝限界法）n问题：问题： 0-1背包问题背包问题:物品数物品数n=

17、3, 重量重量w=(20,15,15), 价值价值v=(40,25,25), 背包容量背包容量c=30, 试装入最大价值之和的物品试装入最大价值之和的物品?n求解：求解： 解空间解空间:(0,0,0), (0,0,1), , (1,1,1) 解空间树解空间树:DBHAIEJKFCLMGNO111111100000002021-9-933 of 158方法概述: 示例2nBFS搜索（优先队列：按价值率优先） 扩展结点 活结点 堆(可行结点) 可行解(叶结点) 解值 A B,C B D,E(D死结点) E J,K(J死结点) K 40 C F,G F L,M L 50(最优) G N,O BCEC

18、FGCGDBHAIEJKFCLMGN O11111110000000w=(20,15,15), v=(40,25,25), c=302021-9-934 of 158n例例2：用分支限界法求解分配问题：用分支限界法求解分配问题n分配问题：设有分配问题：设有n个人，每个人都可个人，每个人都可以完成以完成n种不同的任务，但所需时间种不同的任务，但所需时间不同。如果只需一人去完成每一项工不同。如果只需一人去完成每一项工作，则应如何分配作，则应如何分配n个人并使完成所个人并使完成所有有n项工作的总时间为最小。项工作的总时间为最小。2021-9-935 of 158n可行解：满足以下约束条件：分配一可行

19、解：满足以下约束条件：分配一人且仅一人去做每项工作的解称为分人且仅一人去做每项工作的解称为分配问题的可行解配问题的可行解n考虑考虑n=4的情况。的情况。 A ,B ,C , D四个人四个人分别完成分别完成1、2、3、4。这时问题有。这时问题有4！=24个可行解个可行解2021-9-936 of 158人人 工作工作 1 2 3 4 A 2 10 9 7 B 15 4 14 8 C 13 14 16 11 D 4 15 13 9n 2021-9-937 of 158人人 1 2 3 4 A 2 10 9 7 B 15 4 14 8 C 13 14 16 11 D 4 15 13 922A做1B做

20、1C做1D做1274133243624 342831A做2B做2C做2A做3C做32837 39B做2C做2D做2A 2021-9-938 of 158例例3：同顺序任务加工问题：设有：同顺序任务加工问题：设有4项项待加工的任务待加工的任务J1,J2,J3,J4,它们的工序它们的工序相同：每个任务必须先在机器相同：每个任务必须先在机器M1上上加工，然后在机器加工，然后在机器M2上加工，最后上加工，最后在在M3上加工。各加工时间已知。求上加工。各加工时间已知。求一最佳加工顺序使得尽早完工。一最佳加工顺序使得尽早完工。2021-9-939 of 158设设tij为任务为任务Ji在机器在机器Mj上的

21、加工时间，上的加工时间，且加工时间矩阵且加工时间矩阵T为：为：T =J1J2J3J45 7 9 10 5 2 9 9 57 8 10 M1 M2 M3 =(tij)4*32021-9-940 of 158如若加工顺序是：如若加工顺序是： J J2 2JJ3 3JJ1 1JJ4 4则从开始到结束所需的时间可计算如下图：则从开始到结束所需的时间可计算如下图：2021-9-941 of 158n理想的加工安排是：理想的加工安排是：M2无空闲，最后一无空闲，最后一个在个在M3上加工的任务时间最短。上加工的任务时间最短。n估计下界：比如从估计下界：比如从Ji开始的加工顺序，估开始的加工顺序，估计加工所需

22、的最短时间为：计加工所需的最短时间为： 4 ti1+ tj2+mintk3 j=1 k i 2021-9-942 of 158M1先加工先加工J1 4 ti1+ tj2+mintk3 j=1 k i 4 t11+ tj2+mintk3 j=1 k 1T =J1J2J3J45 7 9 10 5 2 9 9 57 8 10 M1 M2 M3 =5+(7+5+9+8) +2=362021-9-943 of 158M1先加工先加工J2 4 ti1+ tj2+mintk3 j=1 k i 4 t21+ tj2+mintk3 j=1 k 2T =J1J2J3J45 7 9 10 5 2 9 9 57 8

23、10 M1 M2 M3 =10+(7+5+9+8) +5=442021-9-944 of 158M1先加工先加工J4 4 ti1+ tj2+mintk3 j=1 k i 4 t41+ tj2+mintk3 j=1 k 4T =J1J2J3J45 7 9 10 5 2 9 9 57 8 10 M1 M2 M3 =7+(7+5+9+8) +2=382021-9-945 of 1582021-9-946 of 158一般从一般从Ji开始，继以开始，继以Jj的的任务安排，理想时间为：任务安排，理想时间为：ti1+ tj1 +tk2+minth3 k i h i,jJ1 J2 T =J1J2J3J45

24、7 9 10 5 2 9 9 57 8 10 M1 M2 M3 5+ 10+(5+9+8) +5=422021-9-947 of 158ti1+ tj1 +tk2+minth3 k i h i,jJ1 J3 T =J1J2J3J45 7 9 10 5 2 9 9 57 8 10 M1 M2 M3 5+ 9+(5+9+8) +2=38J1 J4 : 36 J1 J2 : 422021-9-948 of 158JiJj 的下界：的下界：ti1+ tj1 +tk1+tp2+tq3 p i,j J1 J4 J2 T =J1J2J3J45 7 9 10 5 2 9 9 57 8 10 M1 M2 M3 5+ 7+ 10+(5+9) +5=41J1 J4 J3 : 37 2021-9-949 of 1582021-9-950 of 1582021-9-951 of 158n例例4：用分支限界法求解：用分支限界法求解0/1背包问题背包问题 n=4, M=15 , (p1, p2, p3,p4)=(10,10,15,18) (w1 , w2 , w3,w4)=(2,4,6,9)2021-9-952 of 1586