1. 概述
在计算机科学中，存在大量具有有限但规模庞大的可行解集合的优化问题。其中一些问题，如图中最短路径（Bellman-Ford）、最小生成树（MST），可以在多项式时间内求解。
但还有相当一部分问题，比如生产计划、机组调度等，无法在多项式时间内求解，属于 NP-Hard 类问题，属于 组合优化问题（Combinatorial Optimization）。
分支限界法（Branch and Bound）是一种广泛用于解决此类问题的算法范式。
本文将深入讲解分支限界算法的原理、应用场景及其实现方式。
2. 基本思想
分支限界算法用于解决组合优化、离散优化和一般数学优化问题。给定一个 NP-Hard 问题，它通过遍历所有可能的解空间来找到最优解。
核心思想是构建一棵决策树（Decision Tree），树的根节点代表整个解空间：
每个子节点代表一个部分解。在构建树的过程中，我们需要为问题设置上界（Upper Bound）和下界（Lower Bound）：
- 上界：可以通过局部优化方法或随机选取一个解来估算
- 下界：通常通过凸松弛（Convex Relaxation）或对偶（Duality）方法获得
在每层遍历中，我们优先探索具有最优界的节点，从而更快找到最优解。
因此，寻找一个高质量的上下界是分支限界法的关键。
3. 分支限界适合哪些场景？
分支限界法在以下情况下表现良好：
✅ 离散优化问题：变量必须属于离散集合，例如 0-1 整数规划、网络流问题等。
✅ 组合优化问题：在离散且庞大的解空间中寻找目标函数的极值，例如布尔可满足性问题（SAT）、整数线性规划（ILP）等。
这类问题通常无法通过贪心或动态规划高效求解，而分支限界法能在合理时间内找到最优解或近似最优解。
4. 分支限界算法示例：任务分配问题
4.1 问题描述
假设我们有 3 个工人 A、B、C 和 3 个任务 Job 1~3，每个工人完成每个任务的代价如下表所示：
| Job 1 | Job 2 | Job 3 | |
|---|---|---|---|
| A | 9 | 3 | 4 |
| B | 7 | 8 | 4 |
| C | 10 | 5 | 2 |
每个工人只能分配一个任务，每个任务只能分配给一个工人。目标是使总代价最小。
4.2 算法伪代码
algorithm MinCost(M):
// INPUT
// M = The cost matrix
// OUTPUT
// The optimal job assignment minimizing the total cost
while true:
E <- LeastCost()
if E is a leaf node:
print(E)
return
for each child S of E:
Add(S)
S.parent <- E
说明：
M是输入的代价矩阵MinCost()维护一个活跃节点列表LeastCost()返回当前活跃节点中代价最小的节点Add()计算新节点代价并加入列表
4.3 算法流程图
流程说明：
- 初始状态下，工人 A 可以分配任意任务，构建第一层节点并计算代价
- 选择代价最小的节点继续扩展，即分配 Job 2 给 A
- 剩余两个任务分配给 B 和 C，继续计算各节点代价
- 最终得出最优解：A 分配 Job 2，B 分配 Job 1，C 分配 Job 3，总代价为 12
5. 优点
- ✅ 时间复杂度较低：相比暴力枚举，分支限界通过剪枝策略减少无效搜索路径
- ✅ 能找到最优解：在问题规模适中时，可以确保找到全局最优解
- ✅ 路径唯一：不会重复访问节点，搜索路径清晰简洁
6. 缺点
- ❌ 时间开销大：对于大规模问题，节点数量可能指数级增长
- ❌ 难以并行化：分支限界依赖于对解空间的顺序探索，难以并行处理
7. 总结
分支限界法是一种广泛应用于组合优化问题的经典算法。它通过构建决策树并利用上下界剪枝策略，在合理时间内找到最优解。
适用场景包括但不限于：
- 0-1 整数规划
- 网络流问题
- 布尔可满足性问题（SAT）
- 任务分配问题
虽然在大规模问题中存在性能瓶颈，但在中等规模下，它依然是求解 NP-Hard 问题的有力工具。在实际开发中，结合问题特性设计高效的剪枝策略，可以显著提升算法效率。