第9章-分支限界法

第9章 分支限界法

BranchandBoundMethod算法设计与分析—本科生课程DesignandAnalysisofAlgorithm邱钊海南大学信息科学技术学院CollegeofInformationScienceandTechnology,HainanUniversityqiuzhao73@2023/2/12教学重点分支限界法的设计思想，各种经典问题的限界函数教学难点各种经典问题的限界函数以及限界算法教学内容及目标知识点教学要求了解理解掌握熟练掌握分支限界法的设计思想√分支限界法的时空性能√TSP问题√多段图的最短路径问题√0/1背包问题√任务分配问题√批处理作业调度问题√学习目标Chapter8BackTrackMethod2023/2/1BranchandBoundMethod3第9章分支限界法

9.1概

述

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

述

2023/2/1BranchandBoundMethod59.1概

述

9.1.1分支限界法的设计思想9.1.2分支限界法的时间性能2023/2/1BranchandBoundMethod6回溯法存在的问题虽用剪枝减少了搜索空间，但按深度优先策略机械地进行，搜索是盲目的。如0/1背包问题。首先将目标函数初始化为最大值，目标函数只有在有一个可行解（第一个叶子）后才有意义，此后的搜索相对来说才有方向，所以从搜索的整个过程来看还是盲目的。如TSP问题（图8.6）。分支限界法先确定一个合理的限界函数由限界函数确定目标函数的界[down,up]仍以穷举法的解空间树为基础，但以广度优先的原理搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值分支限界法的设计思想2023/2/1BranchandBoundMethod7如果某孩子结点的目标函数可能取值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表（表PT）依次从表PT中选取使目标函数的值取极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。目标函数的界[down,up]的确定对最大化问题Up由限界函数确定，down由某种启发方式得到,如贪心算法对最小化问题down由限界函数确定，up由某种启发方式得到,如贪心算法分支限界法的设计思想2023/2/1BranchandBoundMethod8例：0/1背包问题。假设有4个物品，其重量分别为(4,7,5,3)，价值分别为(40,42,25,12)，背包容量W=10。首先，将给定物品按单位重量价值从大到小排序，结果如下：物品重量(w)价值(v)价值/重量(v/w)144010274263525543124分支限界法的设计思想2023/2/1BranchandBoundMethod9确定上下界

down：应用贪心法求得近似解为(1,0,1,0)，获得的价值为65，这可以作为0/1背包问题的下界。up：考虑最好情况，背包中全部装入第1个物品且可以将背包装满，则可得到一个简单上界的计算方法：

up=W×(v1/w1)=10×10=100则目标函数的界：[65,100]限界函数为：分支限界法的设计思想2023/2/1BranchandBoundMethod10×w=0,v=0ub=100w=4,v=40ub=76w=0,v=0ub=60w=11无效解w=4,v=40ub=70w=9,v=65ub=69w=4,v=40ub=64w=12无效解w=9,v=65ub=6523456789×1××PT表图9.10/1背包问题分支限界法的设计思想2023/2/1BranchandBoundMethod11分支限界法的搜索过程如下：在根结点1

没有物品装入背包，w=0,v=0

限界函数值：ub=0+(10-0)=10×10=100在结点2

物品1装入背包，w=w1=4，v=40

目标函数值:ub=40+(10-4)×6=76

将结点2加入待处理结点表PT中在结点3

物品1不装入背包，w=0,v=0

目标函数值:10ub=0+(10-0)×6＝60<65，丢弃结点3在表PT中选取目标函数值取得极大的结点2优先进行搜索；

分支限界法的设计思想2023/2/1BranchandBoundMethod12在结点4

物品2装入背包，w=11>W，不满足约束条件，将结点4丢弃在结点5

物品2不装入背包，w=4,v=40与结点2相同目标函数值为:ub=40+(10-4)×5=70

将结点5加入表PT中在结点6

物品3装入背包，w=4+5=9，v=40+25=65

目标函数值为:ub=65+(10-9)×4=69

将结点6加入表PT中在表PT中选取目标函数值取得极大的结点5优先进行搜索分支限界法的设计思想2023/2/1BranchandBoundMethod13在结点7

物品3不装入背包，w=4,v=40,与结点5相同目标函数值为：ub=40+(10-4)×4＝64<65

丢弃结点7在结点8

物品4装入背包，w=12>W,不满足约束条件，将结点8丢弃；在结点9

物品4不装入背包，w=9,v=65,与结点6相同目标函数值为:ub=65+(W-w)*0=65

将结点9加入表PT中在表PT中选取目标函数值取得极大的结点6优先进行搜索分支限界法的设计思想2023/2/1BranchandBoundMethod14结点9是叶子结点同时结点9的目标函数值是表PT中的极大值，结点9对应的解即是问题的最优解，搜索结束在图9.1的0/1背包问题中，为了在搜索过程中构建搜索经过的树结构，设一个表PT，记录搜索过程，如图9.2。再设计了一表ST，从PT中取出最大值结点进行扩充时，将最大值结点存储到表ST中，表PT和表ST的数据结构为：

(物品i-1的选择结果，<物品i,

物品i

的选择结果>ub)

在搜索过程中表PT和表ST的状态如图9.2所示分支限界法的设计思想2023/2/1BranchandBoundMethod15(c)扩展结点5后(d)扩展结点6后，最优解为(1,0,1,0)65

图9.2方法②确定0/1背包问题最优解的各分量(a)扩展根结点后(b)扩展结点2后(0,<1,1>76)PTST(1,<2,0>70)PTST(0,<1,1>76)(0,<3,1>69)

PTST(0,<1,1>76)(1,<2,0>70)(1,<4,0>65)PTST(0,<1,1>76)(1,<2,0>70)(0,<3,1>69)9256分支限界法的设计思想2023/2/1BranchandBoundMethod16基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点（使目标函数取得极值的结点）成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。分支限界法的设计思想2023/2/1BranchandBoundMethod17分支限界法的一般过程

1．根据限界函数计算目标函数的[down，up]；

2．将待处理结点表PT初始化为空；3.对根结点的每个孩子结点x执行下列操作

3.1估算结点x的目标函数值value; 3.2若（value>=down）,则将结点x加入表PT中；4．循环直到某个叶子结点的目标函数值在表PT中最大4.1i=表PT中值最大的结点；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的结点删除；分支限界法的设计思想2023/2/1BranchandBoundMethod18用分支限界法求解问题的关键如何确定合适的限界函数限界函数用于估算结点的目标函数的可能取值。好的限界函数不仅计算简单，还要保证最优解在搜索空间中，更重要的是能尽早对超出目标函数界的结点进行剪枝，减少搜索空间。有时需要对具体的问题实例进行大量实验才能确定一个合理的限界函数。如何组织待处理结点表

为提高查找极值的效率，待处理结点表PT可采用堆或优先队列的形式存储。分支限界法的设计思想2023/2/1BranchandBoundMethod19用分支限界法求解问题的关键（续）如何确定最优解中的各个分量

分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单纯地沿着双亲结点一层一层向上回溯，因此当搜索到最优解（叶子结点）时，却无法求得该叶子结点对应的最优解中的各个分量（路径）。解决方法：对每个扩展结点保存根结点到该结点的路径；在搜索过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。分支限界法的设计思想2023/2/1BranchandBoundMethod20(c)扩展结点5后(d)扩展结点6后，最优解为(1,0,1,0)65

图9.2方法②确定0/1背包问题最优解的各分量(a)扩展根结点后(b)扩展结点2后(0,<1,1>76)PTST(1,<2,0>70)PTST(0,<1,1>76)(0,<3,1>69)

PTST(0,<1,1>76)(1,<2,0>70)(1,<4,0>65)PTST(0,<1,1>76)(1,<2,0>70)(0,<3,1>69)9256分支限界法的设计思想2023/2/1BranchandBoundMethod219.1概

述

9.1.1分支限界法的设计思想9.1.2分支限界法的时间性能2023/2/1BranchandBoundMethod22与回溯法相同点分支限界法和回溯法实际上都是基于蛮力法，遍历具有指数阶个结点的解空间树在最坏情况下，时间复杂性肯定为指数阶2n或nn与回溯法不同点分支限界法首先扩展解空间树中的上层结点，并用限界函数大范围剪枝根据限界函数不断调整搜索方向，选择最有可能取得最优解的子树优先进行搜索如果选择了结点的合理扩展顺序以及设计好的限界函数，分支界限法可以快速得到问题的解9.1.2分支限界法的时间性能

2023/2/1BranchandBoundMethod23分支限界法的代价首先，设计一个好的限界函数通常需要花费更多的时间计算相应的目标函数值，而且对于具体的问题实例，通常需要进行大量实验，才能确定一个好的限界函数；其次，分支限界法对解空间树中结点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个扩展结点保存该结点到根结点的路径，或者在搜索过程中构建搜索经过的树结构，这使得算法的设计较为复杂；再次，分支限界法为维护PT表需要较大的存储空间，在最坏情况下，分支限界法需要的空间复杂性是指数阶。9.1.2分支限界法的时间性能

2023/2/1BranchandBoundMethod24第9章分支限界法

9.1概

述

9.2图问题中的分支限界法9.3组合问题中的分支限界法9.2图问题中的分支限界法9.2.1TSP问题9.2.2多段图的最短路径问题25BranchandBoundMethod算法设计与分析2023/2/1BranchandBoundMethod269.2.1TSP问题TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。271563134253984C=∞3

158

3∞679

16∞42

574∞3892

3∞(a)一个无向图(b)无向图的代价矩阵图9.4无向图及其代价矩阵2023/2/1BranchandBoundMethod27确定上界ub采用贪心法求得近似解为:1→3→5→4→2→1

ub=1+2+3+7+3=16

这可以作为TSP问题的上界确定下界lb把矩阵中每一行最小的元素相加，可以得到一个简单的下界:

lb=1+3+1+3+2=10一个信息量更大的下界：把矩阵中每一行最小的两个元素相加再除以2，再对这个结果向上取整，就得到了一个合理的下界:

lb=((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14

则，目标函数的界:[lb,ub]=[14,16]注意：该解并不是一个合法的选择（即没构成哈密顿回路），仅给出了一个参考下界。9.2TSP问题2715631342539842023/2/1BranchandBoundMethod28

部分解的目标函数值的计算方法假设当前已确定的路径为U=(r1,r2,…,rk),则：

例如图10.4所示无向图，如果部分解包含顶点U=(1,4)，则该部分解的下界是:lb=(2*5+(1+3)+((3+6)+(1+2)+(2+3)))/2=16分支限界法求解TSP问题示例271563134253984C=∞31

58

3∞679

16∞42

5

74∞3892

3∞i=1,k2023/2/1BranchandBoundMethod29TSP问题的搜索过程考察根结点1

目标函数:lb=((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14

将根结点1加入PT表中考察孩子结点2:C1C2,路径长度为3

目标函数:lb=(2*3+(1+6)+(1+2)+(3+4)+(2+3))/2=14

将结点2加入待处理结点表PT中；在结点3：C1C3，路径长度为1

目标函数:lb=(2*1+(3+2)+(3+6)+(3+4)+(2+3))/2=14

将结点3加入表PT中在结点4：C1C4，路径长度为5

目标函数:lb=(2*5+(1+3)+(3+6)+(1+2)+(2+3))/2=16

将结点4加入表PT中∞3158

3∞679

16∞42

574∞3892

3∞2023/2/1BranchandBoundMethod30在结点5：C1C5，路径长度为8

目标函数：lb=(2*8+(1+2)+(3+6)+(1+2)+(3+4))/2=19

超出目标函数的界，将结点5丢弃；处理结点2的孩子结点。结点6,C1C2C3,路径长度为3+6

目标函数:lb=(2*9+(1+1)+(3+4)+(2+3))/2=16

将结点6加入表PT中在结点7，C1

C2C4，路径长度为3+7

目标函数lb=(2*10+(1+3)+(1+2)+(2+3))/2=16

将结点7加入表PT中分支限界法求解TSP问题示例在表PT中选取目标函数值极小的结点2优先进行搜索∞3

158

3∞6

79

1

6∞42

5

74∞38923

∞2023/2/1BranchandBoundMethod31在结点8，C1

C2C5，路径长度为3+9目标函数:lb=(2*12+(1+2)+(1+2)+(3+4))/2=19超出目标函数的界，将结点8丢弃处理结点3的孩子。结点9，C1

C3C2，路径长度为1+6

目标函数值:lb=(2*7+(3+3)+(3+4)+(2+3))/2=16

将结点9加入表PT中在结点10，C1

C3C4，路径长度为1+4

目标函数:lb=(2*5+(3+3)+(3+6)+(2+3))/2=15

将结点10加入表PT中分支限界法求解TSP问题示例在表PT中选取目标函数值极小的结点3优先进行搜索∞3

1583∞679

1

6∞4

2

5

74∞389

23

∞2023/2/1BranchandBoundMethod32在结点11，C1C3C5，路径长度为1+2

目标函数值:lb=(2*3+(3+3)+(3+6)+(3+4))/2=14

将结点11加入表PT中在表PT中选取目标函数值极小的结点11优先进行搜索处理结点11的孩子。结点12，C1C3C5C2，路径长度为1+2+9，目标函数值:lb=(2*12+(3+3)+(3+4))/2=19

超出目标函数的界，将结点12丢弃在结点13，C1C3

C5C4，路径长度为1+2+3

目标函数值：lb=(2*6+(3+4)+(3+6))/2=14,将结点13加入表PT中在表PT中选取目标函数值极小的结点13优先进行搜索∞3

1583∞679

1

6∞42

5

74∞389

2

3∞2023/2/1BranchandBoundMethod33在表PT中选取目标函数值极小的结点10优先进行搜索处理结点13的孩子。结点14，C1C3

C5C4C2，路径长度为1+2+3+7，目标函数值:lb=(2*13+(3+3))/2=16

由于结点14为叶子结点，得到一个可行解 其路径长度为16∞3

158

3∞67

9

1

6∞42

5

74∞389

2

3∞分支限界法求解TSP问题示例2023/2/1BranchandBoundMethod34分支限界法求解TSP问题示例在表PT中选取目标函数值极小的结点16优先进行搜索处理结点10的孩子。结点15，C1C3

C4C2，长度12。

目标函数:lb=(2*12+(3+3)+(2+3))/2=18

超出目标函数的界，将结点15丢弃结点16，C1C3

C4C5，长度8

目标函数:lb=(2*8+(3+2)+(3+6))/2=15

将结点16加入表PT中处理结点16的孩子。结点17,C1C3C4C5C2,长度17，目标函数:lb=(2*17+(3+3))/2=20,超目标函数的界，结点17丢弃表PT中目标函数值均为16，且已找到叶子结点14的长度是16，故这是最优解，搜索过程结束。

∞3

158

3∞679

1

6∞4

2

5

74∞38

9

2

3∞2023/2/1BranchandBoundMethod3541→2lb=142356781×startlb=141→3lb=141→4lb=161→5lb=192→3lb=162→4lb=162→5lb=193→2lb=163→4lb=153→5lb=14×910115→2lb=195→4lb=141213×4→2lb=16144→2lb=184→5lb=151516×5→2lb=2017×分支限界法求解TSP问题示例C2C1C3C5C4C3C5C4C2C4C5C4C2C2∞3

158

3∞679

1

6∞42

5

74∞3892

3∞2023/2/1BranchandBoundMethod36(g)扩展结点16后的状态，最优解为1→3→5→4→2→1图9.6TSP问题最优解的确定(1,2)14(1,3)14(1,4)16(a)扩展根结点后的状态(b)扩展结点2后的状态(c)扩展结点3后的状态(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)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后的状态2023/2/1BranchandBoundMethod37算法9.1——TSP问题输入：图G＝（V，E）输出：最短哈密尔顿回路

1．根据限界函数计算目标函数的下界down；采用贪心法得到上界up；

2．计算根结点的目标函数值并加入待处理结点表PT；

3．循环直到某个叶子结点的目标函数值在表PT中取得极小值

3.1i=表PT中具有最小值的结点；3.2对结点i的每个孩子结点x执行下列操作： 3.2.1估算结点x的目标函数值lb; 3.2.2若（lb<=up），则将结点x加入表PT中，否则丢弃4.将叶子结点对应的最优值输出，回溯求得最优解的各个分量。伪代码9.2TSP问题9.2图问题中的分支限界法9.2.1TSP问题9.2.2多段图的最短路径问题38BranchandBoundMethod算法设计与分析9.2.2多段图的最短路径问题

设图G=(V,E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集Vi（2≤k≤n,1≤i≤k），使得E中的任何一条边(u,v)，必有u∈Vi，v∈Vi+m（1≤i＜k,

1＜i+m≤k），则称图G为多段图，称s∈V1为源点，t∈Vk为终点。1203456789492387884756866537多段图的最短路径问题是求从源点到终点的最小代价路径。39BranchandBoundMethod算法设计与分析

对图9.7所示多段图应用贪心法求得近似解为0→2→5→8→9，其路径代价为2+7+6+3=18，这可以作为多段图最短路径问题的上界。把每一段最小的代价相加，可以得到一个非常简单的下界，其路径长度为2+4+5+3=14。于是，得到了目标函数的界[14,18]。由于多段图将顶点划分为k个互不相交的子集，所以，多段图划分为k段，一旦某条路径的一些段被确定后，就可以并入这些信息并计算部分解的目标函数值的下界。一般情况下，对于一个正在生成的路径，假设已经确定了i段（1≤i≤k），其路径为(r1,r2,…,ri,ri+1)，此时，该部分解的目标函数值的计算方法即限界函数如下：åå+=+>Î<=++=+kijpiEvrijjjjvrcrrclbpi21,11]}][[{min]][[1段的最短边第＋40BranchandBoundMethod算法设计与分析已确定的路径长度ri+1出发的最短边ri+2后面每段的最短边和

应用分支限界法求解图9.7所示多段图的最短路径问题，其搜索空间如图9.8所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：（1）在根结点1，计算目标函数的值为14，将根结点加入表PT；（2）处理根结点每个孩子结点。结点2，第1段选择边<0,1>，目标函数值为lb=4+8+5+3=20，超出目标函数的界，将结点2丢弃；在结点3，第1段选择边<0,2>，目标函数值为lb=2+7+5+3=17，将结点3加入表PT；在结点4，第1段选择边<0,3>，目标函数值为lb=3+4+5+3=15，将结点4加入表PT中；（3）在表PT中选取目标函数值极小的结点4优先进行搜索；41BranchandBoundMethod算法设计与分析1203456789492387884756866537（4）在结点5，第2段选择边<3,5>，目标函数值为lb=3+4+6+3=16，将结点5加入表PT中；在结点6，第2段选择边<3,6>，目标函数值为lb=3+7+5+3=18，将结点6加入表PT；（5）在表PT中选取目标函数值极小的结点5优先进行搜索；（6）处理结点5的每个孩子结点。结点7，已确定路径是0→3→5→7，可直接确定第4段的边<7,9>，目标函数值为lb=3+4+8+7=22，超界丢弃；在结点8，已确定路径是0→3→5→8，可直接确定第4段的边<8,9>，目标函数值为lb=3+4+6+3=16，为一个可行解；由于结点8是叶子结点，并且其目标函数值是PT中最小的，所以它是最优解，搜索结束。42BranchandBoundMethod算法设计与分析1203456789492387884756866537640→1lb=20231startlb=180→2lb=160→3lb=15×图9.8分支限界法求解多段图的最短路径问题示例(×表示该结点被丢弃，结点上方的数组表示搜索顺序)53→5lb=163→6lb=1887lb=22lb=16×5→85→743BranchandBoundMethod算法设计与分析2023/2/1BranchandBoundMethod44第9章分支限界法

9.1概

述

9.2图问题中的分支限界法9.3组合问题中的分支限界法2023/2/1BranchandBoundMethod459.3组合问题中的分支限界法

9.3.2任务分配问题

9.3.3批处理作业调度问题9.3.10/1背包问题2023/2/1BranchandBoundMethod46问题描述

任务分配问题要求把n项任务分配给n个人，每个人完成每项任务的成本不同，要求分配总成本最小的最优分配方案。如图9.10所示是一个任务分配的成本矩阵。

9.3.2任务分配问题

C＝9278643758187694任务1任务2任务3任务4人员a人员b人员c人员d图9.10任务分配问题的成本矩阵2023/2/1BranchandBoundMethod47如何求最优分配成本的上界Up和下界Down获得上界UP如考虑以矩阵的对角线作为一个可行解:任务1人员a、任务2给人员b任务3人员c、任务4人员d

成本：9+4+1+4=18或应用贪心法求得一个近似解：任务2人员a、任务3人员b

任务1人员c、任务4人员d

成本:2+3+5+4=1414是一个更好的上界9.3.2任务分配问题

C＝9278643758187694任务1任务2任务3任务4人员a人员b人员c人员d图9.10任务分配问题的成本矩阵2023/2/1BranchandBoundMethod48获得下界Down考虑人员a所有任务的最小代价是2人员b执行所有任务的最小代价是3人员c执行所有任务的最小代价是1人员d执行所有任务的最小代价是4

每行取最小元素，其成本下界：2+3+1+4=10

则上下界为：[10,14]

注意：这个解并不是一个合法的选择因为：3、1来自于矩阵同一列，仅给出一个参考下界9.3.2任务分配问题

2023/2/1BranchandBoundMethod49设当前已对人员1～i分配了任务，并且获得了成本v，则限界函数可以定义为：

（式9.4）搜索过程在根结点1

没有分配任务，限界函数函数值为:lb=2+3+1+4=10在结点2

将J1人员a，获得的成本为9

目标函数值为:lb=9+(3+1+4)=17

超出目标函数的界[10,14]，将结点2丢弃9.3.2任务分配问题

C＝9278643758187694人员a人员b人员c人员d2023/2/1BranchandBoundMethod50图9.11分支限界法求解任务分配问题示例(×表示该结点被丢弃，结点上方的数组表示搜索顺序)4→alb=16104×startlb=101→alb=172→alb=103→alb=151→blb=133→blb=104→blb=141→clb=144→clb=174→clb=173→clb=134→dlb=1323567891213111××××

C＝9278643758187694任务1任务2任务3任务4人员a人员b人员c人员d任务1任务4任务2任务1任务3任务4任务1任务49.3.2任务分配问题

2023/2/1BranchandBoundMethod51搜索过程在结点3

将J2人员a，获得的成本为2

目标函数值:lb=2+(3+1+4)=10

将结点3-PT表中在结点4

将J3人员a，获得的成本为7

目标函数值:lb=7+(3+1+4)=15

超出目标函数的界[10,14]，将结点4丢弃9.3.2任务分配问题

C＝9278643758187694任务1任务2任务3任务4人员a人员b人员c人员d2023/2/1BranchandBoundMethod52在结点5

将J4人员a，获得的成本为8

目标函数值:lb=8+(3+1+4)=16

超出目标函数的界[10,14]，将结点5丢弃在结点6

将J2人员a,J1人员b，获得的成本为2+6=8

目标函数值:lb=8+(1+4)＝13

将结点6加入表PT中在表PT中选取目标函数值极小的结点3优先进行搜索9.3.2任务分配问题

9278643758187694任务1任务2任务3任务4人员a人员b人员c人员d2023/2/1BranchandBoundMethod53在结点7

将J2人员a，J3人员b，获得的成本为2+3=5

目标函数值:lb=5+(1+4)＝10

将结点7加入表PT中在结点8

将J2人员a，J4人员b，获得的成本为2+7=9

目标函数值:lb=9+(1+4)＝14

将结点8加入表PT中；在表PT中选取目标函数值极小的结点7优先进行搜索9.3.2任务分配问题

9278643

758187694任务1任务2任务3任务4人员a人员b人员c人员d2023/2/1BranchandBoundMethod54在结点9

将J2人员a，J3人员b

，J1人员c，获得的成本为5+5=10

目标函数值:lb=10+4=14

将结点9加入表PT中在结点10

将J2人员a，J3人员b

，J4人员c，获得的成本为5+8=13

目标函数值:lb=13+4=17

超出目标函数的界[10,14]，将结点10丢弃在表PT中选取目标函数值极小的结点6优先进行搜索9.3.2任务分配问题

2023/2/1BranchandBoundMethod55在结点11

将J2人员a,J1人员b，

J3人员c，获得的成本为8+1=9

目标函数值:lb=9+4=13

将结点11加入表PT中在结点12

将J2人员a,J1人员b，J4人员c，获得的成本为8+8=16

目标函数值:lb=16+4=20

超出目标函数的界[10,14]，将结点12丢弃；在表PT中选取目标函数值极小的结点11优先进行搜索9.3.2任务分配问题

9278643

758187694任务1任务2任务3任务42023/2/1BranchandBoundMethod56在结点13

将J2人员a,J1人员b，J3人员c

，J4人员d

获得的成本为9+4=13

目标函数值为:lb=13

由于结点13是叶子结点，同时结点13的目标函数值是表PT中的极小值，所以，结点13对应的解即是问题的最优解搜索结束。构建搜索经过的树结构取出表PT中最小值结点进行扩充时，并将最小值结点存储到ST中，表PT和表ST的数据结构为：

(人员i-1分配的任务,<任务k,人员i>lb)9.3.2任务分配问题

2023/2/1BranchandBoundMethod57

(人员i-1分配的任务,<任务k,人员i>lb)(e)扩展结点11后的状态，最优解为2→a，1→b，3→c，4→d(0,<2,a>10)(2,<1,b>13)(2,<3,b>10)(2,<4,b>14)(0,<2,a>10)(2,<1,b>13)(2,<4,b>14)(3,<1,c>14)(0,<2,a>10)(2,<3,b>10)(2,<4,b>14)(3,<1,c>14)(1,<3,c>13)(0,<2,a>10)(2,<3,b>10)(2,<1,b>13)(0,<2,a>10)(2,<3,b>10)(2,<1,b>13)(1,<3,c>13)(3,<4,d>13)(a)扩展根结点后的状态(b)扩展结点3后的状态PTSTPTST

PTST

(c)扩展结点7后的状态(d)扩展结点6后的状态(2,<4,b>14)(3,<1,c>14)(3,<4,d>13)PTSTPTST

9.3.2任务分配问题

2023/2/1BranchandBoundMethod589.3组合问题中的分支限界法

9.3.2任务分配问题

9.3.3批处理作业调度问题9.3.10/1背包问题2023/2/1BranchandBoundMethod59问题描述n个作业的集合J={J1,J2,…,Jn}，每个作业都有3项任务分别在3台机器上完成Ji

需要机器j的处理时间为tij（1≤i≤n,1≤j≤3）作业处理顺序:机器1处理机器2处理机器3处理批处理作业调度问题?要求确定这n个作业的最优处理顺序使得从第1个作业在机器1上处理开始，到最后一个作业在机器3上处理结束所需的时间最少。最优调度原则使机器1没有空闲时间，且机器2和3的空闲时间最小9.3.3批处理作业调度问题2023/2/1BranchandBoundMethod60T＝57910529957810J1J2J3J4机器1机器2机器3

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

J1

J3

J2，调度方案:J4:7J1:5J3:9J2:10机器1机器2机器3

图9.13批处理调度问题的调度方案空闲:7J4:8J1:7J3:9J2:5空闲:15J4:10J1:9J3:5J2:29.3.3批处理作业调度问题上界：412023/2/1BranchandBoundMethod62批处理作业调度问题的限界函数down理想情况机器1和机器2开始作业后无空闲，最后处理的恰好是在机器3上处理时间最短的作业。例如，以作业Ji开始的处理顺序，估算处理所需的最短时间是：tij:表示Ji需要机器j的处理时间(1≤i≤n,1≤j≤3)9.3.3批处理作业调度问题作业Ji在机器1上的处理时间作业1~作业n在机器2上的处理时间总和在机器3上处理时间最短的作业2023/2/1BranchandBoundMethod63目标函数下界计算lb若已安排了k-1个作业集合，即：M{1,2,…,

k-1}，|M|=k-1sum1[k-1]：机器1完成k-1个作业的处理时间sum2[k-1]：机器2完成k-1个作业的处理时间现要处理作业k，此时，该部分解的目标函数值的下界lb计算方法如下：（1）sum1[k]=sum1[k-1]+tk1（2）（3）sum2[k]=max{sum1[k],sum2[k-1]}+

tk2

9.3.3批处理作业调度问题2023/2/1BranchandBoundMethod64分支限界法搜索过程在根结点将sum1[0]和sum2[0]分别初始化为0

估算目标函数上界为41，加入表PT在结点2

以作业J1开始处理，则sum1[1]=5

目标函数值:lb=5+(7+5+9+8)+2=36,

sum2[1]=5+7=12

将结点2加入待处理结点表PT中在结点3

以作业J2开始处理，则sum1[1]=10

目标函数值:lb=10+(7+5+9+8)+5=44,

超过上界41，结点3舍弃。T＝579105