分支限界法：从思想到实战
分支限界法，说白了就是「有脑子的暴力搜索」。
我刚开始学算法时，总觉得它跟回溯法差不多。后来在项目中做路径规划，才真正体会到两者的区别——回溯是「一条路走到黑，不行就回头」，分支限界是「每走一步都看看，哪条路最有希望」。
嗯，今天我们就来聊聊这个思想，以及它在三个经典问题里的应用。
分支限界思想的核心
分支限界法有两个关键动作：分支和限界。
- 分支：把问题拆成若干子问题，每个子问题就是一个分支节点。
- 限界：对每个节点估算一个「上界」或「下界」，如果这个界比当前最优解还差，就直接剪掉。
你想想看，这就像面试时筛简历——先看学历，再看经验，如果第一轮就不达标，后面就不用看了。
关键区别：回溯法用深度优先，分支限界法通常用广度优先或优先队列（最佳优先）。
我个人习惯用优先队列来实现分支限界。为什么呢？因为每次都能挑出「最有潜力」的节点先扩展，往往能更快找到最优解。
旅行商问题（TSP）
TSP 问题：一个销售员要跑 n 个城市，每个城市只去一次，最后回到起点，求最短路径。
n 稍微大一点，比如 20 个城市，暴力枚举就是 20! 种可能——你算算，这数字比银河系的星星还多。
分支限界法怎么解？
- 从起点出发，每到一个城市就分支——选择下一个未访问的城市。
- 对每个部分路径，估算一个「下界」：当前已走距离 + 剩余城市的最小可能距离。
- 如果这个下界已经大于当前最优解，直接剪枝。
我在项目中遇到过类似问题——给机器人规划巡检路线，30 个点。用分支限界法，配合一个简单的下界函数，几秒钟就出结果了。要是用回溯法，跑半小时都停不下来。
小技巧：下界函数可以这样算——对每个未访问城市，取它到其他未访问城市的最短边，加起来除以 2。这个下界虽然不紧，但计算快，实际效果不错。
0-1背包问题（分支限界解法）
0-1 背包，大家应该不陌生。n 个物品，每个有重量和价值，背包容量有限，求最大价值。
动态规划能解，但物品重量很大时，DP 表会爆炸。这时候分支限界法就派上用场了。
思路是这样的：
- 按价值密度（价值/重量）从大到小排序。
- 每个节点表示「当前已选物品」和「当前总价值」。
- 分支：下一个物品选或不选。
- 限界：用「贪心+分数背包」算上界——假设剩下的物品可以按比例拿，算出一个理论最大值。
如果这个上界 ≤ 当前最优价值，剪掉。
// 分支限界解0-1背包的核心结构
typedef struct {
int level; // 当前处理到第几个物品
int weight; // 当前总重量
int value; // 当前总价值
double bound; // 上界
} Node;
// 计算上界函数
double bound(Node node, int n, int capacity,
int weights[], int values[]) {
if (node.weight >= capacity) return 0;
double profit_bound = node.value;
int j = node.level + 1;
int total_weight = node.weight;
// 贪心拿完整物品
while (j < n && total_weight + weights[j] <= capacity) {
total_weight += weights[j];
profit_bound += values[j];
j++;
}
// 最后一个物品拿一部分
if (j < n) {
profit_bound += (capacity - total_weight) *
(double)values[j] / weights[j];
}
return profit_bound;
}我曾经用这个解法处理过一个物流装箱问题——100 个包裹，卡车容量有限。分支限界法配合优先队列，比纯贪心多装了 12% 的货值。
注意：分支限界法虽然快，但最坏情况仍然是指数级。如果物品数量超过 50，建议先用启发式算法找近似解，再用分支限界做精确优化。
装载问题
装载问题：有两艘船，载重量分别为 c1 和 c2，有 n 个集装箱，每个重量为 w[i]。问能否把所有集装箱装上船？
这个问题可以转化为：第一艘船尽量装，剩下的给第二艘。说白了，就是找一个子集，总重量 ≤ c1，且尽可能大。
分支限界解法：
- 每个节点表示「当前已选集装箱的总重量」。
- 分支：下一个集装箱装或不装。
- 限界：当前重量 + 剩余所有集装箱重量。如果这个值 ≤ 当前最优解，剪掉。
你可能会问：「这跟回溯法有什么区别？」
区别在于搜索顺序。分支限界用优先队列，每次选「当前重量最大」的节点扩展——这样能更快逼近最优解，剪枝效率更高。
我记得有一次做港口调度，200 个集装箱，两艘船。用回溯法跑了 3 分钟没出结果，换成分支限界法，15 秒就找到了可行方案。
知识体系总览
下面这张图，帮你把分支限界法的核心逻辑串起来：
避坑指南
讲几个我踩过的坑：
- 下界太松：我曾经给 TSP 问题写了一个很粗糙的下界函数，结果剪枝效率极低，跑得比暴力还慢。后来改用「最小生成树」做下界，速度快了 10 倍。
- 优先队列的排序：0-1 背包里，按上界从大到小排序。但要注意——上界相同的节点，优先选 level 大的（更接近叶子节点），这样能更快更新最优解。
- 内存爆炸：分支限界法会生成大量节点。如果问题规模大，建议限制队列大小，或者用迭代加深的方式控制。
我的建议：初学者先拿 0-1 背包练手，因为它的上界函数好理解，调试也方便。等熟练了，再挑战 TSP 和装载问题。
分支限界法，说白了就是「聪明地穷举」。它不像动态规划那样需要完美的状态转移方程，也不像贪心那样可能错过最优解。它给你一个平衡点——在时间和最优性之间做取舍。
嗯，今天就聊到这里。代码多写几遍，你自然就找到感觉了。