0/1 knapsack · best-first

拆解 branch & bound：从 2ⁿ 暴力到 bound 剪枝

阅读前，了解 binary heap (priority queue) 与 A* 搜索会有帮助：前者是「取 bound 最大的活节点」依赖的容器，后者与分支限界同源。全文四节：为什么需要剪枝 → 乐观界 + priority queue 剪枝 → 和 A* 的关系 → 真实应用。每节都能单步观察决策树的展开、bound 的计算，以及子树被剪的过程。

1 · 为什么需要剪枝：2ⁿ 棵子树的暴力

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

读这棵树：从根往下，第 1 层决定物品 A、第 2 层决定 B……每个叶子就是一个完整方案（每件都已拍板）。n 件物品 → ${2^n}$ 个叶子。实线「选」/ 虚线「弃」。节点里的数 = 到此已装价值，下方 $v\cdot w$ = 累计价值/重量；红色 ✗ = 超重不可行。暴力法 = 把每个叶子都算一遍、留下其中可行且价值最大的那个。

1.1 · 叶子数 = 2ⁿ：暴力为什么不可行

上面只有 4 件物品、16 个叶子。但叶子数是指数增长的——拖动滑块观察 n 增大时它的规模 (假设一台每秒能枚举 十亿 (10⁹) 个方案的机器):

所以暴力枚举只在 n 很小时才可行。分支限界的做法是：不走到每个叶子——在树的中间层就给整棵子树估一个乐观上界，达不到已知最好解的子树提前剪掉。「乐观界 + priority queue 剪枝」一节给出这个界的算法。

2 · 核心：乐观界 + priority queue 剪枝

本节沿用「指数级决策树」的 0/1 背包决策树模型。分支限界 = 分支 (branch) + 限界 (bound)。分支 = 在决策树上展开「选 / 不选」；限界 = 给每个节点算一个 bound——这棵子树再走运也只能到多好的乐观估计。一旦某节点的 $bound \le 当前已知最好解 best$ ，它和它整棵子树就再无翻盘可能 → 一刀剪掉，省下指数级的枚举。

背包的 bound 怎么算（LP 松弛上界）：站在某个节点（已决定了前几件、装了 value、占了 weight），把剩下的物品按性价比从高到低往剩余容量里塞；最后一件装不下时允许切一块塞满。这个「可切分背包」的解一定 ≥ 真实 0/1 解——所以是合格的乐观上界（永不低估），剪枝才安全。

**挑谁先探？**用 priority queue 每次 pop 出 bound 最大的活节点 (best-first)——最有希望的方向先走，往往很快就逼出一个高 best，后面的子树就更容易被剪。

**观察这一小片树。**完整决策树有 31 个节点、16 个叶子；分支限界往往只生成其中少数几个，大片子树尚未展开就被 bound 排除。这正是它能处理 NP 难问题实际实例的原因——解空间仍是指数级，但大多数指数子树被挡在搜索之外。

**bound 越紧，剪得越多。**这里用的「可切分背包」是一个较紧的界；界若较松（例如直接用「剩余物品总价值」），剪枝就少，退化回接近暴力枚举。设计一个既紧又易计算的 bound，是分支限界的关键——不同问题（TSP、调度）各有各的界。

两个 best-first demo 可对照来看：本节用 priority queue 取 bound 最大的活节点，「和 A* 的关系」一节则把这套骨架与 A* 的「取 f 最小」并排比较。

3 · 分支限界和 A* 的关系

本节假设已读过「乐观界 + priority queue 剪枝」，并了解 A* 搜索。两者在「用 priority queue，按某个乐观估计挑下一个最该扩展的节点」这个骨架上几乎一致，因而容易混淆。区别在于那个估计是什么，以及在解什么问题。先给出结论，再逐项对照。

一句话：

分支限界解组合优化（背包 / TSP / 分配）,priority queue 里排的是 bound——子树「再走运能到多好」的乐观界。
A* 解图上最短路径,priority queue 里排的是 f = g + h——已走代价 + 剩余代价的启发估计。

3.1 · 逐项对照

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

3.2 · 同一个骨架，两种填法

把代码并排放，你会发现两者就是同一段 best-first 循环，只在「键是什么、取极大还是极小」处分叉：

3.3 · 对照：同一个 priority queue，方向相反

下面是 priority queue 里的 4 个候选节点。切换「镜头」：分支限界挑 bound 最大的（最有希望冲高价值）,A* 挑 f=g+h 最小的（最有希望省路程）。容器、骨架完全一样，只是取极大 vs 取极小。

3.4 · 本质关系：A* 是分支限界的一个特例

把 A* 的 f = g + h 看成什么？它正是「从起点经过 n 到终点的总代价」的一个乐观估计（界）——这恰恰就是 best-first 分支限界的 bound。所以 A* = 在「状态图最短路径」这个具体问题上、bound 取 g + h 形式的 best-first 分支限界。

反过来，分支限界更一般：它的 bound 不一定能拆成「已付出 g + 未来 h」这种可加结构（背包的可切分松弛上界就不是沿路径累加出来的），它要找的也不是「一条路径」而是「一组最优决策」。

两个最容易混的点：

其一，g 算不算？ A* 一定把已付出的真实代价 g 计入排序键；只看 h 的是贪心 best-first,不保证最优。分支限界的 bound 里通常也隐含「已确定部分的真实值 + 未确定部分的松弛值」，与 g+h 同源。

其二，剪枝 vs 不重复扩展：分支限界靠 $bound \le best$ 主动砍子树；A* 靠 admissible h 保证「目标出队即最优」，再靠 consistent h + closed 集做到「每点只扩展一次」——本质也是一种剪枝。

**两个 live demo 对着看：**本系列的「bound + 剪枝」（取 bound 最大、剪子树）与最短路径系列的 A* 网格寻路（取 f 最小、朝目标收窄）——底下那个「每次取极值」的容器，都是同一个 binary heap。

4 · 应用实例：有限预算，投哪些渠道收益最大？

这是个不折不扣的 0/1 背包：每个广告渠道有投放成本和预估收益，总预算有限，每个渠道要么投要么不投，求收益最大的组合。方案空间是 ${2^n}$ 个子集，暴力枚举随渠道数指数增长。分支限界给每个分支算一个乐观上界（可切分背包松弛，算法见「乐观界 + priority queue 剪枝」），凡「最乐观也超不过当前最优」的子树整片剪掉——往往只评估少数几个节点即可确定最优。

拖预算滑块，看最优投放组合（高亮）实时变化，底部对比分支限界评估的节点数 vs 暴力的 ${2^n}$ 。渠道按性价比（收益/成本） 排序——这正是 bound 之所以紧、剪枝之所以狠的关键。

为什么这么省？渠道按性价比排序后，乐观上界特别紧：把剩余预算「允许切分地」按性价比塞满得到一个绝不可能被超越的天花板；一旦某分支的天花板 ≤ 当前已知最优，它整棵子树（指数级方案）一次性被剪。详见「乐观界 + priority queue 剪枝」那节。

4.1 · 同一方法的其他应用

**和别的系列串起来看：**这里每次「取 bound 最大的活节点」靠的还是 binary heap；把 bound 换成 f = g + h、把「最大化价值」换成「最小化路径」，就变成了 A* 搜索。

5 · 它真实跑在哪里

整数规划求解器:Gurobi、CPLEX、Google OR-Tools 解 MILP（混合整数线性规划）的内核就是 branch-and-bound，叠加割平面即 branch-and-cut——这是运筹优化领域的主力引擎。

调度与分配：航空机组排班、车辆路径 VRP / 配送排线、生产排程、云资源装箱 bin-packing 求精确最优，最终都会落到 B&B / MILP。

组合优化：0/1 背包、集合覆盖、TSP 的精确解；EDA 芯片布局布线、编译器里的某些精确寄存器分配。

A 是它的特例*：把 bound 取成 f = g + h、目标从「最大化价值」换成「最小化路径」，best-first 分支限界就是地图导航 / 游戏寻路使用的 A* 搜索。