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

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

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

3、搜索方向，尽快找到问题的解。向，尽快找到问题的解。 9.1 概概 述述 9.1 概概 述述 9.1.1 分支限界法的设计思想分支限界法的设计思想9.1.2 分支限界法的时间性能分支限界法的时间性能n回溯法存在的问题回溯法存在的问题n虽用虽用剪枝剪枝减少了搜索空间，但减少了搜索空间，但按深度优先策略机械地进按深度优先策略机械地进行行，搜索是盲目的，搜索是盲目的。如。如0/1背包问题。背包问题。n首先将目标函数初始化为最大值，目标函数只有在首先将目标函数初始化为最大值，目标函数只有在有一有一个可行解（第一个叶子）后才有意义个可行解（第一个叶子）后才有意义，此后的搜索相对，此后的搜索相对来说才有方向

4、，所以从搜索的整个过程来看还是盲目的。来说才有方向，所以从搜索的整个过程来看还是盲目的。如如TSP问题（图问题（图8.6）。）。n分支限界法分支限界法n先确定一个合理的先确定一个合理的限界函数限界函数n由限界函数确定目标函数的界由限界函数确定目标函数的界down, upn仍以仍以穷举法的解空间树穷举法的解空间树为基础，但以为基础，但以广度优先的原理广度优先的原理搜搜索该结点的所有孩子结点，分别估算这些索该结点的所有孩子结点，分别估算这些孩子结点的目孩子结点的目标函数的可能取值标函数的可能取值分支限界法的设计思想分支限界法的设计思想n如果某孩子结点的目标函数如果某孩子结点的目标函数可能取值超出目

5、标函数的界，则可能取值超出目标函数的界，则将其丢弃，将其丢弃，因为从这个结点生成的解不会比目前已经得到的因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表（表解更好；否则，将其加入待处理结点表（表PT）n依次从表依次从表PT中选取使目标函数的值取极值的结点成为当前扩中选取使目标函数的值取极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。展结点，重复上述过程，直到找到最优解。n目标函数的界目标函数的界down, up的确定的确定n对最大化问题对最大化问题UpUp由限界函数确定，由限界函数确定，downdown由某种启发方式得到由某种启发方式得到, ,如贪心算法如

6、贪心算法n对最小化问题对最小化问题downdown由限界函数确定，由限界函数确定，upup由某种启发方式得到由某种启发方式得到, ,如贪心算法如贪心算法分支限界法的设计思想分支限界法的设计思想n例：例：0/1背包问题。假设有背包问题。假设有4个物品，其重量分别个物品，其重量分别为为(4, 7, 5, 3)，价值分别为，价值分别为(40, 42, 25, 12)，背包容，背包容量量W=10。首先，将给定物品按单位重量价值从大。首先，将给定物品按单位重量价值从大到小排序，结果如下：到小排序，结果如下：物品物品重量重量(w)价值价值(v)价值价值/重量重量(v/w)14401027426352554

7、3124分支限界法的设计思想分支限界法的设计思想n确定上下界确定上下界 ndowndown：应用贪心法求得近似解为应用贪心法求得近似解为(1, 0, 0, 0)，获得的价值，获得的价值为为40，这可以作为，这可以作为0/1背包问题的背包问题的下界下界。nupup：考虑最好情况，背包中全部装入第考虑最好情况，背包中全部装入第1个物品且可以个物品且可以将背包装满，则可得到一个将背包装满，则可得到一个简单上界简单上界的计算方法：的计算方法： up=W(v1/w1)=1010=100n则目标函数的界：则目标函数的界：40, 100n限界函数为限界函数为：)()(11iiwvwWvub分支限界法的设计思

8、想分支限界法的设计思想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=65234567891PT表图9.1 0/1背包问题分支限界法的设计思想分支限界法的设计思想n分支限界法的搜索过程如下：分支限界法的搜索过程如下：n在根结点在根结点1 没有物品装入背包，没有物品装入背包，w=0,v=0 限界函数值：限界函数值：ub=0+(10-0)=1010=100n在结点在结点2 物品物品1装入背包，装入背包，w=w1=4，v

9、=40 目标函数值目标函数值:ub=40 + (10-4)6=76 将结点将结点2加入待处理结点表加入待处理结点表PT中中n在结点在结点3 物品物品1不装入背包，不装入背包， w=0,v=0 目标函数值目标函数值: 10ub=0+(10-0)660， 将结点将结点3加入表加入表PT中中n在表在表PT中选取目标函数值取得中选取目标函数值取得极大的结点极大的结点2 优先进行搜索；优先进行搜索； 分支限界法的设计思想分支限界法的设计思想n在结点在结点4 物品物品2装入背包，装入背包，w=11W，不满足约束条件，不满足约束条件， 将结点将结点4丢弃丢弃n在结点在结点5 物品物品2不装入背包，不装入背包

10、， w=4,v=40 与结点与结点2相同相同 目标函数值为目标函数值为: ub=40 + (10-4)5=70 将结点将结点5加入表加入表PT中中n在结点在结点6 物品物品3装入背包，装入背包，w=4+5=9，v=40+25=65 目标函数值为目标函数值为: ub=65 + (10-9)4=69 将结点将结点6加入表加入表PT中中在表在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点5 优先进行搜索优先进行搜索分支限界法的设计思想分支限界法的设计思想n在结点在结点7 物品物品3不装入背包，不装入背包，w=4,v=40,与结点与结点5相同相同 目标函数值为：目标函数值为：ub=

11、40 + (10-4)464 将结点将结点7加入表加入表PT中中n在结点在结点8 物品物品4装入背包，装入背包，w=12W, 不满足约束条件，将结点不满足约束条件，将结点8丢弃；丢弃；n在结点在结点9 物品物品4 4不装入背包，不装入背包，w=9, v=65, ,与结点与结点6相同相同 目标函数值为目标函数值为: :ub=65+(W-w)*0=65 将结点将结点7加入表加入表PT中中在表在表PT 中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点6 优先进行搜索优先进行搜索分支限界法的设计思想分支限界法的设计思想n结点结点9是叶子结点是叶子结点 同时结点同时结点9 的目标函数值是表的

12、目标函数值是表PT 中的极大值，中的极大值， 结点结点9 对应的解即是问题的最优解，对应的解即是问题的最优解，搜索结束搜索结束n在图在图9.1的的0/1背包问题中，为了在搜索过程中背包问题中，为了在搜索过程中构建搜索构建搜索经过的树结构经过的树结构，设一个表，设一个表PTPT，记录搜索过程，如图，记录搜索过程，如图9.2。n再设计了一表再设计了一表ST，从，从PTPT中中取出最大值结点进行扩充取出最大值结点进行扩充时，时，将最大值结点存储到表将最大值结点存储到表ST中，表中，表PT和表和表ST的数据结构的数据结构为：为： ( (物品物品i-1的选择结果，的选择结果， ub) ) 在搜索过程中表

13、在搜索过程中表PTPT和表和表ST 的状态如图的状态如图9.2所示所示分支限界法的设计思想分支限界法的设计思想(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

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

15、=表表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中所有小于

16、中所有小于value的结点删除；的结点删除；分支限界法的设计思想分支限界法的设计思想n目标函数目标函数“界界”的特性的特性n问题的解向量为问题的解向量为X=(x1, x2, , xn)，其中，其中，xi 的取值范围的取值范围为某个有穷集合为某个有穷集合Si，|Si|=ri（1in）n 是部分解，是部分解， 是相应的界是相应的界n对最小值问题对最小值问题，称为下界，意思是，称为下界，意思是向下搜索所可能取向下搜索所可能取得得的值的值最小不会小于这些下界最小不会小于这些下界。若。若X=(x1, x2, , xn)是是所得到的部分解，满足：所得到的部分解，满足：),()(211kxxxx),(),(

17、211kxxxboundxbound),(),()(21211kxxxboundxxboundxbound分支限界法的设计思想分支限界法的设计思想n对最大值问题对最大值问题，称为上界，意思是向下搜索所可能取，称为上界，意思是向下搜索所可能取得的值最大不会大于这些上界。若得的值最大不会大于这些上界。若 是所得到的部分解，满足：是所得到的部分解，满足：),(21kxxxX),(),()(21211kxxxboundxxboundxbound分支限界法的设计思想分支限界法的设计思想分支限界法的设计思想分支限界法的设计思想n用分支限界法求解问题的关键用分支限界法求解问题的关键n如何确定合适的如何确定合

18、适的限界函数限界函数限界函数用于估算结点的目标函数的可能取值。好的限界函数用于估算结点的目标函数的可能取值。好的限界函数不仅计算简单，还要保证最优解在搜索空间限界函数不仅计算简单，还要保证最优解在搜索空间中，更重要的是能尽早对超出目标函数界的结点进行中，更重要的是能尽早对超出目标函数界的结点进行剪枝，减少搜索空间。有时需要对具体的问题实例进剪枝，减少搜索空间。有时需要对具体的问题实例进行大量实验才能确定一个合理的限界函数。行大量实验才能确定一个合理的限界函数。n如何组织如何组织待处理结点表待处理结点表为提高查找极值的效率，待处理结点表为提高查找极值的效率，待处理结点表PT可采用堆或可采用堆或优

19、先队列的形式存储。优先队列的形式存储。分支限界法的设计思想分支限界法的设计思想n用分支限界法求解问题的关键（续）用分支限界法求解问题的关键（续）n如何确定最优解中如何确定最优解中的各个分量的各个分量分支限界法对问题的解空间树中结点的处理是跳跃式分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单纯地沿着双亲结点一层一层向上回的，回溯也不是单纯地沿着双亲结点一层一层向上回溯，因此当搜索到最优解（叶子结点）时，却无法求溯，因此当搜索到最优解（叶子结点）时，却无法求得该叶子结点对应的最优解中的各个分量。解决方法：得该叶子结点对应的最优解中的各个分量。解决方法：n对每个扩展结点保存根结点到该

20、结点的路径；对每个扩展结点保存根结点到该结点的路径；n在搜索过程中构建搜索经过的树结构，在求得最优在搜索过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。解中的各个分量。分支限界法的设计思想分支限界法的设计思想(c) 扩展结点扩展结点5后后 (d) 扩展结点扩展结点6 后，最优解为后，最优解为(1,0,1,0)65 图图9.3 方法确定方法确定0/1背包问题最优解的各分量背包问题最优解的各分量(a) 扩展根结点后扩展根结点后 (b) 扩展结点扩展结点2后后(0,76) (0,60)PTST(0,60)

21、(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 分支限界法的时间性能分支限界法的时间性能n与回溯法相同点与回溯法相同点n分支限界法分支限界法和和回溯法回溯法实际上都是基于蛮力法，遍历具有实际上都是基于蛮力法，遍历具有指数阶个结点的解空间树指数阶个结点的解空间树n在最坏情况下，时间复杂性肯定为指数阶在最坏情况下，时间

22、复杂性肯定为指数阶2n或或nnn与回溯法不同点与回溯法不同点n分支限界法分支限界法首先扩展解空间树中的上层结点首先扩展解空间树中的上层结点，并用，并用限界限界函数大范围剪枝函数大范围剪枝n根据限界函数根据限界函数不断调整搜索方向不断调整搜索方向，选择最有可能取得最，选择最有可能取得最优解的子树优先进行搜索优解的子树优先进行搜索n如果选择了结点的合理如果选择了结点的合理扩展顺序扩展顺序以及设计以及设计好的限界函数好的限界函数，分支界限法分支界限法可以快速得到问题的解可以快速得到问题的解9.1.2 分支限界法的时间性能分支限界法的时间性能 n分支限界法的代价分支限界法的代价n首先，设计首先，设计一

23、个好的限界函数通常需要花费更多的时间一个好的限界函数通常需要花费更多的时间计算相应的目标函数值计算相应的目标函数值，而且对于具体的问题实例，通，而且对于具体的问题实例，通常需要进行大量实验，才能确定一个好的限界函数；常需要进行大量实验，才能确定一个好的限界函数；n其次，分支限界法其次，分支限界法对解空间树中结点的处理是跳跃式的对解空间树中结点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最优值时，为了从该因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个叶子结点求出对应的最优解中的各个分量，需要对每个扩展结点保存该结点到根结点的路径扩展结点保存该

24、结点到根结点的路径，或者在搜索过程，或者在搜索过程中构建搜索经过的树结构，这使得中构建搜索经过的树结构，这使得算法的设计较为复杂算法的设计较为复杂；n再次，分支限界法为维护再次，分支限界法为维护PT 表表需要较大的存储空间需要较大的存储空间，在，在最坏情况下，分支限界法需要的最坏情况下，分支限界法需要的空间复杂性是指数阶空间复杂性是指数阶。 9.1.2 分支限界法的时间性能分支限界法的时间性能 第第9章章 分支限界法分支限界法 9.1 概概 述述 9.2 图问题中的分支限界法图问题中的分支限界法9.3 组合问题中的分支限界法组合问题中的分支限界法9.2 图问题中的分支限界法图问题中的分支限界法

25、 9.2.1 TSP问题问题 9.2.2 多段图的最短路径问题多段图的最短路径问题9.2.1 TSP问题问题 TSP TSP问题是指旅行家要旅行问题是指旅行家要旅行n个城市，要求各个城个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。的路程最短。271563134253984C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (a) 一个无向图一个无向图 (b) 无向图的代价矩阵无向图的代价矩阵图图9.4 无向图及其代价矩阵无向图及其代价矩阵n确定上界确定上界ubn采用贪心法求得近似解为采

26、用贪心法求得近似解为: :135421 ub=1+2+3+7+3=16 这可以作为这可以作为TSP问题的上界问题的上界n确定下界确定下界lbn把矩阵中每一行最小的元素相加，可以得到一个简单的下界把矩阵中每一行最小的元素相加，可以得到一个简单的下界: : lb=1+3+1+3+2=10n一个信息量更大的下界：把矩阵中每一行最小的两个元素相加再一个信息量更大的下界：把矩阵中每一行最小的两个元素相加再除以除以2，再对这个结果向上取整，就得到了一个合理的下界，再对这个结果向上取整，就得到了一个合理的下界: : lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14 则，目标函数的界

27、则，目标函数的界:lb, ub=14, 16注意：该解并不是一个合法的选择（即没构成哈密顿回路），仅给注意：该解并不是一个合法的选择（即没构成哈密顿回路），仅给出了一个出了一个参考下界参考下界。9.2 TSP问题问题271563134253984n 部分解的目标函数值的计算方法部分解的目标函数值的计算方法n假设当前已确定的路径为假设当前已确定的路径为U=(r1,r2,rk), 则：则： 例如图例如图10.4所示无向图，如果部分解包含顶点所示无向图，如果部分解包含顶点U=(1, 4)，则该，则该部分解的下界是部分解的下界是: lb=(2*5+(1+3)+(3+6)+(1+2)+(2+3)/2=1

28、6UrUrjikiiiijrrrrclb2/ )2(111行最小的两个元素素行不在路径上的最小元分支限界法求解分支限界法求解TSP问题示例问题示例271563134253984C= 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 nTSP问题的搜索过程问题的搜索过程n根结点根结点1，加入表，加入表PT，为扩展结点，为扩展结点 目标函数: lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14n考察孩子结点。结点考察孩子结点。结点2:C1C2, 路径长度为3 目标函数:lb=(2*3+(1+6)+(1+2)+(3+4)+(2+3)/2=14 将

29、结点2加入待处理结点表PT中；n在结点在结点3：C1C3，路径长度为1 目标函数:lb=(2*1+(3+2)+(3+6)+(3+4)+(2+3)/2=14 将结点3加入表PT中n在结点在结点4：C1C4，路径长度为5 目标函数:lb=(2*5+(1+3)+(3+6)+(1+2)+(2+3)/2=16 将结点4加入表PT中 3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 1111,(2 ) / 2jkiiijiikrUlbc rrrr行不在路径上的最小元素行最小的两个元素n在结点在结点5：C1C5，路径长度为8 目标函数：lb=(2*8+(1+2)+(3+6)+(

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

31、9 2 3 n在结点在结点8， C1 C2C5 ，路径长度为3+9目标函数目标函数: lb=(2*12+(1+2)+(1+2)+(3+4)/2=19超出目标函数的界，将结点超出目标函数的界，将结点8丢弃丢弃n处理结点处理结点3的孩子。结点的孩子。结点9， C1 C3C2 ，路径长度为1+6 目标函数值目标函数值:lb=(2*7+(3+3)+(3+4)+(2+3)/2=16 将结点将结点9加入表加入表PT中中n在结点在结点10， C1 C3C4 ，路径长度为1+4 目标函数目标函数:lb=(2*5+(3+3)+(3+6)+(2+3)/2=15 将结点将结点10加入表加入表PT中中分支限界法求解分

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

33、=19 超出目标函数的界，将结点12丢弃n在结点在结点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

34、)/2=16由于结点14为叶子结点，得到一个可行解其路径长度为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*

35、8+(3+2)+(3+6)/2=15 将结点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

36、=1932lb=1634lb=1535lb=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后的状态后的

37、状态(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,

38、 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后的状态后的状态算法算法9.1TSP问题问题输入：图输入：图G（V，E）输出：最短哈密尔顿回路输出：最短哈密尔顿回路 1根据限界函数计算目标函数的下界根据限界函数计算目标函数的下界down；采用贪心法得到上界；采用贪心

39、法得到上界up； 2计算根结点的目标函数值并加入待处理结点表计算根结点的目标函数值并加入待处理结点表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.

40、8所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：（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，将

41、结点5加入表PT中；在结点6，第2段选择边，目标函数值为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=1603

42、lb=15图图9.8 分支限界法求解多段图的最短路径问题示例分支限界法求解多段图的最短路径问题示例(表示该结点被丢弃，结点上方的数组表示搜索顺序表示该结点被丢弃，结点上方的数组表示搜索顺序)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

43、 0/1背包问题背包问题n问题描述问题描述 任务分配问题要求把任务分配问题要求把n项任务分配给项任务分配给n个人，每个人完成个人，每个人完成每项任务的成本不同，要求分配总成本最小的最优分配方每项任务的成本不同，要求分配总成本最小的最优分配方案。如图案。如图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 任务分配问题的成本矩阵任务分配问题的成本矩阵n如何求最优分配成本的上界如何求最

44、优分配成本的上界Up和下界和下界Downn获得上界获得上界UPn如考虑以如考虑以矩阵的对角线矩阵的对角线作为一个可行解作为一个可行解:任务任务1人员人员a、任务、任务2给人员给人员b任务任务3人员人员c、任务、任务4人员人员d 成本成本： 9+4+1+4=18n或应用贪心法求得一个近似解：或应用贪心法求得一个近似解： 任务任务2人员人员a、任务、任务3人员人员b 任务任务1人员人员c、任务、任务4人员人员d成本成本: :2+3+5+4=14 14 是一个更好的上界是一个更好的上界9.3.2 任务分配问题任务分配问题 C9 2 7 86 4 3 75 8 1 87 6 9 4任务任务1 任务任务

45、2 任务任务3 任务任务4人员人员a人员人员b人员人员c人员人员d图图9.10 任务分配问题的成本矩阵任务分配问题的成本矩阵n获得下界获得下界Downn考虑考虑n人员人员a所有任务的最小代价是所有任务的最小代价是2n人员人员b执行所有任务的最小代价是执行所有任务的最小代价是3n人员人员c执行所有任务的最小代价是执行所有任务的最小代价是1n人员人员d执行所有任务的最小代价是执行所有任务的最小代价是4 每行取最小元素，其成本下界：每行取最小元素，其成本下界：2+3+1+4=10 则上下界为：则上下界为：10, 14 注意：这个解并不是一个合法的选择注意：这个解并不是一个合法的选择 因为：因为：3、

46、1来自于矩阵同一列，仅给出一个参考下界来自于矩阵同一列，仅给出一个参考下界9.3.2 任务分配问题任务分配问题 n设当前已对人员设当前已对人员1 1i i分配了任务，并且获得了成本分配了任务，并且获得了成本v v，则限界函数，则限界函数可以定义为：可以定义为： （式（式9.49.4）n搜索过程搜索过程n在根结点在根结点1 没有分配任务，限界函数函数值为:lb=2+3+1+4=10n在结点在结点2 将J1人员a，获得的成本为9 目标函数值为: lb=9 + (3+1+4)=17 超出目标函数的界10, 14，将结点2丢弃nikkvlb1行的最小值第9.3.2 任务分配问题任务分配问题 C9 2

47、7 86 4 3 75 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

48、任务任务4人员人员a人员人员b人员人员c人员人员d任务1任务4任务2任务1任务3任务4任务1任务49.3.2 任务分配问题任务分配问题 n搜索过程搜索过程n在结点在结点3 将J2人员a，获得的成本为2 目标函数值:lb=2 + (3+1+4)=10 将结点3 -PT表中n在结点在结点4 将J3人员a，获得的成本为7 目标函数值:lb=7 + (3+1+4)=15 超出目标函数的界10, 14，将结点4丢弃9.3.2 任务分配问题任务分配问题 C9 2 7 86 4 3 75 8 1 87 6 9 4任务任务1 任务任务2 任务任务3 任务任务4人员人员a人员人员b人员人员c人员人员dn在结点在

49、结点5 将J4人员a，获得的成本为8 目标函数值:lb=8 + (3+1+4)=16 超出目标函数的界10, 14，将结点5丢弃n在结点在结点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 4任务任务1 任务任务2 任务任务3 任务任务4人员人员a人员人员b人员人员c人员人员dn在结点在结点7 将J2人员a，J3人员b，获得的成本为2+3=5 目标函数

50、值:lb=5+(1+4)10 将结点7加入表PT中n在结点在结点8 将J2人员a，J4人员b，获得的成本为2+7=9 目标函数值:lb=9+(1+4)14 将结点8加入表PT中； 在表在表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人员人员dn在结点在结点9 将J2人员a，J3人员b ，J1人员c，获得的成本为5+5=10 目标函数值:lb=10+4=14 将结点9加入表PT中n在结点在结

51、点10 将J2人员a，J3人员b ，J4人员c，获得的成本为5+8=13 目标函数值:lb=13+4=17 超出目标函数的界10, 14，将结点10丢弃在表在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点6 6优先进行搜索优先进行搜索9.3.2 任务分配问题任务分配问题 n在结点在结点11 将J2人员a,J1人员b， J3人员c，获得的成本为8+1=9 目标函数值:lb=9+4=13 将结点11加入表PT中n在结点在结点12 将J2人员a,J1人员b，J4人员c，获得的成本为8+8=16 目标函数值:lb=16+4=20 超出目标函数的界10, 14，将结点12丢弃；在表在表PT中

52、选取目标函数值极小的结点中选取目标函数值极小的结点1111优先进行搜索优先进行搜索9.3.2 任务分配问题任务分配问题 9 2 7 86 4 3 75 8 1 87 6 9 4任务任务1 任务任务2 任务任务3 任务任务4n在结点在结点13 将J2人员a,J1人员b，J3人员c ，J4人员d 获得的成本为9+4=13 目标函数值为:lb=13 由于结点13是叶子结点，同时结点13的目标函数值是表PT中的极小值， 所以，结点13对应的解即是问题的最优解 搜索结束。n构建搜索经过的树结构构建搜索经过的树结构n取出表取出表PT中最小值结点进行扩充时，并将最小值结点存中最小值结点进行扩充时，并将最小值

53、结点存储到储到ST中，表中，表PT 和表和表 ST 的数据结构为：的数据结构为： (人员人员i-1分配的任务分配的任务,lb)9.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) 扩展根结点后的状态扩展根结点后

54、的状态 (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 分配任务分配任

55、务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=表表

56、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背包问题背包问题n问题描述问题描述nn个作业的集合个作业的集合J=J1, J2, , Jn，

57、n每个作业都有每个作业都有3项任务分别在项任务分别在3台机器上完成台机器上完成nJi 需要机器需要机器j 的处理时间为的处理时间为tij（1in, 1j3）n作业处理顺序作业处理顺序: 机器机器1处理处理机器机器2处理处理机器机器3处理处理n批处理作业调度问题批处理作业调度问题?n要求确定这要求确定这 n 个作业的最优处理顺序使得从第个作业的最优处理顺序使得从第1个作业个作业在机器在机器1上处理开始，到最后一个作业在机器上处理开始，到最后一个作业在机器3上处理结上处理结束所需的时间最少。束所需的时间最少。n最优调度原则最优调度原则使机器使机器1没有空闲时间，且机器没有空闲时间，且机器2和和3的

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

59、理顺序为: :J4 J1 J3 J2，调度方案，调度方案: :J4:7 J1:5 J3:9 J2:10机器机器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 开始的处理顺序，估算处理所需的

60、最短时间是最短时间是：tij: 表示表示 Ji 需要机器需要机器 j 的处理时间的处理时间(1in, 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）sum