分支限界法：求解路径与优化问题的关键策略

分支限界法是一种在计算机科学中用于求解优化问题的搜索算法，尤其适用于那些涉及决策树结构的问题，如路径查找、规划和组合优化等。它在搜索过程中通过限制或"界限"来避免无效的解决方案，从而提高效率。本章节将重点介绍分支限界法的基本思想、与回溯法的区别以及在具体问题如单源最短路径、装载问题、布线问题、背包问题和最大团问题等的应用。 分支限界法的核心理念是广度优先或最小耗费优先地探索问题解空间树。与回溯法不同，回溯法旨在找到所有满足约束条件的解，而分支限界法则聚焦于找到一个满足条件的最佳解。搜索策略上，回溯法通常采用深度优先的方式，而分支限界法则可以是广度优先或优先队列策略，如队列式（FIFO）和优先队列式（最大堆/最小堆）。 在具体实现中，分支限界法会维护一个活结点表，每个活结点只允许扩展一次。当一个结点扩展时，如果其子节点导致不可行解或非最优解，这些子节点会被舍弃；反之，可行且有潜力的子节点会被添加到活结点表中。然后，算法会选择下一个具有最高优先级或最小代价的结点作为扩展节点，直到找到所需的解或活结点表为空。 以背包问题为例，队列式分支限界法展示了如何通过优先级队列来决定下一次扩展哪个物品。在这个例子中，算法会根据剩余容量（Cr）、物品价值与重量的关系来判断是否可行，以及是否能带来最大的价值。随着搜索的进行，算法不断调整当前解决方案（x）和剩余容量，直至找到最优解。 分支限界法是一种高效解决优化问题的方法，它通过策略性地剪枝搜索空间，确保了找到的是最佳解或者符合某个特定标准的解，这在各种实际问题中都有着广泛的应用。