0/1 knapsack · best-first

分支限界的拆解

阅读前了解 binary heap 与 A* 搜索会有帮助：前者是「取 bound 最大的活节点」所依赖的容器，后者与分支限界同源。

1 · 指数级决策树

全文用一个具体问题贯穿：0/1 背包。给定一组物品，各有价值与重量，以及一个容量上限，挑一个子集塞进背包，在不超重的前提下让总价值最大。每件物品只有选与不选两种结局，把这些决定一层层摊开就是一棵二叉决策树。

图 1-1 · 4 件物品的完整决策树。第 1 层决定物品 A、第 2 层决定 B，依此类推；实线为选、虚线为弃，节点内的数是到此已装价值，下方标出累计价值与重量，红叉表示超重不可行。每个叶子是一个完整方案。

$n$ 件物品给出 $2^n$ 个叶子。图 1-1 只有 4 件物品，叶子 16 个、节点 31 个；但叶子数按指数增长，暴力枚举很快不可行。

图 1-2 · 叶子数随

n

的增长，按每秒枚举十亿个方案的机器折算所需时间。可拖动

n

观察规模变化。

分支限界的做法是不走到每个叶子，而在树的中间层就给整棵子树估一个乐观上界，达不到已知最好解的子树提前剪掉。

2 · 乐观界与 best-first 剪枝

分支限界由分支（branch）与限界（bound）两部分组成。分支是在决策树上展开选与不选；限界是给每个节点算一个 bound，即这棵子树再走运也只能到多好的乐观估计。一旦某节点的 bound 不超过当前已知最好解，它和它整棵子树就再无翻盘可能，可以一刀剪掉。

背包的 bound 用 LP 松弛给出。站在某个节点上，已决定了前几件、装了若干价值、占了若干重量，把剩下的物品按性价比从高到低往剩余容量里塞，最后一件装不下时允许切一块塞满。这个可切分背包的解一定不小于真实的 0/1 解，因而是合格的乐观上界，永不低估，剪枝才安全。

挑谁先探则交给 priority queue：每次弹出 bound 最大的活节点，即 best-first。最有希望的方向先走，往往很快逼出一个高的已知最好解，后面的子树也就更容易被剪。

图 2-1 · 同一棵决策树上的 best-first 分支限界。可单步执行，观察每个节点的 bound 如何算出、哪些子树在展开前就被 bound 排除。

图 2-1 的完整决策树有 31 个节点、16 个叶子，分支限界往往只生成其中少数几个。解空间仍是指数级，但大多数指数子树被挡在搜索之外，这正是它能处理 NP 难问题实际实例的原因。

警示 · bound 越紧剪得越多。本页用的可切分背包是一个较紧的界；界若较松，例如直接取「剩余物品总价值」，剪枝就少，退化回接近暴力枚举。设计一个既紧又易计算的 bound 是分支限界的关键，不同问题各有各的界。

3 · 与 A* 的关系

分支限界与 A* 在「用 priority queue、按某个乐观估计挑下一个最该扩展的节点」这个骨架上几乎一致，因而容易混淆。区别在于那个估计是什么，以及在解什么问题。分支限界解组合优化，队列里排的是 bound，即子树再走运能到多好的乐观界；A* 解图上最短路径，队列里排的是 $f = g + h$ ，即已走代价加剩余代价的启发估计。

3.1 · 逐项对照

维度	best-first 分支限界	A*
解的对象	解空间决策树，一串「选或不选、第 $k$ 步放哪」的决定	状态图，节点是状态、边是转移代价
队列排序键	bound：当前部分解经松弛能达到的最优目标值	$f = g + h$
键怎么构成	通常只有未来的乐观估计，来自 LP 或贪心松弛	已花费的 $g$ 加未来估计 $h$ ，二者相加
优化方向	最大化取上界、最小化取下界；本页取 bound 最大	最小化，取 $f$ 最小
界与启发的要求	bound 须是真最优的乐观估计，不低估能达到的最优，剪枝才安全	$h$ admissible（不高估）保证最优，consistent 保证每点只扩展一次
核心动作	剪枝：bound 不优于已知最好解即剪去整棵子树	松弛：更新邻居的 $g$ ，按 $f$ 重排
记已访问状态	一般不需要，树结构下路径天然不重复	需要 closed 集或距离表，图里同一状态有多条路径汇聚
终止	队列空，或队首 bound 已不优于现有最好解	目标节点出队时

图 3-1 · 两者的代码并排。同一段 best-first 循环，只在「键是什么、取极大还是极小」两处分叉。

图 3-2 · 同一个 priority queue 里的 4 个候选节点在两种镜头下的取法。可切换镜头，观察分支限界取 bound 最大而 A* 取

f = g + h

最小。

把 A* 的 $f = g + h$ 看作「从起点经该节点到终点的总代价」的乐观估计，它正是 best-first 分支限界的 bound。因此 A* 可以看作在「状态图最短路径」这个具体问题上、bound 取 $g + h$ 形式的分支限界。反过来分支限界更一般：它的 bound 不一定能拆成「已付出的 $g$ 加未来的 $h$ 」这种可加结构，背包的可切分松弛上界就不是沿路径累加出来的；它要找的也不是一条路径，而是一组最优决策。

警示 · 两处最容易混。其一， $g$ 算不算：A* 一定把已付出的真实代价 $g$ 计入排序键，只看 $h$ 的是贪心 best-first，不保证最优；分支限界的 bound 里通常也隐含「已确定部分的真实值加未确定部分的松弛值」，与 $g + h$ 同源。其二，剪枝与不重复扩展是两件事：分支限界靠 bound 不优于已知最好解主动砍子树，A* 靠 admissible 的 $h$ 保证目标出队即最优，再靠 consistent 的 $h$ 配 closed 集做到每点只扩展一次，后者本质上也是一种剪枝。

4 · 预算分配实例

每个广告渠道有投放成本与预估收益，总预算有限，每个渠道要么投要么不投，求收益最大的组合。这是一个不折不扣的 0/1 背包，方案空间是 $2^n$ 个子集。分支限界给每个分支算一个乐观上界，凡「最乐观也超不过当前最优」的子树整片剪掉，往往只评估少数几个节点即可确定最优。

图 4-1 · 有限预算下的渠道投放组合。可拖动预算滑块观察最优组合的变化，底部对比分支限界实际评估的节点数与暴力枚举的

2^n

。渠道按性价比排序，这正是 bound 之所以紧的关键。

省下来的开销来自界的紧度：渠道按性价比排序后，把剩余预算允许切分地按性价比塞满，得到一个绝不可能被超越的天花板；一旦某分支的天花板不优于当前已知最优，它整棵子树的指数级方案一次性被剪。

图 4-2 · 同一方法在其他组合优化问题上的形态对照。

5 · 工程落地

整数规划求解器是最主要的落地：Gurobi、CPLEX 与 Google OR-Tools 解混合整数线性规划（MILP）的内核就是 branch-and-bound，叠加割平面即 branch-and-cut，这是运筹优化领域的主力引擎。调度与分配类问题同理，航空机组排班、车辆路径规划、生产排程、云资源装箱求精确最优，最终都会落到 B&B 或 MILP。此外还有 0/1 背包、集合覆盖、TSP 的精确解，以及 EDA 芯片布局布线与编译器里某些精确寄存器分配。

注 · 本页每次「取 bound 最大的活节点」靠的仍是 binary heap；把 bound 换成 $f = g + h$ 、把最大化价值换成最小化路径，就得到地图导航与游戏寻路使用的 A* 搜索。同一个取极值的容器，两种填法。