分支限界法是一种在计算机科学中用于寻找最优解的算法，尤其在解决组合优化问题时极为常见。它与回溯法相似，都是通过探索问题的解空间树来找到解决方案，但两者的目标和策略有所不同。
一、基本描述
分支限界法主要目标是找到满足约束条件的一个解，或者是找到在特定意义下的最优解，例如最小化成本或最大化收益。这种算法通常以广度优先或最小耗费优先的方式搜索解空间树。与回溯法的深度优先搜索不同，分支限界法更关注全局最优而非局部最优。
1. 分支搜索算法：
- FIFO（First-In-First-Out，先进先出）搜索：按照节点进入活节点表的顺序进行扩展，类似于广度优先搜索。
- LIFO（Last-In-First-Out，后进先出）搜索：类似于深度优先搜索，但通常不用于分支限界法。
- 优先队列式搜索：根据节点的优先级（如函数值或限界值）选择下一个扩展节点，常用于实现最佳优先搜索。
二、分支限界法的一般过程
在分支限界法中，每个活节点只被扩展一次，一次性生成所有子节点。然后，通过对每个活节点计算一个函数值或限界值来评估其潜在的优劣。这个限界函数用于指导搜索，确保优先处理可能导致最优解的节点。如果某个子节点无法导致最优解或违反约束条件，它将被立即排除。搜索继续进行，直到找到最优解或者活节点表为空。
三、回溯法与分支限界法的区别
- 搜索方式：回溯法采用深度优先搜索，而分支限界法则采用广度优先或最小耗费优先搜索。
- 数据结构：回溯法常用堆栈存储活节点，而分支限界法可能使用优先队列来更有效地选择最优节点。
- 结点存储特性：回溯法的活节点在所有可行子节点被遍历后才会被弹出，而分支限界法则是一次性生成并处理所有子节点。
- 应用场景：回溯法适用于寻找所有解或部分解的问题，而分支限界法更适用于寻找单一最优解的问题。
四、典型应用
分支限界法常应用于诸如旅行商问题、0-1背包问题、最小生成树、最短路径等优化问题。通过设置适当的限界函数，可以有效地避免无效的搜索路径，提高求解效率。
分支限界法是一种强大的工具，尤其对于那些需要找到全局最优解的问题。与回溯法相比，它提供了更为系统和高效的搜索策略，能够更快地收敛到最优解，但可能需要更多的内存来存储活节点。在实际应用中，选择哪种方法取决于问题的具体性质和对时间和空间复杂度的要求。
