《内蒙古大学《算法与数据结构》讲义17分枝定界》由会员分享，可在线阅读，更多相关《内蒙古大学《算法与数据结构》讲义17分枝定界（20页珍藏版）》请在金锄头文库上搜索。
1、下载第1 7章分 枝 定 界任何美好的事情都有结束的时候。现在我们学习的是本书的最后一章。幸运的是，本章用到的大部分概念在前面各章中已作了介绍。类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间（常用的树结构是第 1 6章所介绍的子集树和排列树） 。然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。本章与第1 6章所考察的应用完全相同，因此，可以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。17.1 算法思想分枝定界（branch a
2、nd bound）是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成 E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法） ：1) 先进先出（F I F O）即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活节点表的性质与队列相同。2) 最
3、小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个 E-节点就是具有最小耗费的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个 E-节点是具有最大收益的活节点。例17-1 迷宫老鼠 考察图16-3a 给出的迷宫老鼠例子和图1 6 - 1的解空间结构。使用F I F O分枝定界，初始时取（1，1）作为E-节点且活动队列为空。迷宫的位置（1 , 1）被置为1，以免再次返回到这个位置。 （1，1）被扩充，它的相邻节点（ 1，2）和（2，1）加入到队列中（即活节点表） 。为避免再次回到这两个位置
4、，将位置（ 1，2）和（2，1）置为1。此时迷宫如图1 7 - 1 a所示，E-节点（1，1）被删除。1 1 01 1 1 1 1 11 1 11 1 11 1 10 0 00 0 01 0 0a）b）c）图17-1 迷宫问题的F I F O分枝定界方法节点（1，2）从队列中移出并被扩充。检查它的三个相邻节点（见图1 6 - 1的解空间） ，只有（1，3）是可行的移动（剩余的两个节点是障碍节点） ，将其加入队列，并把相应的迷宫位置置为1，所得到的迷宫状态如图17-1b 所示。节点（1，2）被删除，而下一个E-节点（2，1）将会被取出，当此节点被展开时，节点（3，1）被加入队列中，节点（3，1）
5、被置为1，节点（2，1）被删除，所得到的迷宫如图17-1c 所示。此时队列中包含（1，3）和（3，1）两个节点。随后节点（1，3）变成下一个E-节点，由于此节点不能到达任何新的节点，所以此节点即被删除，节点（3，1）成为新的E-节点，将队列清空。节点（3，1）展开， （3，2）被加入队列中，而（3，1）被删除。 （3，2）变为新的E-节点，展开此节点后，到达节点（3，3） ，即迷宫的出口。使用F I F O搜索，总能找出从迷宫入口到出口的最短路径。需要注意的是：利用回溯法找到的路径却不一定是最短路径。有趣的是，程序 6 - 11已经给出了利用F I F O分枝定界搜索从迷宫的（1，1）位置到（
6、n，n) 位置的最短路径的代码。例17-2 0/1背包问题 下面比较分别利用F I F O分枝定界和最大收益分枝定界方法来解决如下背包问题：n=3, w=20,15,15, p=40,25,25, c= 3 0。F I F O分枝定界利用一个队列来记录活节点，节点将按照F I F O顺序从队列中取出；而最大收益分枝定界使用一个最大堆，其中的 E-节点按照每个活节点收益值的降序，或是按照活节点任意子树的叶节点所能获得的收益估计值的降序从队列中取出。本例所使用的背包问题与例1 6 . 2相同，并且有相同的解空间树。使用F I F O分枝定界法搜索，初始时以根节点A作为E-节点，此时活节点队列为空。
7、当节点A展开时，生成了节点B和C，由于这两个节点都是可行的，因此都被加入活节点队列中，节点A被删除。下一个E-节点是B，展开它并产生了节点 D和E，D是不可行的，被删除，而 E被加入队列中。下一步节点 C成为E-节点，它展开后生成节点 F和G，两者都是可行节点，加入队列中。下一个E-节点E生成节点J和K，J不可行而被删除，K是一个可行的叶节点，并产生一个到目前为止可行的解，它的收益值为4 0。下一个E-节点是F，它产生两个孩子L、M，L代表一个可行的解且其收益值为5 0，M代表另一个收益值为1 5的可行解。G是最后一个E-节点，它的孩子N和O都是可行的。由于活节点队列变为空，因此搜索过程终止，
8、最佳解的收益值为5 0。可以看到，工作在解空间树上的 F I F O分枝定界方法非常象从根节点出发的宽度优先搜索。它们的主要区别是在F I F O分枝定界中不可行的节点不会被搜索。最大收益分枝定界算法以解空间树中的节点A作为初始节点。 展开初始节点得到节点B和C，两者都是可行的并被插入堆中，节点B获得的收益值是4 0（设x1 = 1） ，而节点C得到的收益值为0。A被删除，B成为下一个E-节点，因为它的收益值比 C的大。当展开B时得到了节点D和E，D是不可行的而被删除，E加入堆中。由于E具有收益值4 0，而C为0，因为E成为下一个E-节点。展开E时生成节点J和K，J不可行而被删除，K是一个可行
9、的解，因此K为作为目前能找到的最优解而记录下来，然后K被删除。由于只剩下一个活节点C在堆中，因此C作为E-节点被展开，生成F、G两个节点插入堆中。F的收益值为2 5，因此成为下一个E-节点，展开后得到节点L和M，但L、M都被删除，因为它们是叶节点，同时L所对应的解被作为当前最优解记录下来。最终，G成为E-节点，生成的节点为 N和O，两者都是叶节点而被删除，两者所对应的解都不比当前的最优解更好，因此最优解保持不变。此时堆变为空，没有下一个 E-节点产生，搜索过程终止。终止于J的搜索即为最优解。犹如在回溯方法中一样，可利用一个定界函数来加速最优解的搜索过程。定界函数为最大收益设置了一个上限，通过展
10、开一个特殊的节点可能获得这个最大收益。如果一个节点的定界第1 7章分 枝 定 界5 1 7下载函数值不大于目前最优解的收益值，则此节点会被删除而不作展开，更进一步，在最大收益分枝定界方法中，可以使节点按照它们收益的定界函数值的非升序从堆中取出，而不是按照节点的实际收益值来取出。这种策略从可能到达一个好的叶节点的活节点出发，而不是从目前具有较大收益值的节点出发。例17-3 旅行商问题 对于图1 6 - 4的四城市旅行商问题，其对应的解空间为图1 6 - 5所示的排列树。F I F O分枝定界使用节点B作为初始的E-节点，活节点队列初始为空。当B展开时，生成节点C、D和E。由于从顶点1到顶点2，3
11、，4都有边相连，所以C、D、E三个节点都是可行的并加入队列中。当前的E-节点B被删除，新的E-节点是队列中的第一个节点，即节点 C。因为在图1 6 - 4中存在从顶点2到顶点3和4的边，因此展开C，生成节点F和G，两者都被加入队列。下一步，D成为E-节点，接着又是E，到目前为止活节点队列中包含节点F到K。下一个E-节点是F，展开它得到了叶节点 L。至此找到了一个旅行路径，它的开销是 5 9。展开下一个E-节点G，得到叶节点M，它对应于一个开销为6 6的旅行路径。接着H成为E-节点，从而找到叶节点N，对应开销为2 5的旅行路径。下一个E-节点是I，它对应的部分旅行1 - 3 - 4的开销已经为2
12、 6，超过了目前最优的旅行路径，因此， I不会被展开。最后，节点J，K成为E-节点并被展开。经过这些展开过程，队列变为空，算法结束。找到的最优方案是节点 N所对应的旅行路径。如果不使用F I F O方法，还可以使用最小耗费方法来搜索解空间树，即用一个最小堆来存储活节点。这种方法同样从节点 B开始搜索，并使用一个空的活节点列表。当节点 B展开时，生成节点C、D和E并将它们加入最小堆中。在最小堆的节点中，E具有最小耗费（因为1 - 4的局部旅行的耗费是4） ，因此成为E-节点。展开E生成节点J和K并将它们加入最小堆，这两个节点的耗费分别为1 4和2 4。此时，在所有最小堆的节点中，D具有最小耗费，
13、因而成为E-节点，并生成节点H和I。至此，最小堆中包含节点 C、H、I、J和K，H具有最小耗费，因此H成为下一个E-节点。展开节点E，得到一个完整的旅行路径 1 - 3 - 2 - 4 - 1，它的开销是2 5。节点J是下一个E-节点，展开它得到节点P，它对应于一个耗费为2 5的旅行路径。节点K和I是下两个E-节点。由于I的开销超过了当前最优的旅行路径，因此搜索结束，而剩下的所有活节点都不能使我们找到更优的解。对于例1 7 - 2的背包问题，可以使用一个定界函数来减少生成和展开的节点数量。这种函数将确定旅行的最小耗费的下限，这个下限可通过展开某个特定的节点而得到。如果一个节点的定界函数值不能比
14、当前的最优旅行更小，则它将被删除而不被展开。另外，对于最小耗费分枝定界，节点按照它在最小堆中的非降序取出。在以上几个例子中，可以利用定界函数来降低所产生的树型解空间的节点数目。当设计定界函数时，必须记住主要目的是利用最少的时间，在内存允许的范围内去解决问题。而通过产生具有最少节点的树来解决问题并不是根本的目标。因此，我们需要的是一个能够有效地减少计算时间并因此而使产生的节点数目也减少的定界函数。回溯法比分枝定界在占用内存方面具有优势。回溯法占用的内存是 O（解空间的最大路径长度） ，而分枝定界所占用的内存为 O（解空间大小） 。对于一个子集空间，回溯法需要(n)的内存空间，而分枝定界则需要O
15、( 2n) 的空间。对于排列空间，回溯需要(n) 的内存空间，分枝定界需要O (n!) 的空间。虽然最大收益（或最小耗费）分枝定界在直觉上要好于回溯法，并且在许多情况下可能会比回溯法检查更少的节点，但在实际应用中，它可能会在回溯法超出允许的时间限制之前就超出了内存的限制。5 1 8第三部分算法设计方法下载练习1. 假定在一个L I F O分枝定界搜索中，活节点列表的行为与堆栈相同，请使用这种方法来解决例1 7 - 2的背包问题。L I F O分枝定界与回溯有何区别？2. 对于如下0 / 1背包问题：n=4, p=4,3,2,1, w=1,2,3,4, c=6。1) 画出有四个对象的背包问题的解
16、空间树。2) 像例1 7 - 2那样，描述用F I F O分枝定界法解决上述问题的过程。3) 使用程序1 6 - 6的B o u n d函数来计算子树上任一叶节点可能获得的最大收益值，并根据每一步所能得到的最优解对应的定界函数值来判断是否将节点加入活节点列表中。解空间中哪些节点是使用以上机制的F I F O分枝定界方法产生的？4) 像例1 7 - 2那样，描述用最大收益分枝定界法解决上述问题的过程。5) 在最大收益分枝定界中，若使用3）中的定界函数，将产生解空间树中的哪些节点？17.2 应用17.2.1 货箱装船1. FIFO分枝定界1 6 . 2 . 1节的货箱装船问题主要是寻找第一条船的最大装载方案。这个问题是一个子集选择问题，它的解空间被组织成一个子集树。对程序 1 6 - 1进行改造，即得到程序1 7 - 1中的F I F O分枝定界代码。程序1 7 - 1只是寻找最大装载的重量。程序17-1 货箱装船问题的F I F O分枝定界算法templatevoid AddLiveNode(LinkedQueue &Q, T wt,T& bestw, int i, int n)/ 如果
