数据结构之高级算法讲解

算法思想 分枝定界(branch and bound)是另一种系统地搜索解空间的方法,它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时,则生成从该节点移动一步即可到达的所有新节点。在生成的节点中,抛弃那些不可能导出(最优)可行解的节点,其余节点加入活节点表,然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充,直到找到解或活动表为空,扩充过程才结束。