第六章 分支限界法.ppt

1、1,第6章 分支限界法 Branch and Bound,2,6.1分支限界法的基本思想,Breadth-first search 分支限界法与回溯法 （1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,6.1分支限界法的基本思想,3,分支限界法的搜索策略,在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。 为了有效

2、的选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值，并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解 。,6.1分支限界法的基本思想,4,6.1分支限界法的基本思想,5,分支限界法的基本思想,分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。,此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所

3、有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。,6.1分支限界法的基本思想,6,分枝限界法（branch-and-bound）,分枝限界法的思想是构成一棵树，树的每一层代表某一步的各种走法，某一待求量的各种取值或某一子问题的各种解决方案等，而树的每个终端结点表示每一种可能的最终解答。,7,如果可能的解答数目太多，限于计算机容量和计算时间，不可能构成整个树，则至少构成该树的上面一些层，而将其终端结点标上一定的评价函数，以表示沿其子树进一步进行下去效果的优劣区别。对此树按类似后序遍历的次序进行分析，由每个中间结点的各个子树中挑选出其中最“合

4、适”的一个，或根据子树的评价函数确定该中间结点的评价函数。如此进行下去直至根结点为止，即得到整个问题的解答。下面举几个例子。,8,例1八皇后问题。这是高斯1850年提出的一个著名问题：国际象棋中的“皇后”在横向、直向、和斜向都能走步和吃子，问在88=64格的棋盘上如何能摆上八个皇后而使她们都不能互相吃。现已知此问题共有92种解，但只有12种是独立的，其余的都可以由这12种利用对称性或旋转而得到。,9,为简单起见，以四皇后问题为例讲述此方法。设棋盘有44=16格，每行所摆的皇后都有四种可能的位置，四个皇后共有44=256种摆法。如将这些摆法都列出来再选其中合乎条件的方案，就太费时间了。现构成一个

5、树，根结点的四个子树表示第一行的皇后的四种可能的位置；再下一层表示第二行的位置；。设以F表示失败，S表示成功。如果上面的行已经无法摆了，则下面的行表示失败，下面的行即不必再试，返回上一层再试其它分支。,10,假设第一行的皇后先放在第一列，如图（a）所示，则第二行只有三、四列还可以摆。若暂先试第三列，第三行就完全无法再摆，只好回溯到上一层再试另一个分支，即第二行放第四列。这样第三行还剩第二列可以摆，但第四行又无法再摆了。此时只好返回到最上一层，改试第一行放第二列，。最后构成的树如图2所示，共有两个可行方案，实际上这是两个对称的方案。,11,12,图2,13,因为从所有失败的方案返回时该部分子树即

6、不必保留，所以最终内存中只保留成功方案的几条单链分支，比图中所示之树还要简单。如果每试出一个成功方案就立即输出而不必存储，或只试出一个方案就可以了，则只需一个单链，更可以节约存储量。,14,在用这种方法解决优化问题时（以下以最小化问题来说明，最大化问题也与此类似），如果能事先估计出每个分支的下界值，当某分支的下界值比已试过的方案的值还要高时，这整个子树即不必再考虑，因此常常可以大大节约运算时间。下面再以一个例子说明,15,例2分派问题。这是整数规划问题中的一种特殊问题，现举一个数字例子。设有A、B、C、D四位教师，每人都能教I、II、III、IV四门课程，但各人备各门课所需时间不同，如下表所示

7、,16,现要求每门课有一个人教，且每人只教一门课，问如何分配工作才可以使总备课时间最少。 此问题如果用穷举法需要试4！=24种方案，从中选优，现用分枝限界来解。,17,首先要确定如何定问题的下界。设将每人只教一门课变成一人可以教多门课，这样一来得到的总备课时间最小值肯定不会比实际情况还大，可作为问题的下界。而且在这种假定下最小值的计算非常方便，只需将表中各列的最小值加起来即可。例如整个问题的下界为（A教I、III、IV课，B教II课）2+4+9+7=22。,18,现构成一个树，根结点的四个子树表示I课选谁来教；再下一层表示I课教师选定后剩下的人谁教II课；，如图所示。图中每结点旁的数字为该子问

8、题的下界。如果一个结点有几个子树，则选下界最小的先处理（为什么？），图中结点圆圈中数字表示处理顺序。,19,20,首先计算选择I课教师四种方案子问题的下界。例如若选定A教I课，则B、C、D三人教II、III、IV课的最小值为B教II、IV，D教III课，下界为2+4+13+8=27；若选定B教I课，类似算出下界为41（15+10+9+7=41）；。四方案中以D教I课时的点下界24为最小，故先由此向下进行。教I课的人选择以后，教二课的人有三种方案，类似地算出其下界值，其中又以B教II课的点下界24为最小。再往下进行，教III课的人只有两种，下界分别为28和31。,21,因前三门课的人定了后，第四

9、门课实际上也就定了，故这已是实际所需的时间了。数值为31的点当然应当舍弃，然后回溯到点看另外两个点和，它们的下界均比点的28要大，不必再考虑。然后再向上回溯到点看另外三个分枝，其中点和点的下界均大于28，故都应舍弃，唯有点的下界为27，尚有可考虑的余地。由向下进行，三个方案中点（12）和点（13）的下界均比28为大，当然不必再考虑；点（11）的下界虽然恰好等于28，但这只是下界，实际结果很可能比这还要差，充其量等于此值，故当问题要求只得到一种最好方案就够了时，也不必再向下作下去。这样最后得出以点表示的方案：D-I，B-II，A-III，C-IV，总的时间为28。,22,由此例可以看出，分枝限界

10、法的关键是恰当的选择子问题的下界，使之既要容易计算，又不要距离实际的值太远（例如上述例子中，若下界取得太高就不会有多少好处了。,23,设有A、B、C、D、E5人从事J1、J2、J3、J4、J5 5项工作，他们的效益如图所示，求最佳安排使效益最高。,课堂练习,24,例3巡回推销员问题。设有5座城市，城市间的距离矩阵为：,前面用贪婪算法讨论此问题，现以此为例来说明分枝限界方法的应用。,25,因dij=dji，将矩阵D对角线以上的元素从小到大排列有 d24(1),d13(2),d15(2),d25(3),d45(6),d35(9),d34(9), 由于是5个城市，环绕一圈为5条边，则取距离最小的5条

11、边并求和，得 d13+d24+d15+d25+d45=1+2+2+3+6=14 显然下标中5出现了3次，违背了一顶点不能有三条边相连的约束条件。如果不用d15而用下一条较小的边d35代替，则,26,d13+d24+d25+d45+d35=1+2+3+6+9=21 5依然出现3次。如果保留d15，用下一条较小的边d35代替d25，则 d13+d24+d15+d45+d35=1+2+2+6+9=20 按照深度优先方式搜索下去，现将搜索过程形象地表示如下图,27,28,搜索至第5步时发现 d13+d24+d15+d25+d34=1+2+2+3+9=17 并得一条回路，而且是最佳的回路： v1v3v4

12、v2v5v1 其它路径因不合理或其下界都大于17故没有进一步搜索的价值。所以上述路径便是最佳路径。,29,课堂练习,设有5个城市，他们之间的距离如图所示，分别用贪婪算法和分支限界法求一条旅游回路，使得从某城市出发经过其他的4个城市再返回到出发城市的总距离最短。,a,b,e,c,d,3,7,4,6,5,8,4,3,2,6,30,例4. 同顺序加工任务安排问题 设J1,J2,J3,J4是四项待加工的任务，它们的工序一样，即先在机器m1上加工，然后在机器m2上加工，最后在机器m3上加工，加工时间矩阵是：,31,tij即为任务Ji在机器mj上加工所需时间。如若加顺序是： J2J3J1J4 则从开始到结

13、束所需的时间可计算如下图：,32,图中表示机器空闲等待任务。比如机器m2加工J2于开始后15单位时间结束，但m3加工J3于19单位时间才能完结。所以机器m2于15至19单位时间内空闲着等待任务。加工顺序J2J3J1J4需54单位时间。现在要找一最佳的加工顺序，使完成任务的总时间达到最短。,33,分支限界法的关键在于估计下界，比如从Ji开始的加工顺序，估计加工所需的最短时间为： 即在理想状态下机器m1加工完Ji，机器m2无空闲，最后在机器m3上加工的是任务Jk，其中k满足：,34,即最后在机器m3上加工的任务恰好是机器m3上加工时间最短的任务Jk，当然Jk必须不是最先加工的任务Ji。如是，我们可

14、以得出从任务Ji开始所需加工时间的下界，如下图所示：,35,从图中可见，在这种理想状态下，以J1或J4开始的任务安排完成的时间可能最短。其中从J4开始的任务安排有： 5(7578)436 即完成的时间不可能少于36单位，其余同理类推。 一般从Ji开始，继以Jj的任务安排，理想完成时间应为：,36,JiJjJk的加工顺序所需的加工时间的最低界为：,37,利用分枝限界方法求解的过程如下图,38,图中每个节点都有两个数，其中（）里的数表示搜索顺序的序号。最优的加工顺序是： J1J4J3J2 总时数为38单位，相应安排如下图所示：,39,依估计的时间最短优先搜索为原则，最先找到的最优结果为40单位，若估计的界不小于 38，就无搜索的必要。从图中可知剪去的搜索树枝是非常可观。分支限界的效果是很理想的。,40,综合以上几个例子，可以看到分支限界法的基本思想是采用DFS策略，并对每个结点估计一权值（在求极小值问题中对应于从该结点出发能得到的解的下界，若是最大值问题则反之），在搜索时利用权值来决定下一搜索结点的优先顺序（对于最小值问题，权值越小越优先），一旦搜索到一个解，利用这个解的权值可剪去那些不可能得到更优解的结点，直至所有结点均被搜索或剪去，从而大大节省搜索的结点数。,41,例5 布线问