《第六章 分支限界法.ppt》由会员分享，可在线阅读，更多相关《第六章 分支限界法.ppt（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第6章 分支限界法 Branch and Bound 16.1 分支限界法的基本思想分支限界法的基本思想nBreadth-first search n分支限界法与回溯法分支限界法与回溯法（1）求解目标求解目标：回溯法的求解目标是找出解空间树：回溯法的求解目标是找出解空间树中满足约束条件的中满足约束条件的所有解所有解所有解所有解，而分支限界法的求解，而分支限界法的求解目标则是找出满足约束条件的目标则是找出满足约束条件的一个解一个解一个解一个解，或是在满，或是在满足约束条件的解中找出在某种意义下的足约束条件的解中找出在某种意义下的最优解最优解最优解最优解。（2）搜索方式的不同搜索方式的不同：回溯法
2、以：回溯法以深度优先的方式深度优先的方式深度优先的方式深度优先的方式搜搜索解空间树，而分支限界法则以索解空间树，而分支限界法则以广度优先或以最广度优先或以最广度优先或以最广度优先或以最小耗费优先的方式小耗费优先的方式小耗费优先的方式小耗费优先的方式搜索解空间树。搜索解空间树。6.1分支限界法的基本思想分支限界法的基本思想2分支限界法的搜索策略分支限界法的搜索策略在扩展结点处，先生成其所有的儿子结点（分支），在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。然后再从当前的活结点表中选择下一个扩展结点。为了有效的选择下一扩展结点，以加速搜索的进程，为了有效的
3、选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值，并根据这些已在每一活结点处，计算一个函数值，并根据这些已计算出的函数值，从当前活结点表中选择一个最有计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解最优解的分支推进，以便尽快地找出一个最优解。6.1分支限界法的基本思想分支限界法的基本思想36.1分支限界法的基本思想分支限界法的基本思想4分支限界法的基本思想分支限界法的基本思想 分支限界法常以广度优先或以最小耗费（最大效益）分支限界法常以广度优先或以最小
4、耗费（最大效益）优先的方式搜索问题的解空间树。优先的方式搜索问题的解空间树。此后，从活结点表中取下一结点成为当前扩展结此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或续到找到所需的解或活结点表为空时为止活结点表为空时为止。在分支限界法中，每一个活结点在分支限界法中，每一个活结点只有一次机会只有一次机会成成为扩展结点。活结点一旦成为扩展结点，就为扩展结点。活结点一旦成为扩展结点，就一次一次性产生其所有儿子结点性产生其所有儿子结点。在这些儿子结点中，导。在这些儿子结点中，导致不可行解或导致非最优解的儿子
5、结点被舍弃，致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。其余儿子结点被加入活结点表中。6.1分支限界法的基本思想分支限界法的基本思想5分枝限界法（分枝限界法（branch-and-bound）分枝限界法的思想是构成一棵树，树的每一层代表某一步的各种走法，某一待求量的各种取值或某一子问题的各种解决方案等，而树的每个终端结点表示每一种可能的最终解答。6 如果可能的解答数目太多，限于计算机容量和计算时间，不可能构成整个树，则至少构成该树的上面一些层，而将其终端结点标上一定的评价函数，以表示沿其子树进一步进行下去效果的优劣区别。对此树按类似后序遍历的次序进行分析，由每个中间
6、结点的各个子树中挑选出其中最“合适”的一个，或根据子树的评价函数确定该中间结点的评价函数。如此进行下去直至根结点为止，即得到整个问题的解答。下面举几个例子。7例1八皇后问题。这是高斯1850年提出的一个著名问题：国际象棋中的“皇后”在横向、直向、和斜向都能走步和吃子，问在88=64格的棋盘上如何能摆上八个皇后而使她们都不能互相吃。现已知此问题共有92种解，但只有12种是独立的，其余的都可以由这12种利用对称性或旋转而得到。8为简单起见，以四皇后问题为例讲述此方法。设棋盘有44=16格，每行所摆的皇后都有四种可能的位置，四个皇后共有44=256种摆法。如将这些摆法都列出来再选其中合乎条件的方案，
7、就太费时间了。现构成一个树，根结点的四个子树表示第一行的皇后的四种可能的位置；再下一层表示第二行的位置；。设以F表示失败，S表示成功。如果上面的行已经无法摆了，则下面的行表示失败，下面的行即不必再试，返回上一层再试其它分支。9假设第一行的皇后先放在第一列，如图（a）所示，则第二行只有三、四列还可以摆。若暂先试第三列，第三行就完全无法再摆，只好回溯到上一层再试另一个分支，即第二行放第四列。这样第三行还剩第二列可以摆，但第四行又无法再摆了。此时只好返回到最上一层，改试第一行放第二列，。最后构成的树如图2所示，共有两个可行方案，实际上这是两个对称的方案。1011图212因为从所有失败的方案返回时该部
8、分子树即不必保留，所以最终内存中只保留成功方案的几条单链分支，比图中所示之树还要简单。如果每试出一个成功方案就立即输出而不必存储，或只试出一个方案就可以了，则只需一个单链，更可以节约存储量。13在用这种方法解决优化问题时（以下以最小化问题来说明，最大化问题也与此类似），如果能事先估计出每个分支的下界值，当某分支的下界值比已试过的方案的值还要高时，这整个子树即不必再考虑，因此常常可以大大节约运算时间。下面再以一个例子说明14例2分派问题。这是整数规划问题中的一种特殊问题，现举一个数字例子。设有A、B、C、D四位教师，每人都能教I、II、III、IV四门课程，但各人备各门课所需时间不同，如下表所示
9、15 现要求每门课有一个人教，且每人只教一门课，问如何分配工作才可以使总备课时间最少。此问题如果用穷举法需要试4！=24种方案，从中选优，现用分枝限界来解。16 首先要确定如何定问题的下界。设将每人只教一门课变成一人可以教多门课，这样一来得到的总备课时间最小值肯定不会比实际情况还大，可作为问题的下界。而且在这种假定下最小值的计算非常方便，只需将表中各列的最小值加起来即可。例如整个问题的下界为（A教I、III、IV课，B教II课）2+4+9+7=22。17 现构成一个树，根结点的四个子树表示I课选谁来教；再下一层表示I课教师选定后剩下的人谁教II课；，如图所示。图中每结点旁的数字为该子问题的下界
10、。如果一个结点有几个子树，则选下界最小的先处理（为什么？），图中结点圆圈中数字表示处理顺序。1819 首先计算选择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。20因前三门课的人定了后，第四门课实际上也就定
11、了，故这已是实际所需的时间了。数值为31的点当然应当舍弃，然后回溯到点看另外两个点和，它们的下界均比点的28要大，不必再考虑。然后再向上回溯到点看另外三个分枝，其中点和点的下界均大于28，故都应舍弃，唯有点的下界为27，尚有可考虑的余地。由向下进行，三个方案中点（12）和点（13）的下界均比28为大，当然不必再考虑；点（11）的下界虽然恰好等于28，但这只是下界，实际结果很可能比这还要差，充其量等于此值，故当问题要求只得到一种最好方案就够了时，也不必再向下作下去。这样最后得出以点表示的方案：D-I，B-II，A-III，C-IV，总的时间为28。21由此例可以看出，分枝限界法的关键是恰当的选择
12、子问题的下界，使之既要容易计算，又不要距离实际的值太远（例如上述例子中，若下界取得太高就不会有多少好处了。22n设有A、B、C、D、E5人从事J1、J2、J3、J4、J5 5项工作，他们的效益如图所示，求最佳安排使效益最高。J1J2J3J4J5A10 1110 47B13 10 10 85C59774D15 12 10 115E10 11884课堂练习23例3巡回推销员问题。设有5座城市，城市间的距离矩阵为：前面用贪婪算法讨论此问题，现以此为例来说明分枝限界方法的应用。24因dij=dji，将矩阵D对角线以上的元素从小到大排列有d24(1),d13(2),d15(2),d25(3),d45(6
13、),d35(9),d34(9),由于是5个城市，环绕一圈为5条边，则取距离最小的5条边并求和，得d13+d24+d15+d25+d45=1+2+2+3+6=14显然下标中5出现了3次，违背了一顶点不能有三条边相连的约束条件。如果不用d15而用下一条较小的边d35代替，则25d13+d24+d25+d45+d35=1+2+3+6+9=215依然出现3次。如果保留d15，用下一条较小的边d35代替d25，则d13+d24+d15+d45+d35=1+2+2+6+9=20按照深度优先方式搜索下去，现将搜索过程形象地表示如下图2627搜索至第5步时发现d13+d24+d15+d25+d34=1+2+2
14、+3+9=17并得一条回路，而且是最佳的回路：v1v3v4v2v5v1其它路径因不合理或其下界都大于17故没有进一步搜索的价值。所以上述路径便是最佳路径。28课堂练习n设有5个城市，他们之间的距离如图所示，分别用贪婪算法和分支限界法求一条旅游回路，使得从某城市出发经过其他的4个城市再返回到出发城市的总距离最短。abecd374658432629例4.同顺序加工任务安排问题设J1,J2,J3,J4是四项待加工的任务，它们的工序一样，即先在机器m1上加工，然后在机器m2上加工，最后在机器m3上加工，加工时间矩阵是：30tij即为任务Ji在机器mj上加工所需时间。如若加顺序是：J2J3J1J4则从开
15、始到结束所需的时间可计算如下图：31 图中表示机器空闲等待任务。比如机器m2加工J2于开始后15单位时间结束，但m3加工J3于19单位时间才能完结。所以机器m2于15至19单位时间内空闲着等待任务。加工顺序J2J3J1J4需54单位时间。现在要找一最佳的加工顺序，使完成任务的总时间达到最短。32分支限界法的关键在于估计下界，比如从Ji开始的加工顺序，估计加工所需的最短时间为：即在理想状态下机器m1加工完Ji，机器m2无空闲，最后在机器m3上加工的是任务Jk，其中k满足：33即最后在机器m3上加工的任务恰好是机器m3上加工时间最短的任务Jk，当然Jk必须不是最先加工的任务Ji。如是，我们可以得出
16、从任务Ji开始所需加工时间的下界，如下图所示：34从图中可见，在这种理想状态下，以J1或J4开始的任务安排完成的时间可能最短。其中从J4开始的任务安排有：5(7578)436即完成的时间不可能少于36单位，其余同理类推。一般从Ji开始，继以Jj的任务安排，理想完成时间应为：35JiJjJk的加工顺序所需的加工时间的最低界为：36利用分枝限界方法求解的过程如下图37图中每个节点都有两个数，其中（）里的数表示搜索顺序的序号。最优的加工顺序是：J1J4J3J2总时数为38单位，相应安排如下图所示：38依估计的时间最短优先搜索为原则，最先找到的最优结果为40单位，若估计的界不小于 38，就无搜索的必要
17、。从图中可知剪去的搜索树枝是非常可观。分支限界的效果是很理想的。39 综合以上几个例子，可以看到分支限界法的基本思想是采用DFS策略，并对每个结点估计一权值（在求极小值问题中对应于从该结点出发能得到的解的下界，若是最大值问题则反之），在搜索时利用权值来决定下一搜索结点的优先顺序（对于最小值问题，权值越小越优先），一旦搜索到一个解，利用这个解的权值可剪去那些不可能得到更优解的结点，直至所有结点均被搜索或剪去，从而大大节省搜索的结点数。40例5 布线问题n印刷电路板将布线区域划分为nm个方格阵列n精确的电路板布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。n布线时电路只能沿直线或直角布线。n为避免线路相交，已布线方格做上封闭标记，其他线路布线不允许穿过封闭区域。41ab4211a11b432211a12212b24432211a12212b234532211a12212b2344632211a12212b23454732211a12212b2345664832211a12212b234567674932211a12212b2348567867850 分支限界法可应用于大量组合优化问题。其关键技术在于各节点权值如何估计，可以说，一个分支限界求解方法的效率基本上由定界方法所决定，若界估计不好，在极端情况下将与穷举搜索没有区别。51