第15讲 分支定界法

1、理解理解分支限界法分支限界法的剪枝搜索策略。的剪枝搜索策略。掌握分支限界法的掌握分支限界法的算法框架：算法框架： （1）队列式）队列式(FIFO)分支限界法分支限界法 （2）优先队列式分支限界法）优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。通过应用范例学习分支限界法的设计策略。学习要点学习要点分支限界法的基本思想分支限界法与回溯法（1）求解目标求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解所有解，而分支限界法的求解目标则是找出满足约束条件的一个解一个解，或是在满足约束条件的解中找出在某种意义下的最优解某种意义下的最优解。 （2）搜索方式的不同搜索方式的不同：回溯

2、法以深度优先的方式搜索解空间树，而分支限界法则以广度优先广度优先或以最小耗费优最小耗费优先先的方式搜索解空间树。 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 在分支限界法中，每一个活结点活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。分支限界法的基本思想分支限界法的基本思想常见的两种分支限界法（1）队列式队列式(

3、FIFO)(FIFO)分支限界法分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 分支限界法首先确定一个合理的分支限界法首先确定一个合理的限界函数限界函数，并根，并根据限界函数确定据限界函数确定目标函数的界目标函数的界down, up down, up 。然后，按。然后，按照广度优先策略遍历问题的解空间树，在分支结点上，照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子依次搜索该结点的所有孩子结点，分别估算这些孩子结

4、点的目标函数的可能取值。结点的目标函数的可能取值。 如果某孩子结点的如果某孩子结点的目标函数可能取得的值超出目目标函数可能取得的值超出目标函数的界标函数的界，则将其丢弃，因为从这个结点生成的解，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处不会比目前已经得到的解更好；否则，将其加入待处理结点表中。依次从表理结点表中。依次从表PTPT中选取使目标函数的值取得中选取使目标函数的值取得极值的结点成为当前扩展结点，重复上述过程，直到极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。找到最优解。 随着这个遍历过程的不断深入，表随着这个遍历过程的不断深入，表PT中

5、所估算的目中所估算的目标函数的界越来越接近问题的最优解。标函数的界越来越接近问题的最优解。 当搜索到一个叶子结点时当搜索到一个叶子结点时，如果该结点的目标函数，如果该结点的目标函数值是表值是表PT中的极值（对于中的极值（对于最小化问题，是极小值最小化问题，是极小值；对于；对于最大化问题，是极大值最大化问题，是极大值），则该叶子结点对应的解就是），则该叶子结点对应的解就是问题的最优解；否则，根据这个叶子结点调整目标函数问题的最优解；否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表调整下界），依

6、次考察表PT中的结点，将超出目标函数中的结点，将超出目标函数界的结点丢弃，然后从表界的结点丢弃，然后从表PT中选取使目标函数取得极值中选取使目标函数取得极值的结点继续进行扩展。的结点继续进行扩展。单源最短路径问题单源最短路径问题单源最短路径问题1. 问题描述 下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。 2347292235122231333O单源最短路径问题2. 剪枝策略 在算法扩展结点的过程中，一旦发现一个结点的一旦发现一个结点的下界不小于当前找到的最短路长下界不小于当前找到的最短路长，则算法剪去以该

7、结点为根的子树。 在算法中，利用结点间的控制关系结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。 单源最短路径问题3. 算法思想 解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路优先级是结点所对应的当前路长长。 算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆儿子结点被依次插入堆（待处理结点表，以下简称表PT）中。此后，算法从堆中取出具有最小当前具有最小当前路长的结点作为当前扩展结点路长的结点作为当前扩展结点，并依

8、次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。单源最短路径问题1. 问题描述 下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。第1层第2层第4层第5层第3层2347292235122231333O目前的最短路目前的最短路径是径是8，一旦发，一旦发现某个节点的现某个节点的下界不小于这下界不小于这个最短路

9、进，个最短路进，则剪枝。则剪枝。2347292235122231333O利用节点利用节点的控制关的控制关系剪枝系剪枝将会产生将会产生重复的子重复的子树，剪枝树，剪枝 while (true) for (int j = 1; j = n; j+) if (cE.nodejinf)&(E.length+cE.nodejdistj) / 顶点E.node到顶点j可达，且满足控制约束 distj=E.length+cE.nodej; prevj=E.node; / 加入活结点优先队列 MinHeapNode N; N.node=j; /顶点编号为j N.length=distj; H.Insert(N

10、); try H.DeleteMin(E); / 取下一扩展结点 catch (OutOfBounds) break; / 优先队列空顶点顶点i i和和j j间有边，且此路间有边，且此路径长小于原先从原点到径长小于原先从原点到j j的路径长。的路径长。这个判断，实现了剪枝这个判断，实现了剪枝dist:最短距离数组最短距离数组prev: 前驱顶点数组前驱顶点数组E：当前的扩展节点：当前的扩展节点c: 邻接矩阵邻接矩阵H： 活节点优先队列活节点优先队列记载最短路径 缺乏上界缺乏上界函数减枝函数减枝优先权队列优先权队列 VS. 先进先出队列先进先出队列0/10/1背包问题背包问题 0/1 0/1背包

11、问题。假设有背包问题。假设有4 4个物品，其重量分别为个物品，其重量分别为(4, 7, 5, (4, 7, 5, 3)3)，价值分别为，价值分别为(40, 42, 25, 12)(40, 42, 25, 12)，背包容量，背包容量W=10W=10。首先，。首先，将给定物品按单位重量价值从大到小排序，结果如下：将给定物品按单位重量价值从大到小排序，结果如下：物品物品重量重量(w)价值价值(v)价值价值/重量重量(v/w)144010274263525543124 应用贪心法求得近似解为应用贪心法求得近似解为(1, 0, 0, 0)(1, 0, 0, 0)，获得的价，获得的价值为值为4040，这可

12、以作为，这可以作为0/10/1背包问题的下界背包问题的下界。 如何求得如何求得0/10/1背包问题的一个合理的上界呢？考虑最背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第好情况，背包中装入的全部是第1 1个物品且可以将背包个物品且可以将背包装满，则可以得到一个非常简单的上界的计算方法：装满，则可以得到一个非常简单的上界的计算方法：ubub= =W W( (v v1 1/ /w w1 1)=10)=1010=10010=100。于是，得到了目标函数的。于是，得到了目标函数的界界40, 10040, 100。 限界函数为：限界函数为： )()(11iiwvwWvubw=0, v=0

13、ub=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=65234567891分支限界法求解分支限界法求解0/10/1背包问题背包问题 分支限界法求解分支限界法求解0/10/1背包问题，具体的搜索过程如下：背包问题，具体的搜索过程如下：（1 1）在根结点）在根结点1 1，没有将任何物品装入背包，因此，背包，没有将任何物品装入背包，因此，背包的重量和获得的价值均为的重量和获得的价值均为0 0，根据限界函数计算结点，根据限界函数计算结点1 1

14、的目的目标函数值为标函数值为101010=10010=100；（2 2）在结点）在结点2 2，将物品，将物品1 1装入背包，因此，背包的重量为装入背包，因此，背包的重量为4 4，获得的价值为获得的价值为4040，目标函数值为，目标函数值为40 + (10-4)40 + (10-4)6=766=76，将将结点结点2 2加入待处理结点表加入待处理结点表PTPT中中；在结点；在结点3 3，没有将物品，没有将物品1 1装入装入背包，因此，背包的重量和获得的价值仍为背包，因此，背包的重量和获得的价值仍为0 0，目标函数值，目标函数值为为10106 66060，将结点将结点3 3加入表加入表PTPT中中；

15、（3 3）在表）在表PTPT中选取中选取目标函数值取得极大的结点目标函数值取得极大的结点2 2优先进行优先进行搜索搜索； （4 4）在结点）在结点4 4，将物品，将物品2 2装入背包，因此，背包的重量为装入背包，因此，背包的重量为1111，不满足约束条件，将结点，不满足约束条件，将结点4 4丢弃；在结点丢弃；在结点5 5，没有将，没有将物物品品2 2装入背包，因此，背包的重量和获得的价值与结点装入背包，因此，背包的重量和获得的价值与结点2 2相相同，目标函数值为同，目标函数值为40 + (10-4)40 + (10-4)5=705=70，将结点，将结点5 5加入表加入表PTPT中；中；（5 5

16、）在表）在表PTPT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点5 5优先进行优先进行搜索搜索；（6 6）在结点）在结点6 6，将物品，将物品3 3装入背包，因此，背包的重量为装入背包，因此，背包的重量为9 9，获得的价值为获得的价值为6565，目标函数值为，目标函数值为65 + (10-9)65 + (10-9)4=694=69，将，将结点结点6 6加入表加入表PTPT中；在结点中；在结点7 7，没有将物品，没有将物品3 3装入背包，因装入背包，因此，背包的重量和获得的价值与结点此，背包的重量和获得的价值与结点5 5相同，目标函数值相同，目标函数值为为40 + (10-4)4

17、0 + (10-4)4 46464，将结点，将结点6 6加入表加入表PTPT中；中；（7 7）在表）在表PTPT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点6 6优先进行优先进行搜索；搜索；（8 8）在结点）在结点8 8，将物品，将物品4 4装入背包，因此，背包的重量为装入背包，因此，背包的重量为1212，不满足约束条件，将结点不满足约束条件，将结点8 8丢弃；在结点丢弃；在结点9 9，没有将物品，没有将物品4 4装装入背包，因此，背包的重量和获得的价值与结点入背包，因此，背包的重量和获得的价值与结点6 6相同，相同，目目标函数值为标函数值为6565；（9 9）由于结点由于结点

18、9 9是叶子结点，同时结点是叶子结点，同时结点9 9的目标函数值是表的目标函数值是表PTPT中的极大值，所以，结点中的极大值，所以，结点9 9对应的解即是问题的最优解，对应的解即是问题的最优解，搜索结束搜索结束。分支限界法的时间性能分支限界法的时间性能 分支限界法分支限界法和和回溯法回溯法实际上都属于穷举法，当然不能实际上都属于穷举法，当然不能指望它有很好的最坏时间复杂性，遍历具有指数阶个结点指望它有很好的最坏时间复杂性，遍历具有指数阶个结点的解空间树，在最坏情况下，时间复杂性肯定为指数阶。的解空间树，在最坏情况下，时间复杂性肯定为指数阶。 与回溯法不同的是，分支限界法首先扩展解空间树中与回溯

19、法不同的是，分支限界法首先扩展解空间树中的上层结点，并采用限界函数，的上层结点，并采用限界函数，有利于实行大范围剪枝有利于实行大范围剪枝，同时，同时，根据限界函数不断调整搜索方向，选择最有可能取根据限界函数不断调整搜索方向，选择最有可能取得最优解的子树优先进行搜索得最优解的子树优先进行搜索。所以，如果选择了结点的。所以，如果选择了结点的合理扩展顺序以及设计了一个好的限界函数，分支界限法合理扩展顺序以及设计了一个好的限界函数，分支界限法可以快速得到问题的解。可以快速得到问题的解。 分支限界法的较高效率是以付出一定代价为基础的，其分支限界法的较高效率是以付出一定代价为基础的，其工作方式也造成了算法

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

21、应的最优解中的各个分量，需要对每个扩展结点保存该结点到根结点的路径，或者在搜索过程中构建展结点保存该结点到根结点的路径，或者在搜索过程中构建搜索经过的树结构，这使得算法的设计较为复杂；搜索经过的树结构，这使得算法的设计较为复杂； 再次，算法要再次，算法要维护一个待处理结点表维护一个待处理结点表PTPT，并且需要，并且需要在表在表PTPT中快速查找取得极值的结点中快速查找取得极值的结点，等等。这都需要较，等等。这都需要较大的存储空间，大的存储空间，在最坏情况下，分支限界法需要的空间在最坏情况下，分支限界法需要的空间复杂性是指数阶复杂性是指数阶。 任务分配问题任务分配问题 任务分配问题要求把任务分

22、配问题要求把n n项任务分配给项任务分配给n n个人，每个人，每个人完成每项任务的成本不同，要求分配总成本最个人完成每项任务的成本不同，要求分配总成本最小的最优分配方案。如下图所示是一个任务分配的小的最优分配方案。如下图所示是一个任务分配的成本矩阵。成本矩阵。 C9 2 7 86 4 3 75 8 1 87 6 9 4 任务任务1 任务任务2 任务任务3 任务任务4人员人员a人员人员b人员人员c人员人员d 任务分配问题的成本矩阵任务分配问题的成本矩阵求最优分配成本的上界和下界求最优分配成本的上界和下界 考虑任意一个可行解，例如矩阵中的对角线是一个考虑任意一个可行解，例如矩阵中的对角线是一个合法

23、的选择，表示将任务合法的选择，表示将任务1 1分配给人员分配给人员a a、任务、任务2 2分配给分配给人员人员b b、任务、任务3 3分配给人员分配给人员c c、任务、任务4 4分配给人员分配给人员d d，其成，其成本是本是9+4+1+4=189+4+1+4=18；或者应用贪心法求得一个近似解：将；或者应用贪心法求得一个近似解：将任务任务2 2分配给人员分配给人员a a、任务、任务3 3分配给人员分配给人员b b、任务、任务1 1分配给分配给人员人员c c、任务、任务4 4分配给人员分配给人员d d，其成本是，其成本是2+3+5+4=142+3+5+4=14。显然，显然，1414是一个更好的上

24、界。为了获得下界，考虑人员是一个更好的上界。为了获得下界，考虑人员a a执行所有任务的最小代价是执行所有任务的最小代价是2 2，人员，人员b b执行所有任务的执行所有任务的最小代价是最小代价是3 3，人员，人员c c执行所有任务的最小代价是执行所有任务的最小代价是1 1，人，人员员d d执行所有任务的最小代价是执行所有任务的最小代价是4 4。因此，将每一行的最。因此，将每一行的最小元素加起来就得到解的下界，其成本是小元素加起来就得到解的下界，其成本是2+3+1+4=102+3+1+4=10。需要强调的是，这个解并不是一个合法的选择（需要强调的是，这个解并不是一个合法的选择（3 3和和1 1来来

25、自于矩阵的同一列），它仅仅给出了一个参考下界，这自于矩阵的同一列），它仅仅给出了一个参考下界，这样，样，最优值一定是最优值一定是10, 1410, 14之间的某个值之间的某个值。设当前已对人员设当前已对人员1 1i i分配了任务，并且获得了成本分配了任务，并且获得了成本v v，则限界函数可以定义为：，则限界函数可以定义为：nikkvlb1行的最小值第 （2 2）在结点）在结点2 2，将任务，将任务1 1分配给人员分配给人员a a，获得的成本为，获得的成本为9 9，目标，目标函数值为函数值为9 + (3+1+4)=179 + (3+1+4)=17，超出目标函数的界，超出目标函数的界10, 141

26、0, 14，将结将结点点2 2丢弃丢弃；在结点；在结点3 3，将任务，将任务2 2分配给人员分配给人员a a，获得的成本为，获得的成本为2 2，目标函数值为目标函数值为2 + (3+1+4)=102 + (3+1+4)=10，将结点，将结点3 3加入待处理结点表加入待处理结点表PTPT中；在结点中；在结点4 4，将任务，将任务3 3分配给人员分配给人员a a，获得的成本为，获得的成本为7 7，目标函，目标函数值为数值为7 + (3+1+4)=157 + (3+1+4)=15，超出目标函数的界，超出目标函数的界10, 1410, 14，将结点，将结点4 4丢弃；在结点丢弃；在结点5 5，将任务，

27、将任务4 4分配给人员分配给人员a a，获得的成本为，获得的成本为8 8，目，目标函数值为标函数值为8 + (3+1+4)=168 + (3+1+4)=16，超出目标函数的界，超出目标函数的界10, 1410, 14，将，将结点结点5 5丢弃；丢弃；应用分支限界法求解任务分配问题，具体的搜索过程如下：应用分支限界法求解任务分配问题，具体的搜索过程如下：（1 1）在根结点）在根结点1 1，没有分配任务，根据限界函数估算目标函，没有分配任务，根据限界函数估算目标函数值为数值为2+3+1+4=102+3+1+4=10； （3 3）在表）在表PTPT中选取目标函数值极小的结点中选取目标函数值极小的结点

28、3 3优先进行搜索；优先进行搜索；（4 4）在结点）在结点6 6，将任务，将任务1 1分配给人员分配给人员b b，获得的成本为，获得的成本为2+6=82+6=8，目标函数值为目标函数值为8+(1+4)8+(1+4)1313，将结点，将结点6 6加入表加入表PTPT中；在结点中；在结点7 7，将任务将任务3 3分配给人员分配给人员b b，获得的成本为，获得的成本为2+3=52+3=5，目标函数值为，目标函数值为5+(1+4)5+(1+4)1010，将结点，将结点7 7加入表加入表PTPT中；在结点中；在结点8 8。将任务。将任务4 4分配给分配给人员人员b b，获得的成本为，获得的成本为2+7=

29、92+7=9，目标函数值为，目标函数值为9+(1+4)9+(1+4)1414，将，将结点结点8 8加入表加入表PTPT中；中； （5 5）在表在表PTPT中选取目标函数值极小的结点中选取目标函数值极小的结点7 7优先进行搜索优先进行搜索；（6 6）在结点）在结点9 9，将任务，将任务1 1分配给人员分配给人员c c，获得的成本为，获得的成本为5+5=105+5=10，目标函数值为目标函数值为10+4=1410+4=14，将结点，将结点9 9加入表加入表PTPT中；在结点中；在结点1010，将任，将任务务4 4分配给人员分配给人员c c，获得的成本为，获得的成本为5+8=135+8=13，目标函

30、数值为，目标函数值为13+4=1713+4=17，超出目标函数的界，超出目标函数的界10, 1410, 14，将结点，将结点1010丢弃；丢弃；（7）在表）在表PT中选取目标函数值极小的结点中选取目标函数值极小的结点6优先进行搜索；优先进行搜索；（8）在结点）在结点11，将任务，将任务3分配给人员分配给人员c，获得的成本为，获得的成本为8+1=9，目标函数值为目标函数值为9+4=13，将结点，将结点11加入表加入表PT中；在结点中；在结点12，将，将任务任务4分配给人员分配给人员c，获得的成本为，获得的成本为8+8=16，目标函数值为，目标函数值为16+4=20，超出目标函数的界，超出目标函数

31、的界10, 14，将结点，将结点12丢弃；丢弃；（9 9）在表）在表PTPT中选取目标函数值极小的结点中选取目标函数值极小的结点1111优先进行搜索；优先进行搜索；（1010）在结点）在结点1313，将任务，将任务4 4分配给人员分配给人员d d，获得的成本为，获得的成本为9+4=139+4=13，目标函数值为，目标函数值为1313，由于结点，由于结点1313是叶子结点，同时结是叶子结点，同时结点点1313的目标函数值是表的目标函数值是表PTPT中的极小值，所以，结点中的极小值，所以，结点1313对应的对应的解即是问题的最优解，搜索结束。解即是问题的最优解，搜索结束。4alb=16104sta

32、rtlb=101alb=172alb=103alb=151blb=133blb=104blb=141clb=144clb=174clb=173clb=134dlb=13分支限界法求解任务分配问题示例分支限界法求解任务分配问题示例(表示该结点被丢弃，结点上方的数组表示搜索顺序表示该结点被丢弃，结点上方的数组表示搜索顺序)23567891213111 为了在搜索过程中构建搜索经过的树结构，设一个表为了在搜索过程中构建搜索经过的树结构，设一个表ST，在表，在表PT中取出最小值结点进行扩充时，将最小值结点中取出最小值结点进行扩充时，将最小值结点存储到表存储到表ST中，表中，表PT和表和表ST的数据结构

33、为的数据结构为(人员人员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 PT (c) 扩展结点扩展结

34、点7后的状态后的状态 (d) 扩展结点扩展结点6后的状态后的状态(2,14) (3,14) (3,13)PTSTPTST ST 回溯过程是：(3,13)(1,13)(2,13)(0,10) 。算法算法 任务分配问题任务分配问题 1根据限界函数计算目标函数的下界根据限界函数计算目标函数的下界down；采用贪心法得到上界；采用贪心法得到上界up； 2将待处理结点表将待处理结点表PT初始化为空；初始化为空； 3for (i=1; i=1) 5.1 xk=1; 5.2 while (xk=n) 5.2.1 如果人员如果人员k分配任务分配任务xk不发生冲突，则不发生冲突，则 5.2.1.1 根据式根据式9.4计算目标函数值计算目标函数值lb; 5.2.1.2 若若lb=up，则将，则将i,lb存储在表存储在表PT中；中； 5.2.2 xk=xk+1; 5.