6.5 分支限界法：带着预算的搜索
6.5 分支限界法：带着预算的搜索
本节摘要：分支限界在回溯的搜索树上加装"估价器"：每个节点算一个乐观上界，一旦上界不超当前已知最好解，整棵子树剪掉。与回溯剪"不可能"（可行性）不同，限界剪"不划算"（最优性）。本节在 0-1 背包上实测：同一最优解，纯回溯十八个节点、限界后五个节点；并说明最优优先（best-first）队列版与 DFS 版的取舍。
回溯的遗憾：走完了才知道白走
上一节的回溯靠可行性剪枝（冲突即剪），但对最优化问题还有一类更狠的浪费：一条分支在数学上注定不如已知解，回溯却要把它走到叶子才死心。分支限界补上这一刀：
- 分支：与回溯相同，把决策树展开（带或不带第 i 件物品、放或不放这个皇后）；
- 限界：给每个节点算一个乐观估计 bound——假设此后一切顺利（剩余容量全装性价比最高的物品、甚至允许拆开装），最好能到多少。若 bound 不大于当前已知最优解 best，这条子树不可能翻盘，剪。
一句话分工：回溯剪掉"不可能"，限界剪掉"不划算"。两者常常同框出现：先查可行性，再查上界。
同一棵树的两种走法
# 0-1 背包：纯回溯 vs 限界剪枝，节点数对决 def solve(cap, items, prune): n = len(items) best, nodes = [0], [0] dens = sorted(range(n), key=lambda i: -items[i][1] / items[i][0]) # 按性价比排序 def bound(i, w, v): # 乐观上界：剩余按性价比装，最后一件可拆 b, cw = v, cap - w for idx in dens: if idx < i: continue iw, iv = items[idx] if iw <= cw: cw -= iw; b += iv else: b += cw * iv / iw # 拆开装：0-1 背包不许，但作为上界成立 break return b def rec(i, w, v): nodes[0] += 1 best[0] = max(best[0], v) if i == n: return if prune and bound(i, w, v) <= best[0]: return # 不划算：整棵子树放弃 iw, iv = items[i] if w + iw <= cap: # 可行性剪枝：装不下就不带 rec(i + 1, w + iw, v + iv) rec(i + 1, w, v) rec(0, 0, 0) return best[0], nodes[0] cap, items = 5, [(2, 3), (3, 4), (4, 5), (5, 6)] print("纯回溯：最优值与节点数 =", solve(cap, items, prune=False)) print("限界剪枝：最优值与节点数 =", solve(cap, items, prune=True)) # 输出： # 纯回溯：最优值与节点数 = (7, 18) # 限界剪枝：最优值与节点数 = (7, 5) # 同一个最优解 7（带重量 2 与 3 的两件），节点从 18 降到 5
bound 的设计是整门功法的要害：它必须是真解的上界（乐观），又要尽量紧（剪得准）。背包用"允许拆装的松弛版"当上界——松弛问题放宽了约束，最优值必然不小于原问题，作为上界合法；拆装版又恰好能用贪心线性解出（6.3 节的既证结论），上界算得快。松弛求界是运筹学的通用手法。
搜索顺序：DFS 限界与最优优先
上面的实现是 DFS 式限界：一路扎到底先拿一个可行解垫底（best 有值可依），回程时用上界剪枝。另一种流派是最优优先：所有活节点进优先队列（3.4 节的堆），每次弹出上界最大的节点展开——像"最有希望的方向先走"，通常更早触达最优解、队列里活节点更少，代价是堆维护与内存。
| 维度 | DFS 限界（回溯式） | 最优优先（队列式） |
|---|---|---|
| 数据结构 | 递归栈 | 优先队列（堆） |
| 找到首个可行解 | 快（一路到底） | 慢（要排队） |
| 剪枝时机 | 回程时（需 best 垫底） | 展开前（天然拿到最大上界） |
| 内存 | O(深度) | O(活节点数)，可能很大 |
| 典型用途 | 找全部解、深树 | 只要最优解、如旅行商 |
最优优先版把"往下走哪条"交给堆决定，代码骨架反而更短——堆顶就是全体活节点里上界最乐观的那个，一旦它都翻不了盘，剩下的可全体弃权：
# 最优优先分支限界：堆顶永远是上界最乐观的活节点 import heapq def knapsack_bestfirst(cap, items): n = len(items) order = sorted(range(n), key=lambda i: -items[i][1] / items[i][0]) # 性价比降序 def bound(i, w, v): # 松弛上界：与上文同款 b, cw = v, cap - w for idx in order: if idx < i: continue iw, iv = items[idx] if iw <= cw: cw -= iw; b += iv else: b += cw * iv / iw break return b best, pops = 0, 0 heap = [(-bound(0, 0, 0), 0, 0, 0)] # 存负号：把大根堆伪装成小根堆 while heap: negb, i, w, v = heapq.heappop(heap) pops += 1 if -negb <= best: # 最乐观的上界都翻不了盘：终止 break best = max(best, v) if i == n: continue iw, iv = items[i] if w + iw <= cap: # 分支一：带第 i 件 heapq.heappush(heap, (-bound(i + 1, w + iw, v + iv), i + 1, w + iw, v + iv)) heapq.heappush(heap, (-bound(i + 1, w, v), i + 1, w, v)) # 分支二：不带 return best, pops cap, items = 5, [(2, 3), (3, 4), (4, 5), (5, 6)] print("最优优先：最优值与弹出次数 =", knapsack_bestfirst(cap, items)) # 输出：最优优先：最优值与弹出次数 = (7, 4) # 对照上文 DFS 限界的 (7, 5)：少弹一次，且第四次弹出即知全树无望、整体收工
⚠️ 常见坑：上界算小了。bound 若可能低于真最优解（比如忘了允许拆装、或只按整数装），剪枝会误杀最优分支，返回的"最优"是错的。上界只许高估，剪枝条件用"小于等于 best 才剪"，边界保守一点不亏。
💡 关键直觉：分支限界 = 回溯 + 一张"最乐观能赚多少"的估价表。估价越准，走得越少；估价免费的话，剪枝永远划算——前提是它真的是上界。
走火入魔：两起限界事故
**事故一：没有垫底解就开始剪。**best 一开始是零或负无穷时，限界条件几乎不触发（或过度触发），白算上界。DFS 版先快速下沉拿一个贪心可行解初始化 best，是标准起手。
**事故二：解空间忘了排序。**按性价比预先排列物品，同样的限界逻辑剪枝效率天差地别——高性价比分支先走，best 迅速抬高，后续剪枝更狠。搜索顺序本身就是启发式。
本节要点回顾
- 分支限界 = 分支搜索 + 上界剪枝：回溯剪"不可能"（可行性），限界剪"不划算"（最优性）；
- 上界三性：必须是真解的上界（乐观）、要紧（剪得准）、要便宜（松弛问题可快解）；
- 背包实测：同一最优值，纯回溯十八个节点对限界五个节点，放大后差距指数级；
- 两种走法：DFS 限界省内存、先得可行解；最优优先用堆弹"最有希望"的节点，常更早触顶；
- 工程起手式：贪心解垫底 best、物品按性价比排序、剪枝条件保守写。
五套范式至此齐备。下一章进入高阶兵器库：并查集、线段树、字符串匹配与位运算——它们全是前六章心法的组合应用。