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

第9章分支限界法Branch and Bound Method,算法设计与分析本科生课程Design and Analysis of Algorithm,海南大学信息科学技术学院College of Information Science and Technology,Hainan University,2023/1/17,2,学习目标,Chapter 8 Back Track Method,2023/1/17,Branch and Bound Method,3,第9章 分支限界法,9.1 概 述,9.2 图问题中的分支限界法,9.3 组合问题中的分支限界法,2023/1/17,Branch and Bound Method,4,回溯法：按深度优先策略遍历问题的解空间树，应用约束条件、目标函数等剪枝函数实行剪枝分支限界法：按广度优先策略遍历问题的解空间树，在遍历过程中，对已经处理的每一个结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。,9.1 概 述,2023/1/17,Branch and Bound Method,5,9.1 概 述,9.1.1 分支限界法的设计思想,9.1.2 分支限界法的时间性能,2023/1/17,Branch and Bound Method,6,回溯法存在的问题虽用剪枝减少了搜索空间，但按深度优先策略机械地进行，搜索是盲目的。如0/1背包问题。首先将目标函数初始化为最大值，目标函数只有在有一个可行解（第一个叶子）后才有意义，此后的搜索相对来说才有方向，所以从搜索的整个过程来看还是盲目的。如TSP问题（图8.6）。分支限界法先确定一个合理的限界函数由限界函数确定目标函数的界down,up仍以穷举法的解空间树为基础，但以广度优先的原理搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值,分支限界法的设计思想,2023/1/17,Branch and Bound Method,7,如果某孩子结点的目标函数可能取值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表（表PT）依次从表PT中选取使目标函数的值取极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。目标函数的界down,up的确定对最大化问题Up由限界函数确定，down由某种启发方式得到,如贪心算法对最小化问题down由限界函数确定，up由某种启发方式得到,如贪心算法,分支限界法的设计思想,2023/1/17,Branch and Bound Method,8,例：0/1背包问题。假设有4个物品，其重量分别为(4,7,5,3)，价值分别为(40,42,25,12)，背包容量W=10。首先，将给定物品按单位重量价值从大到小排序，结果如下：,分支限界法的设计思想,2023/1/17,Branch and Bound Method,9,确定上下界 down：应用贪心法求得近似解为(1,0,0,0)，获得的价值为40，这可以作为0/1背包问题的下界。up：考虑最好情况，背包中全部装入第1个物品且可以将背包装满，则可得到一个简单上界的计算方法：up=W(v1/w1)=1010=100则目标函数的界：40,100限界函数为：,分支限界法的设计思想,2023/1/17,Branch and Bound Method,10,PT表,图9.1 0/1背包问题,分支限界法的设计思想,2023/1/17,Branch and Bound Method,11,分支限界法的搜索过程如下：在根结点1 没有物品装入背包，w=0,v=0 限界函数值：ub=0+(10-0)=1010=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)660，将结点3加入表PT中,在表PT中选取目标函数值取得极大的结点2 优先进行搜索；,分支限界法的设计思想,2023/1/17,Branch and Bound Method,12,在结点4 物品2装入背包，w=11W，不满足约束条件，将结点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/1/17,Branch and Bound Method,13,在结点7 物品3不装入背包，w=4,v=40,与结点5相同 目标函数值为：ub=40+(10-4)464 将结点7加入表PT中在结点8 物品4装入背包，w=12W,不满足约束条件，将结点8丢弃；在结点9 物品4不装入背包，w=9,v=65,与结点6相同 目标函数值为:ub=65+(W-w)*0=65 将结点7加入表PT中,在表PT 中选取目标函数值取得极大的结点6 优先进行搜索,分支限界法的设计思想,2023/1/17,Branch and Bound Method,14,结点9是叶子结点 同时结点9 的目标函数值是表PT 中的极大值，结点9 对应的解即是问题的最优解，搜索结束在图9.1的0/1背包问题中，为了在搜索过程中构建搜索经过的树结构，设一个表PT，记录搜索过程，如图9.2。再设计了一表ST，从PT中取出最大值结点进行扩充时，将最大值结点存储到表ST中，表PT和表ST的数据结构为：(物品i-1的选择结果，ub)在搜索过程中表PT和表ST 的状态如图9.2所示,分支限界法的设计思想,2023/1/17,Branch and Bound Method,15,(c)扩展结点5后(d)扩展结点6 后，最优解为(1,0,1,0)65 图9.2 方法确定0/1背包问题最优解的各分量,3,7,9,2,5,6,7,分支限界法的设计思想,2023/1/17,Branch and Bound Method,16,基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点（使目标函数取得极值的结点）成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,分支限界法的设计思想,2023/1/17,Branch and Bound Method,17,分支限界法的一般过程 1根据限界函数计算目标函数的 down，up；2将待处理结点表PT 初始化为空；3.对根结点的每个孩子结点x执行下列操作 3.1 估算结点x的目标函数值value;3.2 若（value=down）,则将结点x加入表PT中；4循环直到某个叶子结点的目标函数值在表PT中最大4.1 i=表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/1/17,Branch and Bound Method,18,目标函数“界”的特性问题的解向量为X=(x1,x2,xn)，其中，xi 的取值范围为某个有穷集合Si，|Si|=ri（1in）是部分解，是相应的界对最小值问题，称为下界，意思是向下搜索所可能取得的值最小不会小于这些下界。若X=(x1,x2,xn)是所得到的部分解，满足：,分支限界法的设计思想,2023/1/17,Branch and Bound Method,19,对最大值问题，称为上界，意思是向下搜索所可能取得的值最大不会大于这些上界。若 是所得到的部分解，满足：,分支限界法的设计思想,2023/1/17,Branch and Bound Method,20,两种分支方法设解向量 X=(x1,x2,xn)xi 的取值范围为有穷集Si，|Si|=n，1in每棵子树都有ni个分支最坏情况下，结点表的空间为O(n1*n2*nn)若状态空间树是完全n叉树，n1=n2=nn=n，结点表的空间为O(nn)每棵子树只有两个分支xi 取特定值的分支、及不取特定值的分支：状态空间树是完全二叉树，最坏情况下结点表的空间为O（2n),分支限界法的设计思想,2023/1/17,Branch and Bound Method,21,用分支限界法求解问题的关键如何确定合适的限界函数限界函数用于估算结点的目标函数的可能取值。好的限界函数不仅计算简单，还要保证最优解在搜索空间中，更重要的是能尽早对超出目标函数界的结点进行剪枝，减少搜索空间。有时需要对具体的问题实例进行大量实验才能确定一个合理的限界函数。如何组织待处理结点表为提高查找极值的效率，待处理结点表PT可采用堆或优先队列的形式存储。,分支限界法的设计思想,2023/1/17,Branch and Bound Method,22,用分支限界法求解问题的关键（续）如何确定最优解中的各个分量分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单纯地沿着双亲结点一层一层向上回溯，因此当搜索到最优解（叶子结点）时，却无法求得该叶子结点对应的最优解中的各个分量。解决方法：对每个扩展结点保存根结点到该结点的路径；在搜索过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。,分支限界法的设计思想,2023/1/17,Branch and Bound Method,23,(c)扩展结点5后(d)扩展结点6 后，最优解为(1,0,1,0)65 图9.3 方法确定0/1背包问题最优解的各分量,3,7,9,2,5,6,7,分支限界法的设计思想,2023/1/17,Branch and Bound Method,24,9.1 概 述,9.1.1 分支限界法的设计思想,9.1.2 分支限界法的时间性能,2023/1/17,Branch and Bound Method,25,与回溯法相同点分支限界法和回溯法实际上都是基于蛮力法，遍历具有指数阶个结点的解空间树在最坏情况下，时间复杂性肯定为指数阶2n或nn与回溯法不同点分支限界法首先扩展解空间树中的上层结点，并用限界函数大范围剪枝根据限界函数不断调整搜索方向，选择最有可能取得最优解的子树优先进行搜索如果选择了结点的合理扩展顺序以及设计好的限界函数，分支界限法可以快速得到问题的解,9.1.2 分支限界法的时间性能,2023/1/17,Branch and Bound Method,26,分支限界法的代价首先，设计一个好的限界函数通常需要花费更多的时间计算相应的目标函数值，而且对于具体的问题实例，通常需要进行大量实验，才能确定一个好的限界函数；其次，分支限界法对解空间树中结点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个扩展结点保存该结点到根结点的路径，或者在搜索过程中构建搜索经过的树结构，这使得算法的设计较为复杂；再次，分支限界法为维护PT 表需要较大的存储空间，在最坏情况下，分支限界法需要的空间复杂性是指数阶。,9.1.2 分支限界法的时间性能,2023/1/17,Branch and Bound Method,27,第9章 分支限界法,9.1 概 述,9.2 图问题中的分支限界法,9.3 组合问题中的分支限界法,9.2 图问题中的分支限界法,9.2.1 TSP问题,9.2.2 多段图的最短路径问题,28,Branch and Bound Method,算法设计与分析,2023/1/17,Branch and Bound Method,29,9.2.1 TSP问题,TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。,C=,3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3,(a)一个无向图(b)无向图的代价矩阵图9.4 无向图及其代价矩阵,2023/1/17,Branch and Bound Method,30,确定上界ub采用贪心法求得近似解为:135421 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.2 TSP问题,2023/1/17,Branch and Bound Method,31,部分解的目标函数值的计算方法假设当前已确定的路径为U=(r1,r2,rk),则：例如图10.4所示无向图，如果部分解包含顶点U=(1,4)，则该部分解的下界是:lb=(2*5+(1+3)+(3+6)+(1+2)+(2+3)/2=16,分支限界法求解TSP问题示例,2023/1/17,Branch and Bound Method,32,TSP问题的搜索过程根结点1，加入表PT，为扩展结点 目标函数:lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14考察孩子结点。结点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中,3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3,2023/1/17,Branch and Bound Method,33,在结点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 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3,2023/1/17,Branch and Bound Method,34,在结点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 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3,2023/1/17,Branch and Bound Method,35,在结点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 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3,2023/1/17,Branch and Bound Method,36,在表PT中选取目标函数值极小的结点10优先进行搜索,处理结点13的孩子。结点14，C1C3 C5C4C2，路径长度为1+2+3+7，目标函数值:lb=(2*13+(3+3)/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问题示例,2023/1/17,Branch and Bound Method,37,分支限界法求解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 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3,2023/1/17,Branch and Bound Method,38,分支限界法求解TSP问题示例,C2,C1,C3,C5,C4,C3,C5,C4,C2,C4,C5,C4,C2,C2,3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3,39,可编辑,2023/1/17,Branch and Bound Method,40,2023/1/17,Branch and Bound Method,41,9.2 TSP问题,9.2 图问题中的分支限界法,9.2.1 TSP问题,9.2.2 多段图的最短路径问题,42,Branch and Bound Method,算法设计与分析,9.2.2 多段图的最短路径问题,设图G=(V,E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集Vi（2kn,1ik），使得E中的任何一条边(u,v)，必有uVi，vVi+m（1ik,1i+mk），则称图G为多段图，称sV1为源点，tVk为终点。,多段图的最短路径问题是求从源点到终点的最小代价路径。,43,Branch and Bound Method,算法设计与分析,对图9.7所示多段图应用贪心法求得近似解为02589，其路径代价为2+7+6+3=18，这可以作为多段图最短路径问题的上界。把每一段最小的代价相加，可以得到一个非常简单的下界，其路径长度为2+4+5+3=14。于是，得到了目标函数的界14,18。由于多段图将顶点划分为k个互不相交的子集，所以，多段图划分为k段，一旦某条路径的一些段被确定后，就可以并入这些信息并计算部分解的目标函数值的下界。一般情况下，对于一个正在生成的路径，假设已经确定了i段（1ik），其路径为(r1,r2,ri,ri+1)，此时，该部分解的目标函数值的计算方法即限界函数如下：,44,Branch and Bound Method,算法设计与分析,应用分支限界法求解图9.7所示多段图的最短路径问题，其搜索空间如图9.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优先进行搜索；,45,Branch and Bound Method,算法设计与分析,（4）在结点5，第2段选择边，目标函数值为lb=3+4+6+3=16，将结点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中最小的，所以它是最优解，搜索结束。,46,Branch and Bound Method,算法设计与分析,47,Branch and Bound Method,算法设计与分析,2023/1/17,Branch and Bound Method,48,第9章 分支限界法,9.1 概 述,9.2 图问题中的分支限界法,9.3 组合问题中的分支限界法,2023/1/17,Branch and Bound Method,49,9.3 组合问题中的分支限界法,9.3.2 任务分配问题,9.3.3 批处理作业调度问题,9.3.1 0/1背包问题,2023/1/17,Branch and Bound Method,50,问题描述 任务分配问题要求把n项任务分配给n个人，每个人完成每项任务的成本不同，要求分配总成本最小的最优分配方案。如图9.10所示是一个任务分配的成本矩阵。,9.3.2 任务分配问题,2023/1/17,Branch and Bound Method,51,如何求最优分配成本的上界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=14 14 是一个更好的上界,9.3.2 任务分配问题,2023/1/17,Branch and Bound Method,52,获得下界Down考虑人员a所有任务的最小代价是2人员b执行所有任务的最小代价是3人员c执行所有任务的最小代价是1人员d执行所有任务的最小代价是4 每行取最小元素，其成本下界：2+3+1+4=10 则上下界为：10,14 注意：这个解并不是一个合法的选择 因为：3、1来自于矩阵同一列，仅给出一个参考下界,9.3.2 任务分配问题,2023/1/17,Branch and Bound Method,53,设当前已对人员1i分配了任务，并且获得了成本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,9 2 7 86 4 3 75 8 1 87 6 9 4,人员a人员b人员c人员d,2023/1/17,Branch and Bound Method,54,图9.11 分支限界法求解任务分配问题示例(表示该结点被丢弃，结点上方的数组表示搜索顺序),C,任务1,任务4,任务2,任务1,任务3,任务4,任务1,任务4,9.3.2 任务分配问题,2023/1/17,Branch and Bound Method,55,搜索过程在结点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,2023/1/17,Branch and Bound Method,56,在结点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 任务分配问题,2023/1/17,Branch and Bound Method,57,在结点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 任务分配问题,2023/1/17,Branch and Bound Method,58,在结点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/1/17,Branch and Bound Method,59,在结点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 任务分配问题,9 2 7 86 4 3 75 8 1 87 6 9 4,任务1 任务2 任务3 任务4,2023/1/17,Branch and Bound Method,60,在结点13 将J2人员a,J1人员b，J3人员c，J4人员d 获得的成本为9+4=13 目标函数值为:lb=13 由于结点13是叶子结点，同时结点13的目标函数值是表PT中的极小值，所以，结点13对应的解即是问题的最优解 搜索结束。构建搜索经过的树结构取出表PT中最小值结点进行扩充时，并将最小值结点存储到ST中，表PT 和表 ST 的数据结构为：(人员i-1分配的任务,lb),9.3.2 任务分配问题,2023/1/17,Branch and Bound Method,61,(人员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)扩展根结点后的状态(b)扩展结点3后的状态,PTSTPTST PTST,(c)扩展结点7后的状态(d)扩展结点6后的状态,(2,14)(3,14)(3,13),PTSTPTST,9.3.2 任务分配问题,2023/1/17,Branch and Bound Method,62,9.3.2 任务分配问题,2023/1/17,Branch and Bound Method,63,9.3.2 任务分配问题,2023/1/17,Branch and Bound Method,64,9.3 组合问题中的分支限界法,9.3.2 任务分配问题,9.3.3 批处理作业调度问题,9.3.1 0/1背包问题,2023/1/17,Branch and Bound Method,65,问题描述n个作业的集合J=J1,J2,Jn，每个作业都有3项任务分别在3台机器上完成Ji 需要机器j 的处理时间为tij（1in,1j3）作业处理顺序:机器1处理机器2处理机器3处理批处理作业调度问题?要求确定这 n 个作业的最优处理顺序使得从第1个作业在机器1上处理开始，到最后一个作业在机器3上处理结束所需的时间最少。最优调度原则使机器1没有空闲时间，且机器2和3的空闲时间最小,9.3.3 批处理作业调度问题,2023/1/17,Branch and Bound Method,66,设 J=J1,J2,J3,J4 是 4 个待处理的作业，每个作业的处理顺序相同:机器1上处理机器2上处理机器3上处理需要的处理时间如下矩阵所示:,9.3.3 批处理作业调度问题,2023/1/17,Branch and Bound Method,67,上界？随机产生几个方案，从中选取最短完成时间为问题的上界。如若处理顺序为: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:2,9.3.3 批处理作业调度问题,上界：41,2023/1/17,Branch and Bound Method,68,批处理作业调度问题的限界函数down理想情况机器1和机器2开始作业后无空闲，最后处理的恰好是在机器3上处理时间最短的作业。例如，以作业 Ji 开始的处理顺序，估算处理所需的最短时间是：tij:表示 Ji 需要机器 j 的处理时间(1in,1j3),9.3.3 批处理作业调度问题,作业Ji在机器1上的处理时间,作业1作业n在机器2上的处理时间总和,在机器3上处理时间最短的作业,2023/1/17,Branch and Bound Method,69,目标函数下界计算lb若已安排了k-1个作业集合，即：M 1,2,k-1，|M|=k-1sum1k-1：机器1完成k-1个作业的处理时间sum2k-1：机器2完成k-1个作业的处理时间现要处理作业k，此时，该部分解的目标函数值的下界lb计算方法如下：（1）sum1k=sum1k-1+tk1（2）（3）sum2k=maxsum1k,sum2k-1+tk2,9.3.3 批处理作业调度问题,2023/1/17,Branch and Bound Method,70,分支限界法搜索过程在根结点 将sum10和sum20分别初始化为0估算目标函数上界为41，加入表PT在结点2 以作业J1开始处理，则sum11=5 目标函数值:lb=5+(7+5+9+8)+2=36,sum21=5+7=12 将结点2加入待处理结点表PT中在结点3 以作业J2开始处理，则 sum11=10 目标函数值:lb=10+(7+5+9+8)+5=44,超过上界41，结点3舍弃。,2023/1/17,Branch and Bound Method,71,图10.15 批处理作业调度问题的示例,作业J1,J4,J3,J2,(1)sum1k=sum1k-1+tk1(2)(3)sum2k=maxsum1k,sum2k-1+tk2,2023/1/17,Branch and Bound Method,72,在结点4，以作业J3开始处理，则sum11=9，目标函数值为9+(7+5+9+8)+2=40，sum21=9+9=18 将结点4加入表PT中在结点5，以作业J4开始处理，则sum11=7，目标函数值为7+(7+5+9+8)+2=38，sum21=7+8=15 将结点5加入表PT中 在表PT中选取目标函数值极小的结点2优先进行搜索在结点6，准备处理作业J1J2，则sum12=5+10=15 目标函数值:lb=max(15,12)+(5+9+8)+5=42,超过上界舍弃；,9.3.3 批处理作业调度问题,2023/1/17,Branch and Bound Method,73,在结点7 准备处理作业J1J3，则sum12=5+9=14 目标函数值：lb=max(14,12)+(5+9+8)+2=38，sum22=max(14,12)+9=23,将结点7加入表PT中在结点8准备处理作业J1J4，则sum12=5+7=12目标函数值:lb=max(12,12)+(5+9+8)+2=36，sum22=max(12,12)+8=20将结点8加入表PT中在表PT中选取目标函数值极小的结点8优先进行搜索,9.3.3 批处理作业调度问题,2023/1/17,Branch and Bound Method,74,在结点9准备处理作业J1J4 J2，则sum13=12+10=22，目标函数值:lb=max(22,20)+(5+9)+5=41，sum23=max(22,20)+5=27将结点9加入表PT中在结点10准备处理作业J1J4 J3，则sum13=12+9=21目标函数:lb=max(21,20)+(5+9)+2=37，sum23=max(21,20)+9=30将结点10加入表PT中在表PT 中选取目标函数值极小的结点10 优先进行搜索,9.3.3 批处理作业调度问题,2023/1/17,Branch and Bound Method,75,在结点11准备处理作业J1J4 J3 J2，则sum14=21+10=31目标函数值为max(31,30)+5+2=38，sum24=max(31,30)+5=36 由于结点11是叶子结点，并且目标函数值在表PT中最小，则结点11代表的解即是问题的最优解，sum24是机器2完成所有4个作业的时间，则机器3完成所有4个作业的时间是:sum24+t23=36+2=38。完成顺序：j1j4j3j2搜索过程结束,9.3.3 批处理作业调度问题,2023/1/17,Branch and Bound Method,76,9.3.3 批处理作业调度问题,77,可编辑,