经典算法思想4——分支限界（branch-and-bound）

Answer 1

分支界限法是一种在问题的解空间树上搜索问题解的算法。与回溯法相比，它们的求解目标不同。回溯法的目的是找出满足约束条件的所有解，而分支界限法则旨在找到满足约束条件的一个解，或在满足约束条件的解中找出最优解。

分支搜索算法遵循广度优先策略，依次搜索每个结点的所有分支，抛弃不满足约束的结点，其余结点加入活结点表。接着从表中选择一个结点作为下一个扩展结点，继续搜索。选择下一个扩展结点的方式不同，会有不同的分支搜索方式，如FIFO搜索、LIFO搜索、优先队列式搜索。

分支界限法的一般过程包括搜索策略和分支界限法的特殊搜索方式。在扩展结点处生成所有子结点，并从活结点表中选择一个最有利的结点作为扩展结点，这有利于搜索朝着解空间树上有最优解的分支推进，以便尽快找到一个最优解。

分支界限法以广度优先或最小耗费优先的方式搜索问题的解空间树。在搜索过程中，分支限界法与回溯法对当前扩展结点的使用方式不同。每一个活结点只有一次机会成为扩展结点，并一次性产生其所有子结点。在这些子结点中，那些导致不可行解或非最优解的子结点被舍弃，其余子结点加入活结点中。这一过程持续到找到所求解或活结点表为空时为止。

在搜索过程中，对某个节点进行估计，确定是否向下搜索（选择最小损耗的结点进行搜索）。在分支结点上，预先估算沿着各个儿子结点向下搜索的路径中目标函数可能取得的界，然后选择界最小或最大的结点向下搜索。通常采用优先队列维护这些结点和它们可能取得的界。

回溯法与分支界限法的区别主要在于求解目标和搜索方式。回溯法的目的是找出满足约束条件的所有解，而分支界限法的目标是在满足约束条件的解中找出最优解。分支界限法采用广度优先或最小损耗优先搜索方式，而回溯法采用深度优先搜索方式。

分支界限法的步骤涉及定义结点包含的信息，包括当前选择装入背包的商品集合、当前不选择装入背包的商品集合、当前尚待选择的商品集合、搜索深度以及上界。举一个例子，解决背包问题时，假设商品按照价值重量比递减排序，那么选择价值重量比最大的商品进行分支，可以确定装入或不装入背包的分支。当总重量超过背包载重量时，立即剪枝，优化搜索过程。

通过以上步骤和例子，可以看到分支界限法在优化搜索路径、减少不必要的计算、快速找到最优解方面具有显著优势。这种方法广泛应用于各种优化问题中，如背包问题、资源分配问题等。

请参考原文获取更多实例和深入理解。