分枝定界-简介分枝定界（branch and bound）是另一种系统地搜索解空间的方法，它与回溯法的主要区 别在于对E-节点的扩充方式每个活节点有且仅有一次机会变成E-节点当一个节点变为 E-节点时，则生成从该节点移动一步即可到达的所有新节点在生成的节点中，抛弃那些不 可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下 一个E-节点从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩 充过程才结束分枝定界-方法有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）：1） 先进先出（F I F 0）即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活节 点表的性质与队列相同2） 最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益如果查找 一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费 的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个 E-节点是具有最大收益的活节点分枝定界-例子例5-1【迷宫老鼠】考察图16-3a给出的迷宫老鼠例子和图1 6 - 1的解空间结构。
使用F I F 0分枝定界，初始时取（1, 1）作为E-节点且活动队列为空迷宫的位置（1 , 1 ）被置 为1,以免再次返回到这个位置1, 1）被扩充，它的相邻节点（1, 2）和（2, 1）加入 到队列中（即活节点表）为避免再次回到这两个位置，将位置（1, 2）和（2, 1）置为1 此时迷宫如图1 7 - 1 a所示，E-节点（1, 1）被删除节点（1, 2）从队列中移出并被扩充检查它的三个相邻节点（见图1 6 - 1的解空间），只 有（1, 3）是可行的移动（剩余的两个节点是障碍节点），将其加入队列，并把相应的迷宫 位置置为1,所得到的迷宫状态如图17-1b所示节点（1, 2）被删除，而下一个E-节点（2, 1）将会被取出，当此节点被展开时，节点（3, 1）被加入队列中，节点（3, 1）被置为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 FO搜索，总能找出从迷宫入口到出口的最短路径需要注意的是：利用回溯法找 到的路径却不一定是最短路径有趣的是，程序6 - 11已经给出了利用F I F O分枝定界搜 索从迷宫的（1, 1）位置到（n n）位置的最短路径的代码例5-2【0/1背包问题】下面比较分别利用F I F O分枝定界和最大收益分枝定界方法来解 决如下背包问题：n=3, w=【20,15,15】,p=【40,25,25】,c= 3 0F I F O分枝定界利用一个 队列来记录活节点，节点将按照F I F O顺序从队列中取出；而最大收益分枝定界使用一个 最大堆，其中的E-节点按照每个活节点收益值的降序，或是按照活节点任意子树的叶节点 所能获得的收益估计值的降序从队列中取出本例所使用的背包问题与例1 6.2相同，并且 有相同的解空间树使用F I F O分枝定界法搜索，初始时以根节点A作为E-节点，此时活节点队列为空当节 占八、、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代 表另一个收益值为15的可行解G是最后一个E-节点，它的孩子N和O都是可行的由 于活节点队列变为空，因此搜索过程终止，最佳解的收益值为5 0可以看到，工作在解空间树上的F I F O分枝定界方法非常象从根节点出发的宽度优先搜索 它们的主要区别是在F I F O分枝定界中不可行的节点不会被搜索最大收益分枝定界算法 以解空间树中的节点A作为初始节点展开初始节点得到节点B和C,两者都是可行的并 被插入堆中，节点B获得的收益值是4 0 （设x1 = 1）,而节点C得到的收益值为0A被删 除，B成为下一个E-节点，因为它的收益值比C的大当展开B时得到了节点D和E, D 是不可行的而被删除，E加入堆中由于E具有收益值4 0，而C为0,因为E成为下一个 E-节点展开E时生成节点J和K, J不可行而被删除，K是一个可行的解，因此K为作为目前能找 到的最优解而记录下来，然后K被删除。
由于只剩下一个活节点C在堆中，因此C作为E- 节点被展开，生成F、G两个节点插入堆中F的收益值为2 5,因此成为下一个E-节点， 展开后得到节点L和M,但L、M都被删除，因为它们是叶节点，同时L所对应的解被作 为当前最优解记录下来最终，G成为E-节点，生成的节点为N和O,两者都是叶节点而 被删除，两者所对应的解都不比当前的最优解更好，因此最优解保持不变此时堆变为空， 没有下一个E-节点产生，搜索过程终止终止于J的搜索即为最优解犹如在回溯方法中一样，可利用一个定界函数来加速最优解的搜索过程定界函数为最大收 益设置了一个上限，通过展开一个特殊的节点可能获得这个最大收益如果一个节点的定界 函数值不大于目前最优解的收益值，则此节点会被删除而不作展开，更进一步，在最大收益 分枝定界方法中，可以使节点按照它们收益的定界函数值的非升序从堆中取出，而不是按照 节点的实际收益值来取出这种策略从可能到达一个好的叶节点的活节点出发，而不是从目 前具有较大收益值的节点出发例5-3【旅行商问题】对于图1 6 - 4的四城市旅行商问题，其对应的解空间为图1 6 - 5所 示的排列树F I F O分枝定界使用节点B作为初始的E-节点，活节点队列初始为空。
当B 展开时，生成节点C、D和E由于从顶点1到顶点2，3，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 6,超过了目前最优的旅行路径， 因此，I不会被展开最后，节点J, K成为E-节点并被展开经过这些展开过程，队列变 为空，算法结束找到的最优方案是节点N所对应的旅行路径如果不使用F I FO方法，还可以使用最小耗费方法来搜索解空间树，即用一个最小堆来存 储活节点这种方法同样从节点B开始搜索，并使用一个空的活节点列表当节点B展开 时，生成节点C、D和E并将它们加入最小堆中。
在最小堆的节点中，E具有最小耗费（因 为1 - 4的局部旅行的耗费是4）,因此成为E-节点展开E生成节点J和K并将它们加入最 小堆，这两个节点的耗费分别为14和2 4此时，在所有最小堆的节点中，D具有最小耗 费，因而成为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的开销超过了当前最优的旅行路径， 因此搜索结束，而剩下的所有活节点都不能使我们找到更优的解对于例5 - 2的背包问题，可以使用一个定界函数来减少生成和展开的节点数量这种函数 将确定旅行的最小耗费的下限，这个下限可通过展开某个特定的节点而得到如果一个节点 的定界函数值不能比当前的最优旅行更小，则它将被删除而不被展开另外，对于最小耗费 分枝定界，节点按照它在最小堆中的非降序取出在以上几个例子中，可以利用定界函数来降低所产生的树型解空间的节点数目当设计定界 函数时，必须记住主要目的是利用最少的时间，在内存允许的范围内去解决问题。
而通过产 生具有最少节点的树来解决问题并不是根本的目标因此，我们需要的是一个能够有效地减 少计算时间并因此而使产生的节点数目也减少的定界函数回溯法比分枝定界在占用内存方面具有优势回溯法占用的内存是O （解空间的最大路径长 度），而分枝定界所占用的内存为O （解空间大小）对于一个子集空间，回溯法需要（n）的 内存空间，而分枝定界则需要O ( 2n )的空间对于排列空间，回溯需要(n)的内存空间， 分枝定界需要O (n!)的空间虽然最大收益(或最小耗费)分枝定界在直觉上要好于回溯 法，并且在许多情况下可能会比回溯法检查更少的节点，但在实际应用中，它可能会在回溯 法超出允许的时间限制之前就超出了内存的限制。