在求解组合优化问题时，比如背包问题、任务分配、旅行商问题，最容易想到的方法是枚举所有可能的情况，再从中挑选最优解。但解空间往往呈指数级增长，哪怕只有20个物品的背包问题，全排列的组合数量也大到难以承受。分支限界法就是为了解决这个问题而诞生的，它在系统搜索解空间的同时，利用界限函数估算候选解的上下界，及时剪掉那些不可能产生最优解的分支，从而把搜索规模压缩到可接受的范围。
分支限界法的核心思想是什么
分支限界法本质上是一种对解空间树的系统性搜索策略。它把问题的所有可能解组织成一棵树，树的根节点代表初始状态，每一个子节点代表一次决策的选择。搜索的过程就是从根节点出发不断扩展子节点的过程，这一点和回溯法是相通的。
它区别于暴力枚举的关键在于「限界」两个字。在扩展每个节点之前，算法会用一个界限函数对这个节点能产生的解的好坏做出估计：如果是求最大值问题，就估算这个分支可能达到的价值上界；如果是求最小值问题，就估算可能付出的代价下界。一旦发现某个节点的界限已经比当前找到的最好解还要差，就可以断定这条分支不可能包含最优解，直接剪掉，不再继续搜索。
举个直观的例子，在0-1背包问题中，如果已经装了部分物品，剩余容量还不足以让总价值超过当前已知的最优值，那么无论后面怎么选，这条分支都不用再考虑了。剪枝越准确，被排除的分支就越多，算法效率就越高。因此界限函数的设计是分支限界法的灵魂，它必须在「估算准确」和「计算开销小」之间取得平衡。
分支限界法与回溯法有什么区别
很多人容易把分支限界法和回溯法混为一谈，因为两者都基于解空间树，都用到了剪枝。但从求解目标和搜索策略来看，它们有明显的差异。
首先，求解目标不同。回溯法通常用于找出满足约束条件的所有解或者任意一个可行解，比如八皇后问题、图的着色问题；而分支限界法专注于求解最优值问题，比如最大价值、最小代价，它需要一个能够比较优劣的目标函数作为前提。
其次，搜索方式不同。回溯法一般采用深度优先策略，一条路走到黑，走不通再回头；分支限界法通常采用广度优先或者最佳优先策略，借助队列或优先队列来管理待扩展的节点，每次挑选界限最有希望的节点优先扩展。这种差异带来的好处是，分支限界法往往能较早地发现一个较优的可行解，这个解又能反过来作为剪枝依据，进一步压缩搜索空间。
最后，剪枝依据不同。回溯法的剪枝主要基于约束条件，违反约束就回退；分支限界法的剪枝基于目标函数的界限，即使满足约束，只要不可能优于当前最优解，也会被舍弃。两者的对比可以总结为下表：
| 对比项 | 回溯法 | 分支限界法 |
|---|---|---|
| 求解目标 | 所有解或任一可行解 | 最优解 |
| 搜索方式 | 深度优先 | 广度优先或最佳优先 |
| 数据结构 | 递归栈 | 队列或优先队列 |
| 剪枝依据 | 约束函数 | 界限函数 |
经典应用一：任务分配问题
任务分配问题是分支限界法最经典的入门案例。假设有n个任务要分配给n个人，第i个人完成第j个任务需要花费cost[i][j]，要求每个人恰好分配一个任务，且总代价最小。
处理思路是：用已经分配任务的代价之和作为当前代价，再用界限函数估计剩余任务的最小可能代价，一个简单的估计方法是取每一行剩余元素的最小值之和。如果某个节点的下界已经不小于当前最优解，就剪掉。下面用Python实现一个示例：
import heapq
def assignment_problem(cost):
n = len(cost)
# 计算每一行的最小值之和，作为初始下界
bound = sum(min(row) for row in cost)
# 优先队列元素：(下界, 已花费代价, 下一个待分配的人, 已用任务集合)
heap = [(bound, 0, 0, frozenset())]
best = float('inf')
while heap:
lb, cur, person, used = heapq.heappop(heap)
# 剪枝：下界不优于当前最优解，直接跳过
if lb >= best:
continue
if person == n:
best = min(best, cur)
continue
for task in range(n):
if task not in used:
new_cost = cur + cost[person][task]
# 用剩余各行最小值之和估计下界
rest = sum(min(cost[i][j] for j in range(n) if j not in used and j != task)
for i in range(person + 1, n))
heapq.heappush(heap, (new_cost + rest, new_cost, person + 1, used | {task}))
return best
cost = [
[9, 2, 7, 8],
[6, 4, 3, 7],
[5, 8, 1, 8],
[7, 6, 9, 4]
]
print(assignment_problem(cost)) # 输出 13
这段代码里，界限函数采用的是行最小值的松弛估计，虽然不是最紧的界，但计算简单，剪枝效果已经不错。如果想要更精确的界，可以用匈牙利算法求解剩余矩阵的下界，代价是每个节点的计算量会增加，实际中需要权衡。
经典应用二：0-1背包问题的分支限界实现
在0-1背包问题中，常见的界限函数是用贪心思想计算上界：把剩余物品按单位重量价值降序排列，尽可能往背包里装，装不下的部分按比例折算。由于实际只能整个装入物品，这个折算出来的上界一定不小于真实能达到的最大价值，因此用它剪枝是安全的。
from queue import PriorityQueue
class Node:
def __init__(self, level, value, weight, bound):
self.level = level # 当前考虑到的物品下标
self.value = value # 已获得的价值
self.weight = weight # 已占用的重量
self.bound = bound # 价值上界
def knapsack(weights, values, capacity):
n = len(weights)
# 按单位价值降序排列（贪心界的前提）
items = sorted(range(n), key=lambda i: values[i] / weights[i], reverse=True)
def compute_bound(node):
if node.weight >= capacity:
return 0
value, weight, level = node.value, node.weight, node.level
while level < n and weight + weights[items[level]] <= capacity:
weight += weights[items[level]]
value += values[items[level]]
level += 1
if level < n: # 装不下的物品按比例折算
value += (capacity - weight) * values[items[level]] / weights[items[level]]
return value
pq = PriorityQueue()
root = Node(0, 0, 0, 0)
root.bound = compute_bound(root)
pq.put((-root.bound, root))
best = 0
while not pq.empty():
node = pq.get()[1]
if node.bound <= best:
continue # 上界不优于当前最优，剪枝
i = node.level
if i >= n:
continue
idx = items[i]
# 选择装入当前物品
if node.weight + weights[idx] <= capacity:
child = Node(i + 1, node.value + values[idx],
node.weight + weights[idx], 0)
child.bound = compute_bound(child)
if child.value > best:
best = child.value
if child.bound > best:
pq.put((-child.bound, child))
# 不装入当前物品
child = Node(i + 1, node.value, node.weight, 0)
child.bound = compute_bound(child)
if child.bound > best:
pq.put((-child.bound, child))
return best
print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 5)) # 输出 7
注意Python标准库的PriorityQueue默认是小顶堆，所以代码里对bound取了负数来模拟大顶堆，保证每次优先扩展上界最大的节点。这种最佳优先的搜索顺序能让算法尽快逼近最优解，一旦最优解被找到，剩余节点会因为上界不足而被大量剪掉。
使用分支限界法需要注意什么
第一，界限函数的质量直接决定算法性能。界限估计得太松，剪枝效果差，算法退化为近似枚举；估计得太紧，每个节点的计算成本又会上升。实践中通常先采用简单快速的界，在性能不满足时再逐步精细化。
第二，分支限界法并不能改变问题的复杂性类别。对于NP难问题，最坏情况下它仍然需要指数级时间，只是对绝大多数具体实例能显著加速。如果输入规模特别大且要求实时响应，应该考虑动态规划、近似算法或启发式算法作为替代方案。
第三，初始解的获取很重要。如果在搜索开始前就能通过贪心或其他启发式方法得到一个较优的可行解，后续剪枝会从一开始就非常高效。这也是工程实现中常见的优化技巧，值得在写代码时主动运用。