算法设计及分析 王红梅 第二版 第9章 分支限界法

1、教学重点教学重点分支限界法的设计思想，各种经典问题的限界函数分支限界法的设计思想，各种经典问题的限界函数教学难点教学难点各种经典问题的限界函数以及限界算法各种经典问题的限界函数以及限界算法教学内容及目教学内容及目标标知识点知识点教学要求教学要求了解了解理解理解掌握掌握熟练掌握熟练掌握分支限界法的设计思想分支限界法的设计思想分支限界法的时空性能分支限界法的时空性能TSP问题问题多段图的最短路径问题多段图的最短路径问题0/1背包问题背包问题任务分配问题任务分配问题批处理作业调度问题批处理作业调度问题学习目标第第9章章 分支限界法分支限界法 9.1 概概 述述 9.2 图图问题中的分支限界法问题中的

2、分支限界法9.3 组合问题中的分支限界法组合问题中的分支限界法回溯法回溯法：按深度优先策略遍历问题的解空间：按深度优先策略遍历问题的解空间树，应用约束条件、目标函数等剪枝函数实树，应用约束条件、目标函数等剪枝函数实行剪枝行剪枝分支限界法分支限界法：按广度优先策略遍历问题的解：按广度优先策略遍历问题的解空间树，在遍历过程中，对已经处理的每一空间树，在遍历过程中，对已经处理的每一个结点根据限界函数估算目标函数的可能取个结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值的结点优值，从中选取使目标函数取得极值的结点优先进行广度优先搜索，从而不断调整搜索方先进行广度优先搜索，从而不断调整

3、搜索方向，尽快找到问题的解。向，尽快找到问题的解。 9.1 概概 述述 9.1 概概 述述 9.1.1 分支限界法的设计思想分支限界法的设计思想9.1.2 分支限界法的时间性能分支限界法的时间性能分支限界法的设计思想分支限界法的设计思想分支限界法的设计思想分支限界法的设计思想物品物品重量重量(w)价值价值(v)价值价值/重量重量(v/w)144010274263525543124分支限界法的设计思想分支限界法的设计思想)()(11iiwvwWvub分支限界法的设计思想分支限界法的设计思想w=0, v=0ub=100w=4, v=40ub=76w=0, v=0ub=60w=11无效解无效解w=4

4、, v=40ub=70w=9, v=65ub=69w=4, v=40ub=64w=12无效解无效解w=9, v=65ub=65234567891PT表图9.1 0/1背包问题分支限界法的设计思想分支限界法的设计思想n在表在表PT中选取目标函数值取得中选取目标函数值取得极大的结点极大的结点2 优先进行搜索；优先进行搜索； 分支限界法的设计思想分支限界法的设计思想在表在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点5 优先进行搜索优先进行搜索分支限界法的设计思想分支限界法的设计思想在表在表PT 中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点6 优先进行搜索优先进行

5、搜索分支限界法的设计思想分支限界法的设计思想分支限界法的设计思想分支限界法的设计思想(c) 扩展结点扩展结点5后后 (d) 扩展结点扩展结点6 后，最优解为后，最优解为(1,0,1,0)65 图图9.2 方法确定方法确定0/1背包问题最优解的各分量背包问题最优解的各分量(a) 扩展根结点后扩展根结点后 (b) 扩展结点扩展结点2后后(0,76) (0,60)PTST(0,60) (1,70)PTST(0,76)(0,60) (0,69) (0,64)PTST(0,76) (1,70)(0,60) (0,64) (1,65)PTST(0,76) (1,70) (0,69)3792567分支限界法

6、的设计思想分支限界法的设计思想分支限界法的设计思想分支限界法的设计思想分支限界法的一般过程分支限界法的一般过程 1根据限界函数计算目标函数的根据限界函数计算目标函数的 down，up； 2将待处理结点表将待处理结点表PT 初始化为空；初始化为空； 3. 对根结点的每个孩子结点对根结点的每个孩子结点x执行下列操作执行下列操作 3.1 估算结点估算结点x的目标函数值的目标函数值value; 3.2 若（若（value=down）,则将结点则将结点x加入表加入表PT中；中； 4循环直到某个叶子结点的目标函数值在表循环直到某个叶子结点的目标函数值在表PT中最大中最大4.1 i=表表PT中值最大的结点；

7、中值最大的结点；4.2 对结点对结点i的每个孩子结点的每个孩子结点x执行下列操作执行下列操作4.2.1 估算结点估算结点x的目标函数值的目标函数值value；4.2.2 若若(value=down)，则将结点，则将结点x加入表加入表PT中；中；4.2.3 若（结点若（结点x是叶子结点且是叶子结点且value值在表值在表PT中最大），则将结点中最大），则将结点x对对应的解输出，算法结束；应的解输出，算法结束；4.2.4 若若(结点结点x是叶子结点但是叶子结点但value值在表值在表PT中不是最大中不是最大),则令则令down=value，并且将表，并且将表PT中所有小于中所有小于value的结点

8、删除；的结点删除；分支限界法的设计思想分支限界法的设计思想),()(211kxxxx),(),(211kxxxboundxbound),(),()(21211kxxxboundxxboundxbound分支限界法的设计思想分支限界法的设计思想),(21kxxxX),(),()(21211kxxxboundxxboundxbound分支限界法的设计思想分支限界法的设计思想分支限界法的设计思想分支限界法的设计思想分支限界法的设计思想分支限界法的设计思想分支限界法的设计思想分支限界法的设计思想(c) 扩展结点扩展结点5后后 (d) 扩展结点扩展结点6 后，最优解为后，最优解为(1,0,1,0)65

9、图图9.3 方法确定方法确定0/1背包问题最优解的各分量背包问题最优解的各分量(a) 扩展根结点后扩展根结点后 (b) 扩展结点扩展结点2后后(0,76) (0,60)PTST(0,60) (1,70)PTST(0,76)(0,60) (0,69) (0,64)PTST(0,76) (1,70)(0,60) (0,64) (1,65)PTST(0,76) (1,70) (0,69)3792567分支限界法的设计思想分支限界法的设计思想9.1 概概 述述 9.1.1 分支限界法的设计思想分支限界法的设计思想9.1.2 分支限界法的时间性能分支限界法的时间性能9.1.2 分支限界法的时间性能分支限

10、界法的时间性能 9.1.2 分支限界法的时间性能分支限界法的时间性能 第第9章章 分支限界法分支限界法 9.1 概概 述述 9.2 图问题中的分支限界法图问题中的分支限界法9.3 组合问题中的分支限界法组合问题中的分支限界法9.2 图问题中的分支限界法图问题中的分支限界法 9.2.1 TSP问题问题 9.2.2 多段图的最短路径问题多段图的最短路径问题9.2.1 TSP问题问题 TSP TSP问题是指旅行家要旅行问题是指旅行家要旅行n个城市，要求各个城个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。的路程最短。27156

11、3134253984C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (a) 一个无向图一个无向图 (b) 无向图的代价矩阵无向图的代价矩阵图图9.4 无向图及其代价矩阵无向图及其代价矩阵9.2 TSP问题问题271563134253984n 部分解的目标函数值的计算方法部分解的目标函数值的计算方法n假设当前已确定的路径为假设当前已确定的路径为U=(r1,r2,rk), 则：则： 例如图例如图10.4所示无向图，如果部分解包含顶点所示无向图，如果部分解包含顶点U=(1, 4)，则该，则该部分解的下界是部分解的下界是: lb=(2*5+(1+3)+(3+6)+

12、(1+2)+(2+3)/2=16UrUrjikiiiijrrrrclb2/ )2(111行最小的两个元素素行不在路径上的最小元分支限界法求解分支限界法求解TSP问题示例问题示例271563134253984C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 1111,(2 )/ 2jkiiijiikrUlbc rrrr行不在路径上的最小元素行最小的两个元素分支限界法求解分支限界法求解TSP问题示例问题示例在表在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点2优先进行搜索

13、优先进行搜索 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 分支限界法求解分支限界法求解TSP问题示例问题示例在表在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点3优先进行搜索优先进行搜索 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 在表在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点11优先进行搜索优先进行搜索n处理结点处理结点11的孩子。结点的孩子。结点12，C1C3C5C2 ，路径长度为1+2+9，目标函数值:lb=(2*12+(3+3)+(3+4)/2=19 超出目标函数的界，将结点12丢弃n

14、在结点在结点13， C1C3 C5C4 ，路径长度为1+2+3 目标函数值：lb=(2*6+(3+4)+(3+6)/2=14,将结点13加入表PT中在表在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点13优先进行搜索优先进行搜索 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 在表在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点10优先进行搜索优先进行搜索n处理结点处理结点13的孩子。结点的孩子。结点14， C1C3 C5C4C2 ，路径长度为1+2+3+7，目标函数值:lb=(2*13+(3+3)/2=16由于结点14为叶子结点，得到一

15、个可行解其路径长度为16 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 分支限界法求解分支限界法求解TSP问题示例问题示例分支限界法求解分支限界法求解TSP问题示例问题示例在表在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点16优先进行搜索优先进行搜索n处理结点处理结点10的孩子。结点的孩子。结点15，C1C3 C4C2，长，长度度12。 目标函数:lb=(2*12+(3+3)+(2+3)/2=18 超出目标函数的界，将结点15丢弃n结点结点16， C1C3 C4C5 ，长度，长度8 目标函数:lb=(2*8+(3+2)+(3+6)/2=15 将结

16、点16加入表PT中n处理结点处理结点16的孩子。结点的孩子。结点17,C1C3C4C5C2,长度长度17，目标函数:lb =(2*17+(3+3)/2=20,超目标函数的界，结点17丢弃表表PT中目标函数值均为中目标函数值均为16，且已找到叶子结点，且已找到叶子结点14的长度是的长度是16，故这是最优解，搜索过程结束。故这是最优解，搜索过程结束。 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 412lb=142356781startlb=1413lb=1414lb=1615lb=1923lb=1624lb=1625lb=1932lb=1634lb=1535lb

17、=1491152lb=1954lb=141142lb=16142lb=1845lb=151152lb=201分支限界法求解分支限界法求解TSP问题示例问题示例C2C1C3C5C4C3C5C4C2C4C5C4C2C2 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (g) 扩展结点扩展结点16后的状态，最优解为后的状态，最优解为135421图图9.6 TSP问题最优解的确定问题最优解的确定(1, 2)14 (1, 3)14 (1, 4)16(a) 扩展根结点后的状态扩展根结点后的状态 (b) 扩展结点扩展结点2后的状态后的状态(c) 扩展结点扩展结点3后的状态后的

18、状态(d) 扩展结点扩展结点11后的状态后的状态(e) 扩展结点扩展结点13后的状态后的状态(1, 3)14 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5)14(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5, 4)14 (1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 4)15 (1, 3, 5, 4, 2)

19、16(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 5, 4, 2)16 (1, 3, 4, 5)15(1, 4)16 (1, 2, 3)16 (1, 2, 4)16 (1, 3, 2)16 (1, 3, 5, 4, 2)16 (1, 3, 4, 5)15(f) 扩展结点扩展结点10后的状态后的状态算法算法9.1TSP问题问题输入：图输入：图G（V，E）输出：最短哈密尔顿回路输出：最短哈密尔顿回路 1根据限界函数计算目标函数的下界根据限界函数计算目标函数的下界down；采用贪心法得到上界；采用贪心法得到上界up； 2计算根结点的目标函数值

20、并加入待处理结点表计算根结点的目标函数值并加入待处理结点表PT； 3循环直到某个叶子结点的目标函数值在表循环直到某个叶子结点的目标函数值在表PT中取得极小值中取得极小值 3.1 i=表表PT中具有最小值的结点；中具有最小值的结点； 3.2 对结点对结点i的每个孩子结点的每个孩子结点x执行下列操作：执行下列操作：3.2.1 估算结点估算结点x的目标函数值的目标函数值lb;3.2.2 若（若（lb kijpiEvrijjjjvrcrrclbpi21,11min1段的最短边段的最短边第第 应用分支限界法求解图9.7所示多段图的最短路径问题，其搜索空间如图9.8所示，具体的搜索过程如下（加黑表示该路径

21、上已经确定的边）：（1）在根结点1，计算目标函数的值为14，将根结点加入表PT；（2）处理根结点每个孩子结点。结点2，第1段选择边，目标函数值为lb=4+8+5+3=20，超出目标函数的界，将结点2丢弃；在结点3，第1段选择边，目标函数值为lb=2+7+5+3=17，将结点3加入表PT；在结点4，第1段选择边，目标函数值为lb=3+4+5+3=15，将结点4加入表PT中；（3）在表PT中选取目标函数值极小的结点4优先进行搜索；1203456789492387884756866537（4）在结点5，第2段选择边，目标函数值为lb=3+4+6+3=16，将结点5加入表PT中；在结点6，第2段选择边

22、，目标函数值为lb=3+7+5+3=18，将结点6加入表PT；（5）在表PT中选取目标函数值极小的结点5优先进行搜索；（6）处理结点5的每个孩子结点。结点7，已确定路径是0357，可直接确定第4段的边，目标函数值为lb=3+4+8+7=22，超界丢弃；在结点8，已确定路径是0358，可直接确定第4段的边，目标函数值为lb=3+4+6+3=16，为一个可行解；由于结点8是叶子结点，并且其目标函数值是PT中最小的，所以它是最优解，搜索结束。12034567894923878847568665376401lb=20231startlb=1802lb=1603lb=15图图9.8 分支限界法求解多段图

23、的最短路径问题示例分支限界法求解多段图的最短路径问题示例(表示该结点被丢弃，结点上方的数组表示搜索顺序表示该结点被丢弃，结点上方的数组表示搜索顺序)535lb=1636lb=1887lb=22lb=165857第第9章章 分支限界法分支限界法 9.1 概概 述述 9.2 图问题中的分支限界法图问题中的分支限界法9.3 组合问题中的分支限界法组合问题中的分支限界法9.3 9.3 组合问题中的分支限界法组合问题中的分支限界法 9.3.2 9.3.2 任务分配问题任务分配问题 9.3.3 9.3.3 批处理作业调度问题批处理作业调度问题9.3.1 9.3.1 0/1背包问题背包问题9.3.2 任务分

24、配问题任务分配问题 C9 2 7 86 4 3 75 8 1 87 6 9 4任务任务1 任务任务2 任务任务3 任务任务4人员人员a人员人员b人员人员c人员人员d图图9.10 任务分配问题的成本矩阵任务分配问题的成本矩阵9.3.2 任务分配问题任务分配问题 C9 2 7 86 4 3 75 8 1 87 6 9 4任务任务1 任务任务2 任务任务3 任务任务4人员人员a人员人员b人员人员c人员人员d图图9.10 任务分配问题的成本矩阵任务分配问题的成本矩阵9.3.2 任务分配问题任务分配问题 nikkvlb1行的最小值第9.3.2 任务分配问题任务分配问题 C9 2 7 86 4 3 75

25、8 1 87 6 9 4人员人员a人员人员b人员人员c人员人员d图图9.11 分支限界法求解任务分配问题示例分支限界法求解任务分配问题示例(表示该结点被丢弃，结点上方的数组表示搜索顺序表示该结点被丢弃，结点上方的数组表示搜索顺序)4alb=16104startlb=101alb=172alb=103alb=151blb=133blb=104blb=141clb=144clb=174clb=173clb=134dlb=1323567891213111nikkvlb1行的最小值第 C9 2 7 86 4 3 75 8 1 87 6 9 4任务任务1 任务任务2 任务任务3 任务任务4人员人员a人员

26、人员b人员人员c人员人员d任务1任务4任务2任务1任务3任务4任务1任务49.3.2 任务分配问题任务分配问题 9.3.2 任务分配问题任务分配问题 C9 2 7 86 4 3 75 8 1 87 6 9 4任务任务1 任务任务2 任务任务3 任务任务4人员人员a人员人员b人员人员c人员人员dn在结点在结点6 将J2人员a,J1人员b，获得的成本为2+6=8 目标函数值:lb=8+(1+4)13 将结点6加入表PT中在表在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点3优先进行搜索优先进行搜索9.3.2 任务分配问题任务分配问题 9 2 7 86 4 3 75 8 1 87 6 9

27、 4任务任务1 任务任务2 任务任务3 任务任务4人员人员a人员人员b人员人员c人员人员d在表在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点7优先进行搜索优先进行搜索9.3.2 任务分配问题任务分配问题 9 2 7 86 4 3 75 8 1 87 6 9 4任务任务1 任务任务2 任务任务3 任务任务4人员人员a人员人员b人员人员c人员人员d在表在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点6 6优先进行搜索优先进行搜索9.3.2 任务分配问题任务分配问题 在表在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点1111优先进行搜索优先进行搜索9.3.2

28、任务分配问题任务分配问题 9 2 7 86 4 3 75 8 1 87 6 9 4任务任务1 任务任务2 任务任务3 任务任务49.3.2 任务分配问题任务分配问题 (人员人员i-1分配的任务分配的任务,lb)(e) 扩展结点扩展结点11后的状态，后的状态，最优解为最优解为2a，1b，3c，4d(0,10)(2,13) (2,10) (2,14)(0,10)(2,13) (2,14) (3,14)(0,10) (2,10) (2,14) (3,14) (1,13)(0,10) (2,10) (2,13) (0,10) (2,10) (2,13) (1,13)(a) 扩展根结点后的状态扩展根结点

29、后的状态 (b) 扩展结点扩展结点3后的状态后的状态 PTSTPTST PTST (c) 扩展结点扩展结点7后的状态后的状态 (d) 扩展结点扩展结点6后的状态后的状态(2,14) (3,14) (3,13)PTSTPTST 9.3.2 任务分配问题任务分配问题 算法算法9.3任务分配问题任务分配问题 1根据限界函数计算目标函数的根据限界函数计算目标函数的 down；采用贪心法得到；采用贪心法得到up； 2将待处理结点表将待处理结点表PT 初始化为空；初始化为空； 3for (i=1; i=1) 5.1 xk=1; 5.2 while (xk=n) 5.2.1 如果人员如果人员k 分配任务分配

30、任务xk 不发生冲突，则不发生冲突，则 5.2.1.1 根据式根据式9.4 计算目标函数值计算目标函数值 lb; 5.2.1.2 若若 lb=up，则将，则将 i,lb 存储在表存储在表PT 中；中； 5.2.2 xk=xk+1; 5.3 9.3.2 任务分配问题任务分配问题 算法算法9.3任务分配问题任务分配问题 5.3 如果如果k= =n且叶子结点的且叶子结点的lb值在表值在表PT中最小，中最小， 则输出该叶子结点对应的最优解；则输出该叶子结点对应的最优解； 5.4 否则，如果否则，如果k= =n且表且表PT中的叶子结点的中的叶子结点的lb值不是最小，则值不是最小，则 5.4.1 up=表

31、表PT中的叶子结点最小的中的叶子结点最小的lb值值; 5.4.2 将表将表PT中超出目标函数界的结点删除；中超出目标函数界的结点删除； 5.5 i=表表PT中中lb最小的结点的最小的结点的xk值；值； 5.6 k=表表PT中中lb最小的结点的最小的结点的k值；值；k+;9.3.2 任务分配问题任务分配问题 9.3 9.3 组合问题中的分支限界法组合问题中的分支限界法 9.3.2 9.3.2 任务分配问题任务分配问题 9.3.3 9.3.3 批处理作业调度问题批处理作业调度问题9.3.1 9.3.1 0/1背包问题背包问题9.3.3 批处理作业调度问题批处理作业调度问题T 5 7 910 5 2

32、 9 9 5 7 8 10J1J2J3J4机器1 机器2 机器3 设设 J=J1, J2, J3, J4 是是 4 个待处理的作业，每个作业的处个待处理的作业，每个作业的处理顺序相同理顺序相同: 机器机器1上处理上处理机器机器2上处理上处理机器机器3上处理上处理需要的处理时间如下矩阵所示需要的处理时间如下矩阵所示:9.3.3 批处理作业调度问题批处理作业调度问题上界？随机产生几个方案，从中选取最短完成时间为问题的上界？随机产生几个方案，从中选取最短完成时间为问题的上界。如若处理顺序为上界。如若处理顺序为: :J4 J1 J3 J2，调度方案，调度方案: :J4:7 J1:5 J3:9 J2:1

33、0机器机器1机器机器2机器机器3 图图9.13 批处理调度问题的调度方案批处理调度问题的调度方案空闲空闲:7 J4:8 J1:7 J3:9 J2:5空闲空闲:15 J4:10 J1:9 J3:5 J2:29.3.3 批处理作业调度问题批处理作业调度问题上界：41min3121kiknjjitttn批处理作业调度问题的限界函数批处理作业调度问题的限界函数ndown理想情况机器1和机器2开始作业后无空闲，最后处理的恰好是在机器3上处理时间最短的作业。例如，以作业 Ji 开始的处理顺序，估算处理所需的最短时间是最短时间是：tij: 表示表示 Ji 需要机器需要机器 j 的处理时间的处理时间(1in,

34、 1j3)9.3.3 批处理作业调度问题批处理作业调度问题作业Ji在机器1上的处理时间作业作业1作业作业n在机器2上的处理时间总和在机器3上处理时间最短的作业n目标函数下界计算目标函数下界计算lb若已安排了k-1个作业集合，即：M 1, 2, , k-1，|M|=k-1sum1k-1：机器机器1 1完成k-1个作业的处理时间sum2k-1：机器2完成k-1个作业的处理时间现要处理作业k，此时，该部分解的目标函数值的下界lb计算方法如下：（1）sum1k=sum1k-1+ tk1（2）（3）sum2k=maxsum1k, sum2k-1 + tk2 23,maxsum1k,sum2k-1min ijj k j Mi Mlbtt9.3.3 批