算法思想算法思想例15-1下一个扩展结点B，产生结点D和E，由于D是不可行的，因此被删除，而E被加入队列中。下一步选择结点C为扩展结点，生成结点F和G，两者都是可行结点，加入队列中。下一个扩展结点E生成结点J和K，J不可行而被删除，K是一个可行的叶结点，并产生一个到目前为止可行的解，它的收益值为40。例15-1从上述过程可看出，在解空间树上进行的FIFO分枝定界方法类似于从根结点出发的广度优先搜索，它们的主要区别是在FIFO分枝定界法中不可行的结点不会被搜索。②最大收益分枝定界法使用一个最大堆，其中的扩展结点按照每个活结点收益值的降序，或者按照活结点任意子树的叶结点所能获得的收益估计值的降序，从队列中取出。该方法的搜索过程也以解空间树中的结点A作为初始结点，进行扩展后得到结点B和C，两者都是可行的并被加入堆中，结点B获得的收益值是40（设x1=1），C获得的收益值为0。例15-1由于只剩下一个活结点C在堆中，因此C作为扩展结点被展开，生成F、G两个结点加入堆中。F的收益值为25，因此成为下一个扩展结点，展开后得到结点L和M，L所对应的解作为当前最优解被记录下来。由于L和M是叶结点，因此同时都被删除，最后G成为扩展结点，生成的结点为N和O，两者所对应的解都不比当前的最优解更好，因此最优解保持不变，两者都是叶结点而被删除，此时堆变为空，搜索过程结束，到达结点L的搜索为最优解。算法思想应用应用应用应用应用应用应用应用应用应用应用应用应用应用应用应用应用应用