分支定界法概述

分枝定界-简介分枝定界（branchandbound）是另一种系统地搜寻解空间的方法，它与回溯法的主要区分在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的全部新节点。在生成的节点中，抛弃那些不行能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。分枝定界-方法有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）：1）先进先出（FIFO）即从活节点表中取出节点的挨次与加入节点的挨次相同，因此活节点表的性质与队列相同。2）最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。假如查找一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费的活节点；假如盼望搜寻一个具有最大收益的解，则可用最大堆来构造活节点表，下一个E-节点是具有最大收益的活节点。分枝定界-例子例5-1【迷宫老鼠】考察图16-3a给出的迷宫老鼠例子和图16-1的解空间结构。使用FIF0分枝定界，初始时取（1,1）作为E-节点且活动队列为空。迷宫的位置（1,1）被置为1,以免再次返回到这个位置。（1,1）被扩充，它的相邻节点（1,2）和（2,1）加入到队列中（即活节点表X为避开再次回到这两个位置，将位置（1,2）和（2,1）置为1。此时迷宫如图17-1a所示，E-节点（1,1）被删除。节点（1,2）从队列中移出并被扩充。检查它的三个相邻节点（见图16-1的解空间），只有（1,3）是可行的移动（剩余的两个节点是障碍节点），将其加入队列，并把相应的迷宫位置置为1,所得到的迷宫状态如图17-lb所示。节点（1,2）被删除，而下一个E-节点（2,1）将会被取出，当此节点被绽开时，节点（3,1）被加入队列中，节点（3,1）被置为1,节点（2,1）被删除，所得到的迷宫如图17-lc所示。此时队列中包含（1,3）和（3,1）两个节点。随后节点（1,3）变成下一个E-节点，由于此节点不能到达任何新的节点，所以此节点即被删除，节点（3,1）成为新的E-节点，将队列清空。节点（3,1）绽开，（3,2）被加入队列中,010（3,1）被删除。（3,2）变为新的E-节点,绽开此节点后，到达节点（3,3）,即迷宫的出口。使用FIFO搜寻，总能找出从迷宫入口到出口的最短路径。需要留意的是：采用回溯法找到的路径却不肯定是最短路径。好玩的是，程序6-11已经给出了采用FIFO分枝定界搜寻从迷宫的（1,1）位置到（n,n）位置的最短路径的代码。例5-2【0/1背包问题】下面比较分别采用FIFO分枝定界和最大收益分枝定界方法来解决如下背包问题：n=3,w=[20,15,15],p=[40,25,25],c=30o法FO分枝定界采用一个队列来纪录活节点，节点将根据FIFO挨次从队列中取出；而最大收益分枝定界使用一个最大堆，其中的E-节点根据每个活节点收益值的降序，或是根据活节点任意子树的叶节点所能获得的收益估量值的降序从队列中取出。本例所使用的背包问题与例16.2相同，并且有相同的解空间树。使用FIF0分枝定界法搜寻，初始时以根节点A作为E-节点，此时活节点队列为空。当节点A绽开时，生成了节点B和C,由于这两个节点都是可行的，因此都被加入活节点队列中，节点A被删除。下一个E-节点是B,绽开它并产生了节点D和E,D是不行行的，被删除，而E被加入队列中。下一步节点C成为E-节点，它绽开后生成节点F和G,两者都是可行节点，加入队列中。下一个E-节点E生成节点J和K,J不行行而被删除，K是一个可行的叶节点，并产生一个到目前为止可行的解，它的收益值为40o下一个E-节点是F,它产生两个孩子L、M,L代表一个可行的解且其收益值为50,M代表另一个收益值为15的可行解。G是最终一个E-节点，它的孩子N和0都是可行的。由于活节点队列变为空，因此搜寻过程终止,最佳解的收益值为50。可以看到，工作在解空间树上的FIFO分枝定界方法特别象从根节点动身的宽度优先搜寻。它们的主要区分是在FIFO分枝定界中不行行的节点不会被搜寻。最大收益分枝定界算法以解空间树中的节点A作为初始节点。绽开初始节点得到节点B和C,两者都是可行的并被插入堆中，节点B获得的收益值是40（设xl=1），而节点C得到的收益值为0oA被删除，B成为下一个E-节点，由于它的收益值比C的大。当绽开B时得到了节点D和E,D是不行行的而被删除，E加入堆中。由于E具有收益值40,而C为0,由于E成为下一个E-节点。绽开E时生成节点J和K,J不行行而被删除，K是一个可行的解，因此K为作为目前能找到的最优解而纪录下来，然后K被删除。由于只剩下一个活节点C在堆中，因此C作为E-节点被绽开，生成F、G两个节点插入堆中。F的收益值为25,因此成为下一个E-节点，绽开后得到节点L和M,但L、M都被删除，由于它们是叶节点，同时L所对应的解被作为当前最优解纪录下来。最终，G成为E-节点，生成的节点为N和0,两者都是叶节点而被删除，两者所对应的解都不比当前的最优解更好，因此最优解保持不变。此时堆变为空，没有下一个E-节点产生，搜寻过程终止。终止于J的搜寻即为最优解。如同在回溯方法中一样，可采用一个定界函数来加速最优解的搜寻过程。定界函数为最大收益设置了一个上限，通过绽开一个特别的节点可能获得这个最大收益。假如一个节点的定界函数值不大于目前最优解的收益值，则此节点会被删除而不作绽开，更进一步，在最大收益分枝定界方法中，可以使节点根据它们收益的定界函数值的非升序从堆中取出,而不是根据节点的实际收益值来取出。这种策略从可能到达一个好的叶节点的活节点动身,而不是从目前具有较大收益值的节点动身。例5-3【旅行商问题】对于图16-4的四城市旅行商问题，其对应的解空间为图16-5所示的排列树。FIFO分枝定界使用节点B作为初始的E-节点，活节点队列初始为空。当B绽开时，生成节点C、D和E。由于从顶点1到顶点2,3,4都有边相连，所以C、D、E三个节点都是可行的并加入队列中。当前的E-节点B被删除，新的E-节点是队列中的第一个节点，即节点Co由于在图16-4中存在从顶点2到顶点3和4的边，因此绽开C,生成节点F和G,两者都被加入队列。下一步，D成为E-节点，接着又是E,到目前为止活节点队列中包含节点F到Ko下一个E-节点是F,绽开它得到了叶节点L。至此找到了一个旅行路径，它的开销是59O绽开下一个E-节点G，得到叶节点M,它对应于一个开销为66的旅行路径。接着H成为E-节点，从而找到叶节点N,对应开销为25的旅行路径。下一个E-节点是I,它对应的部分旅行1-3-4的开销已经为26,超过了目前最优的旅行路径，因此，I不会被绽开。最终，节点J,K成为E-节点并被绽开。经过这些绽开过程，队列变为空，算法结束。找到的最优方案是节点N所对应的旅行路径。假如不使用FIF0方法，还可以使用最小耗费方法来搜寻解空间树，即用一个最小堆来存储活节点。这种方法同样从节点B开头搜寻，并使用一个空的活节点列表。当节点B绽开时，生成节点C、D和E并将它们加入最小堆中。在最小堆的节点中，E具有最小耗费（由于1-4的局部旅行的耗费是4）,因此成为E-节点。绽开E生成节点J和K并将它们加入最小堆，这两个节点的耗费分别为14和24。此时，在全部最小堆的节点中，D具有最小耗费，因而成为E-节点，并生成节点H和10至此，最小堆中包含节点C、H、I、J和K,H具有最小耗费，因此H成为下一个E-节点。绽开节点E,得到一个完整的旅行路径1-3-2-4-1,它的开销是25。节点J是下一个E-节点，绽开它得到节点P,它对应于一个耗费为25的旅行路径。节点K和I是下两个E-节点。由于I的开销超过了当前最优的旅行路径，因此搜寻结束，而剩下的全部活节点都不能使我们找到更优的解。对于例5-2的背包问题，可以使用一个定界函数来削减生成和绽开的节点数量。这种函数》各确定旅行的最小耗费的下限，这个下限可通过绽开某个特定的节点而得到。假如一个节点的定界函数值不能比当前的最优旅行更小，则它将被删除而不被绽开。此外，对于最小耗费分枝定界，节点根据它在最小堆中的非降序取出。在以上几个例子中，可以采用定界函数来降低所产生的树型解空间的节点数目。当设计定界函数时，必需记住主要目的是采用最少的时间，在内存允许的范围内去解决问题。而通过产生具有最少节点的树来解决问题并不是根本的目标。因此，我们需要的是一个能够有效地削减计算时间并因此而使产生的节点数目也削减的定界函数。回溯法比分枝定界在占用内存方面具有优势。回溯法占用的内存是0（解