选择下一个E-节点

有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）：

先进先出

先进先出（F I F O） 即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活节点表的性质与队列相同。

最小耗费或最大收益法

在这种模式中，每个节点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个E-节点是具有最大收益的活节点。

示例

迷宫老鼠

考察图16-3a 给出的迷宫老鼠例子和图1 6 - 1的解空间结构。使用F I F O分枝定界，初始时取（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 F O搜索，总能找出从迷宫入口到出口的最短路径。需要注意的是：利用回溯法找到的路径却不一定是最短路径。有趣的是，程序6 - 11已经给出了利用F I F O分枝定界搜索从迷宫的（1，1）位置到（n，n） 位置的最短路径的代码。

背包问题

下面比较分别利用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-节点，此时活节点队列为空。当节点

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都是可行的。由于活节点队列变为空，因此搜索过程终止，最佳解的收益值为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是一个可行的解，因此K为作为目前能找到的最优解而记录下来，然后K被删除。由于只剩下一个活节点C在堆中，因此C作为E-节点被展开，生成F、G两个节点插入堆中。F的收益值为2 5，因此成为下一个E-节点，展开后得到节点L和M，但L、M都被删除，因为它们是叶节点，同时L所对应的解被作为当前最优解记录下来。最终，G成为E-节点，生成的节点为N和O，两者都是叶节点而被删除，两者所对应的解都不比当前的最优解更好，因此最优解保持不变。此时堆变为空，没有下一个E-节点产生，搜索过程终止。终止于J的搜索即为最优解。

犹如在回溯方法中一样，可利用一个定界函数来加速最优解的搜索过程。定界函数为最大收益设置了一个上限，通过展开一个特殊的节点可能获得这个最大收益。如果一个节点的定界函数值不大于目前最优解的收益值，则此节点会被删除而不作展开，更进一步，在最大收益分枝定界方法中，可以使节点按照它们收益的定界函数值的非升序从堆中取出，而不是按照节点的实际收益值来取出。这种策略从可能到达一个好的叶节点的活节点出发，而不是从目前具有较大收益值的节点出发。