算法设计与分析-王红梅-第二版-第9章-分支限界法课件.ppt

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

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

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

4、行解（第一个叶子）后才有意义，此后的搜索相对，此后的搜索相对来说才有方向，所以从搜索的整个过程来看还是盲目的。来说才有方向，所以从搜索的整个过程来看还是盲目的。如如TSPTSP问题（图问题（图8.68.6）。）。n分支限界法分支限界法n先确定一个合理的先确定一个合理的限界函数限界函数n由限界函数确定目标函数的界由限界函数确定目标函数的界down,updown,upn仍以仍以穷举法的解空间树穷举法的解空间树为基础，但以为基础，但以广度优先的原理广度优先的原理搜搜索该结点的所有孩子结点，分别估算这些索该结点的所有孩子结点，分别估算这些孩子结点的目孩子结点的目标函数的可能取值标函数的可能取值分支限界

5、法的设计思想分支限界法的设计思想n如果某孩子结点的目标函数如果某孩子结点的目标函数可能取值超出目标函数的界，则可能取值超出目标函数的界，则将其丢弃，将其丢弃，因为从这个结点生成的解不会比目前已经得到的因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表（表解更好；否则，将其加入待处理结点表（表PTPT）n依次从表依次从表PTPT中选取使目标函数的值取极值的结点成为当前扩中选取使目标函数的值取极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。展结点，重复上述过程，直到找到最优解。n目标函数的界目标函数的界down,updown,up的确定的确定n对最大化问题对最大

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

7、重量价值从大到小排序，结果如下：价值从大到小排序，结果如下：物品物品重量重量(w)价值价值(v)价值价值/重量重量(v/w)144010274263525543124分支限界法的设计思想分支限界法的设计思想n确定上下界确定上下界 ndowndown：应用贪心法求得近似解为应用贪心法求得近似解为(1,0,0,0)(1,0,0,0)，获得的，获得的价值为价值为4040，这可以作为，这可以作为0/10/1背包问题的背包问题的下界下界。nupup：考虑最好情况，背包中全部装入第考虑最好情况，背包中全部装入第1 1个物品且可以个物品且可以将背包装满，则可得到一个将背包装满，则可得到一个简单上界简单上界的

8、计算方法：的计算方法：up=Wup=W(v(v1 1/w/w1 1)=10)=1010=10010=100n则目标函数的界：则目标函数的界：40,10040,100n限界函数为限界函数为：)()(11iiwvwWvub分支限界法的设计思想分支限界法的设计思想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分支限界法的搜索过程如下：分支限

9、界法的搜索过程如下：n在根结点在根结点1 1 没有物品装入背包，没有物品装入背包，w=0,v=0w=0,v=0 限界函数值：限界函数值：ub=0+(10-0)=10ub=0+(10-0)=1010=10010=100n在结点在结点2 2 物品物品1 1装入背包，装入背包，w=ww=w1 1=4=4，v=40v=40 目标函数值目标函数值:ub=40+(10-4)ub=40+(10-4)6=766=76 将结点将结点2 2加入待处理结点表加入待处理结点表PTPT中中n在结点在结点3 3 物品物品1 1不装入背包，不装入背包，w=0,v=0w=0,v=0 目标函数值目标函数值:10ub=0+(10

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

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

12、ub=40+(10-4)ub=40+(10-4)4 46464 将结点将结点7 7加入表加入表PTPT中中n在结点在结点8 8 物品物品4 4装入背包，装入背包，w=12W,w=12W,不满足约束条件，将结点不满足约束条件，将结点8 8丢弃；丢弃；n在结点在结点9 9 物品物品4 4不装入背包，不装入背包，w=9,v=65w=9,v=65,与结点与结点6 6相同相同 目标函数值为目标函数值为:ub=65+(W-w)ub=65+(W-w)*0=650=65 将结点将结点7 7加入表加入表PTPT中中在表在表PT PT 中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点6 6 优先进行搜

13、索优先进行搜索分支限界法的设计思想分支限界法的设计思想n结点结点9 9是叶子结点是叶子结点 同时结点同时结点9 9 的目标函数值是表的目标函数值是表PT PT 中的极大值，中的极大值，结点结点9 9 对应的解即是问题的最优解，对应的解即是问题的最优解，搜索结束搜索结束n在图在图9.19.1的的0/10/1背包问题中，为了在搜索过程中背包问题中，为了在搜索过程中构建搜构建搜索经过的树结构索经过的树结构，设一个表，设一个表PTPT，记录搜索过程，如图，记录搜索过程，如图9.29.2。n再设计了一表再设计了一表STST，从，从PTPT中中取出最大值结点进行扩充取出最大值结点进行扩充时，时，将最大值结

14、点存储到表将最大值结点存储到表STST中，表中，表PTPT和表和表STST的数据结构的数据结构为：为：(物品物品i-1i-1的选择结果，的选择结果，ubub)在搜索过程中表在搜索过程中表PTPT和表和表ST ST 的状态如图的状态如图9.29.2所示所示分支限界法的设计思想分支限界法的设计思想(c)(c)扩展结点扩展结点5 5后后 (d)(d)扩展扩展结点结点6 6 后，最优解为后，最优解为(1,0,1,0)65(1,0,1,0)65 图图9.2 9.2 方法确定方法确定0/10/1背包问题最优解背包问题最优解的各分量的各分量(a)扩展根结点后扩展根结点后 (b)扩展结点扩展结点2后后(0,7

15、6)(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分支限界法的设计思想分支限界法的设计思想分支限界法的设计思想分支限界法的设计思想分支限界法的一般过程分支限界法的一般过程 1 1根据限界函数计算目标函数的根据限界函数计算目标函数的 downdown，upup；2 2将待处理结点表将待处理结点表PT PT 初始化为空；初始化为空；3.3.对根结点的每个孩子结点对根结点的每个孩子结点x x执行下列操作执行下列操作 3.1

16、 3.1 估算结点估算结点x x的目标函数值的目标函数值value;value;3.2 3.2 若（若（value=downvalue=down）,则将结点则将结点x x加入表加入表PTPT中；中；4 4循环直到某个叶子结点的目标函数值在表循环直到某个叶子结点的目标函数值在表PTPT中最大中最大4.1 4.1 i i=表表PTPT中值最大的结点；中值最大的结点；4.2 4.2 对结点对结点i i的每个孩子结点的每个孩子结点x x执行下列操作执行下列操作4.2.1 4.2.1 估算结点估算结点x x的目标函数值的目标函数值valuevalue；4.2.2 4.2.2 若若(value=down)

17、(value=down)，则将结点，则将结点x x加入表加入表PTPT中；中；4.2.3 4.2.3 若（结点若（结点x x是叶子结点且是叶子结点且valuevalue值在表值在表PTPT中最大），则将中最大），则将结点结点x x对应的解输出，算法结束；对应的解输出，算法结束；4.2.4 4.2.4 若若(结点结点x x是叶子结点但是叶子结点但valuevalue值在表值在表PTPT中不是最大中不是最大),),则令则令down=valuedown=value，并且将表，并且将表PTPT中所有小于中所有小于valuevalue的结点删除；的结点删除；分支限界法的设计思想分支限界法的设计思想n目标

18、函数目标函数“界界”的特性的特性n问题的解向量为问题的解向量为X=(xX=(x1 1,x,x2 2,x xn n)，其中，其中，x xi i 的取值的取值范围为某个有穷集合范围为某个有穷集合S Si i，|S|Si i|=|=r ri i（1in1in）n 是部分解，是部分解，是相应的界是相应的界n对最小值问题对最小值问题，称为下界，意思是，称为下界，意思是向下搜索所可能取向下搜索所可能取得得的值的值最小不会小于这些下界最小不会小于这些下界。若。若X=(xX=(x1 1,x,x2 2,x xn n)是所得到的部分解，满足：是所得到的部分解，满足：),()(211kxxxx),(),(211kx

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

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

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

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

23、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 概概 述述 9.1.1 9.1.1 分支限界法的设计思想分支限界法的设计思想9.1.2 9.1.2 分支限界法的时间性分支限界法的时间性能能n与回溯法相同点与回溯法相同点n分支限界法分支限界法和和回溯法回溯法实际上都是基于蛮力法，遍历具有实际上都是基于蛮力法，遍历具有指数阶个结点的解空间树指数阶个结点的解空间树

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

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

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

27、问题中的分支限界法9.3 9.3 组合问题中的分支限界法组合问题中的分支限界法9.2 9.2 图问题中的分支限界图问题中的分支限界法法 9.2.1 TSP9.2.1 TSP问题问题 9.2.2 9.2.2 多段图的最短路径问多段图的最短路径问题题9.2.1 TSP9.2.1 TSP问题问题 TSP TSP问题是指旅行家要旅行问题是指旅行家要旅行n n个城市，要求各个城个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。的路程最短。271563134253984C C=3 3 1 1 5 85 8 3 3 6 6 7 97 9

28、 1 1 6 6 4 4 2 2 5 5 7 4 7 4 3 3 8 9 8 9 2 2 3 3 (a)(a)一个无向图一个无向图 (b)(b)无无向图的代价矩阵向图的代价矩阵图图9.4 9.4 无向图及其代价矩阵无向图及其代价矩阵n确定上界确定上界ububn采用贪心法求得近似解为采用贪心法求得近似解为:135421135421 ub=1+2+3+7+3=16ub=1+2+3+7+3=16 这可以作为这可以作为TSPTSP问题的上界问题的上界n确定下界确定下界lblbn把矩阵中每一行最小的元素相加，可以得到一个简单的下界把矩阵中每一行最小的元素相加，可以得到一个简单的下界:lb=1+3+1+3

29、+2=10lb=1+3+1+3+2=10n一个信息量更大的下界：把矩阵中每一行最小的两个元素相加再一个信息量更大的下界：把矩阵中每一行最小的两个元素相加再除以除以2 2，再对这个结果向上取整，就得到了一个合理的下界，再对这个结果向上取整，就得到了一个合理的下界:lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14 则，目标函数的界则，目标函数的界:lb,ub=14,16:lb,ub=14,16注意：该解并不是一个合法的选择（即没构成哈密顿回路），仅给注意：该解并不是一个合法的选择（即没构成哈密顿回路

30、），仅给出了一个出了一个参考下界参考下界。9.2 TSP9.2 TSP问题问题271563134253984n 部分解的目标函数值的计算方法部分解的目标函数值的计算方法n假设当前已确定的路径为假设当前已确定的路径为U=(rU=(r1 1,r,r2 2,r,rk k),),则：则：例如图例如图10.410.4所示无向图，如果部分解包含顶点所示无向图，如果部分解包含顶点U=(1,4)U=(1,4)，则，则该部分解的下界是该部分解的下界是:lb=(2lb=(2*5 5+(1+3)+(3+6)+(1+2)+(2+3)/2=16+(1+3)+(3+6)+(1+2)+(2+3)/2=16UrUrjikii

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

32、 3 目标函数:lb=(2lb=(2*3+(1+6)+(1+2)+(3+4)+(2+3)/2=143+(1+6)+(1+2)+(3+4)+(2+3)/2=14 将结点2 2加入待处理结点表PTPT中；n在结点在结点3 3：C C1 1C C3 3，路径长度为1 1 目标函数:lb=(2:lb=(2*1+(3+2)+(3+6)+(3+4)+(2+3)/2=141+(3+2)+(3+6)+(3+4)+(2+3)/2=14 将结点3 3加入表PTPT中n在结点在结点4 4：C C1 1C C4 4，路径长度为5 5 目标函数:lb=(2lb=(2*5+(1+3)+(3+6)+(1+2)+(2+3)/

33、2=165+(1+3)+(3+6)+(1+2)+(2+3)/2=16 将结点4 4加入表PTPT中 3 3 1 1 5 85 8 3 3 6 6 7 97 9 1 1 6 6 4 4 2 2 5 5 7 7 4 4 3 3 8 9 8 9 2 2 3 3 1111,(2)/2jkiiijiikrUlbc rrrr行不在路径上的最小元素行最小的两个元素n在结点在结点5 5：C C1 1C C5 5，路径长度为8 8 目标函数：lb=(2lb=(2*8+(1+2)+(3+6)+(1+2)+(3+4)/2=198+(1+2)+(3+6)+(1+2)+(3+4)/2=19 超出目标函数的界，将结点5

34、5丢弃；n处理结点处理结点2 2的孩子结点。结点的孩子结点。结点6,6,C C1 1C C2 2C C3 3,路径长度为3+6 6 目标函数:lb=(2lb=(2*9+(1+1)+(3+4)+(2+3)/2=169+(1+1)+(3+4)+(2+3)/2=16 将结点6 6加入表PTPT中n在结点在结点7 7，C C1 1 C C2 2C C4 4，路径长度为3+7 目标函数lb=(2lb=(2*10+(1+3)+(1+2)+(2+3)/2=1610+(1+3)+(1+2)+(2+3)/2=16 将结点7 7加入表PTPT中分支限界法求解分支限界法求解TSPTSP问题示例问题示例在表在表PTP

35、T中选取目标函数值极小的结点中选取目标函数值极小的结点2 2优先进行搜索优先进行搜索 3 3 1 1 5 85 8 3 3 6 6 7 7 9 9 1 1 6 6 4 4 2 2 5 5 7 7 4 4 3 3 8 9 2 8 9 2 3 3 n在结点在结点8 8，C C1 1 C C2 2C C5 5，路径长度为3+9目标函数目标函数:lb=(2lb=(2*12+(1+2)+(1+2)+(3+4)/2=1912+(1+2)+(1+2)+(3+4)/2=19超出目标函数的界，将结点超出目标函数的界，将结点8 8丢弃丢弃n处理结点处理结点3 3的孩子。结点的孩子。结点9 9，C C1 1 C C

36、3 3C C2 2，路径长度为1+6 目标函数值目标函数值:lb=(2lb=(2*7+(3+3)+(3+4)+(2+3)/2=167+(3+3)+(3+4)+(2+3)/2=16 将结点将结点9 9加入表加入表PTPT中中n在结点在结点1010，C C1 1 C C3 3C C4 4，路径长度为1+4 目标函数目标函数:lb=(2lb=(2*5+(3+3)+(3+6)+(2+3)/2=155+(3+3)+(3+6)+(2+3)/2=15 将结点将结点1010加入表加入表PTPT中中分支限界法求解分支限界法求解TSPTSP问题示例问题示例在表在表PTPT中选取目标函数值极小的结点中选取目标函数值

37、极小的结点3 3优先进行搜索优先进行搜索 3 3 1 1 5 85 8 3 3 6 6 7 97 9 1 1 6 6 4 4 2 2 5 5 7 7 4 4 3 3 8 8 9 9 2 2 3 3 n在结点在结点1111，C C1 1C C3 3C C5 5，路径长度为1+2 目标函数值:lb=(2lb=(2*3+(3+3)+(3+6)+(3+4)/2=143+(3+3)+(3+6)+(3+4)/2=14 将结点1111加入表PTPT中在表在表PTPT中选取目标函数值极小的结点中选取目标函数值极小的结点1111优先进行搜索优先进行搜索n处理结点处理结点1111的孩子。结点的孩子。结点1212，

38、C C1 1C C3 3C C5 5C C2 2，路径长度为1+2+9，目标函数值:lb=(2lb=(2*12+(3+3)+(3+4)/2=1912+(3+3)+(3+4)/2=19 超出目标函数的界，将结点1212丢弃n在结点在结点1313，C C1 1C C3 3 C5C5C C4 4，路径长度为1+2+3 目标函数值：lb=(2lb=(2*6+(3+4)+(3+6)/2=14,6+(3+4)+(3+6)/2=14,将结点1313加入表PTPT中在表在表PTPT中选取目标函数值极小的结点中选取目标函数值极小的结点1313优先进行搜索优先进行搜索 3 3 1 1 5 85 8 3 6 3 6

39、 7 7 9 9 1 1 6 6 4 4 2 2 5 5 7 4 7 4 3 3 8 8 9 9 2 2 3 3 在表在表PTPT中选取目标函数值极小的结点中选取目标函数值极小的结点1010优先进行搜索优先进行搜索n处理结点处理结点1313的孩子。结点的孩子。结点1414，C C1 1C C3 3 C5C5C4C4C C2 2，路径长度为1+2+3+7，目标函数值:lb=(2lb=(2*13+(3+3)/2=1613+(3+3)/2=16由于结点1414为叶子结点，得到一个可行解其路径长度为1616 3 3 1 1 5 85 8 3 3 6 6 7 7 9 9 1 1 6 6 4 4 2 2

40、5 5 7 7 4 4 3 3 8 8 9 9 2 2 3 3 分支限界法求解分支限界法求解TSPTSP问题示例问题示例分支限界法求解分支限界法求解TSPTSP问题示例问题示例在表在表PTPT中选取目标函数值极小的结点中选取目标函数值极小的结点1616优先进行搜索优先进行搜索n处理结点处理结点1010的孩子。结点的孩子。结点1515，C C1 1C C3 3 C C4 4C C2 2，长度，长度1212。目标函数:lb=(2lb=(2*12+(3+3)+(2+3)/2=1812+(3+3)+(2+3)/2=18 超出目标函数的界，将结点1515丢弃n结点结点1616，C C1 1C C3 3

41、C C4 4C C5 5 ，长度，长度8 8 目标函数:lb=(2lb=(2*8+(3+2)+(3+6)/2=158+(3+2)+(3+6)/2=15 将结点1616加入表PTPT中n处理结点处理结点1616的孩子。结点的孩子。结点1717,C C1 1C C3 3C C4 4C C5 5C C2 2,长度长度1717，目标函数:lb=(2:lb=(2*17+(3+3)/2=20,17+(3+3)/2=20,超目标函数的界，结点1717丢弃表表PTPT中目标函数值均为中目标函数值均为1616，且已找到叶子结点，且已找到叶子结点1414的长度是的长度是1616，故，故这是最优解，搜索过程结束。这

42、是最优解，搜索过程结束。3 3 1 1 5 85 8 3 3 6 6 7 7 9 9 1 1 6 6 4 4 2 2 5 5 7 7 4 4 3 3 8 8 9 9 2 2 3 3 412lb=142356781startlb=1413lb=1414lb=1615lb=1923lb=1624lb=1625lb=1932lb=1634lb=1535lb=1491152lb=1954lb=141142lb=16142lb=1845lb=151152lb=201分支限界法求解分支限界法求解TSPTSP问题示例问题示例C C2 2C C1 1C C3 3C C5 5C C4 4C C3 3C C5 5

43、C C4 4C C2 2C C4 4C C5 5C C4 4C C2 2C C2 2 3 3 1 1 5 85 8 3 3 6 6 7 97 9 1 1 6 6 4 4 2 2 5 5 7 7 4 4 3 3 8 9 8 9 2 2 3 3 (g)扩展结点扩展结点16后的状态，最优解为后的状态，最优解为135421图图9.6 TSP问题最优解的确定问题最优解的确定(1,2)14 (1,3)14 (1,4)16(a)扩展根结点后的状态扩展根结点后的状态 (b)扩展结点扩展结点2后的状态后的状态(c)扩展结点扩展结点3后的状态后的状态(d)扩展结点扩展结点11后的状态后的状态(e)扩展结点扩展结点

44、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)

45、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计算根结点的目标函数值并加入待处理结点表计算根结点的目标函数值并加入待处理结点表PT；3循环直到某个叶子结点的目标函数值在表循环直到某个叶子结点的目标函数值在表PT中取得极小值中取得极小值 3.1 i=表表PT中具有最小值的结点；中具有最小值

46、的结点；3.2 对结点对结点i的每个孩子结点的每个孩子结点x执行下列操作：执行下列操作：3.2.1 估算结点估算结点x的目标函数值的目标函数值lb;3.2.2 若（若（lb kijpiEvrijjjjvrcrrclbpi21,11min1段的最短边段的最短边第第 应用分支限界法求解图9.7所示多段图的最短路径问题，其搜索空间如图9.8所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：（1）在根结点1，计算目标函数的值为14，将根结点加入表PT；（2）处理根结点每个孩子结点。结点2，第1段选择边，目标函数值为lb=4 4+8 8+5+3=20，超出目标函数的界，将结点2丢弃；在结点3，第

47、1段选择边，目标函数值为lb=2 2+7 7+5+3=17，将结点3加入表PT；在结点4，第1段选择边，目标函数值为lb=3 3+4 4+5+3=15，将结点4加入表PT中；（3）在表PT中选取目标函数值极小的结点4优先进行搜索；1203456789492387884756866537（4）在结点5，第2段选择边，目标函数值为lb=3 3+4 4+6 6+3=16，将结点5加入表PT中；在结点6，第2段选择边，目标函数值为lb=3 3+7 7+5 5+3=18，将结点6加入表PT；（5）在表PT中选取目标函数值极小的结点5优先进行搜索；（6）处理结点5的每个孩子结点。结点7，已确定路径是035

48、7，可直接确定第4段的边，目标函数值为lb=3 3+4 4+8 8+7=22，超界丢弃；在结点8，已确定路径是0358，可直接确定第4段的边，目标函数值为lb=3+4+6 6+3=16，为一个可行解；由于结点8是叶子结点，并且其目标函数值是PT中最小的，所以它是最优解，搜索结束。12034567894923878847568665376401lb=20231startlb=1802lb=1603lb=15图图9.8 分支限界法求解多段图的最短路径问题示例分支限界法求解多段图的最短路径问题示例(表示该结点被丢弃，结点上方的数组表示搜索顺序表示该结点被丢弃，结点上方的数组表示搜索顺序)535lb=

49、1636lb=1887lb=22lb=165857第第9 9章章 分支限界法分支限界法 9.1 9.1 概概 述述 9.2 9.2 图问题中的分支限界法图问题中的分支限界法9.3 9.3 组合问题中的分支限界法组合问题中的分支限界法9.3 9.3 组合问题中的分支限界法组合问题中的分支限界法 9.3.2 9.3.2 任务分配问题任务分配问题 9.3.3 9.3.3 批处理作业调度问题批处理作业调度问题9.3.1 0/19.3.1 0/1背包问题背包问题n问题描述问题描述 任务分配问题要求把任务分配问题要求把n n项任务分配给项任务分配给n n个人，每个人完个人，每个人完成每项任务的成本不同，要

50、求分配总成本最小的最优分配成每项任务的成本不同，要求分配总成本最小的最优分配方案。如图方案。如图9.109.10所示是一个任务分配的成本矩阵。所示是一个任务分配的成本矩阵。9.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人员人员d图图9.10 任务分配问题的成本矩阵任务分配问题的成本矩阵n如何求最优分配成本的上界如何求最优分配成本的上界UpUp和下界和下界DownDownn获得上界获得上界UPUPn如考虑以如考虑以矩阵的对角线矩阵的对角线作为一个可行解作为一个