算法设计第 6 章：分支限界法——队列式与优先队列式的最优解搜索

写于 2026-11-01

回溯法找的是"所有解"或"一个可行解"，分支限界法找的是一个最优解，而且要求尽快找到。它和回溯共用同一棵解空间树，区别只在遍历顺序：回溯是深度优先、一条路走到黑；分支限界是广度优先或最佳优先，用活结点表管理待扩展的结点，用界函数整片整片地杀掉不可能更优的子树。这一章的核心不是模板，而是界函数怎么设计得既正确又紧。

一、两种组织方式：队列式与优先队列式

队列式（FIFO）分支限界：活结点表用普通队列，按入队顺序扩展，等价于 BFS。优点是实现简单、同一层结点一起处理，适合"求最短步数"类问题（布线问题）；缺点是不区分好坏，可能先扩展了大量劣质结点。

优先队列式（LC，Least Cost）：活结点表用堆，每次取"当前代价最小"或"上界最大"的结点扩展。它总是沿着最有希望的方向深入，能在较少结点内找到最优解，但每个结点要算界值、维护堆，单结点开销更大。

维度	队列式 FIFO	优先队列式 LC
活结点表	队列	小顶堆 / 大顶堆
扩展顺序	按层（BFS）	按界值（最佳优先）
单结点开销	低	高（算界 + 堆调整）
找到最优解的结点数	多	少
典型问题	布线、最少步数	0-1 背包、TSP、作业调度

两种方式都遵循同一套流程：从活结点表取结点 → 一次性生成全部儿子 → 对每个儿子算约束与界 → 剪掉不可行与不优的 → 剩下的加入活结点表。一次扩展全部儿子是它与回溯最本质的实现差异（回溯一次只走一个儿子）。

二、与回溯法的区别及适用场景

对比项	回溯法	分支限界法
搜索方式	深度优先（栈 / 递归）	广度优先或最佳优先（队列 / 堆）
扩展方式	逐个儿子深入	一次生成全部儿子
目标	所有解 / 任一可行解	一个最优解
存储	O(递归深度)	O(活结点数)，最坏 O(2ⁿ)
剪枝	约束 + 限界	约束 + 限界（界函数更关键）
空间	省	费

判据很直接：要枚举全部方案（如 n 后求 92 个解、着色求所有方案）用回溯；只要一个最优值（如背包最大价值、TSP 最短回路）用分支限界。若解很深而最优解在浅层，分支限界优势明显；若内存紧张，回溯更稳。

三、单源最短路径与布线问题

单源最短路径的分支限界解法：以源点为根，每个活结点代表一条"从源点到某顶点"的路径，界值就是该路径当前长度。每次取界值最小的结点扩展，松弛其邻边。这实际上就是 Dijkstra 算法——Dijkstra 可以看作优先队列式分支限界在单源最短路上的特化。复杂度 O((n+m) log n)（堆实现）。

布线问题：在 m×n 的网格上从起点 a 到目标 b 找最短布线路径，障碍格不可通过。这是无权图的最短路径，用队列式分支限界（即 BFS）逐层扩展，每个格子记录"前驱"以便回溯路径。复杂度 O(mn)，空间 O(mn)。

这里体现了两者的分工：无权/等权用队列式（BFS 天然按层给出最短），带权用优先队列式。

四、0-1 背包与最大团的界函数设计

0-1 背包：结点表示"前 i 件已决定"，界值 ub = 当前价值 cv + 剩余物品按单位价值降序贪心填满所得价值（最后一件可取小数）。用大顶堆按 ub 取最大者扩展，当某叶子的 cv 超过当前最优 bestp 时更新；当堆顶的 ub ≤ bestp 时，整堆都不可能有更优解，直接终止。这是分支限界能提前结束的理论依据。

最大团：在无向图中找点数最多的完全子图，解空间是子集树。

约束：新顶点必须与当前团中所有顶点相邻，否则剪。
界：设已选 cn 个、还剩 n−i 个待考察，若 cn + (n − i) ≤ bestn 则剪——即使剩下的全选也超不过当前最优。

界函数的质量直接决定搜索量。最大团若只用"剩余顶点数"这种粗界，剪枝很弱；改用着色上界（对剩余子图做贪心着色，颜色数即为团的上界）能把规模推高一个数量级。

五、旅行商问题与作业调度

旅行商问题（TSP）：从某城出发遍历所有城市一次并回到起点，求最短回路。解空间是排列树（(n−1)! 个叶子）。

约束：当前路径的下一个城市未访问过。
界：lb = 已走路径长度 + 未访问城市的最小出边之和（每个未访问城市至少要出去一次），若 lb ≥ bestc 则剪。
更强的界：用剩余子图的最小生成树下界，但每个结点要多花 O(n²)，需要权衡。

批处理作业调度（n 个作业在三台机器 M1、M2、M3 上同序加工，求完成时间和最小）：排列树，优先队列按"当前完成时间之和 + 剩余作业最短加工时间和"取最小。这是下界，用于淘汰那些已经比当前最优还差的结点。

注意界的两个方向：求最小化问题时用下界 lb 剪（lb ≥ best 则剪），求最大化问题时用上界 ub 剪（ub ≤ best 则剪）。方向搞反是本章最常见的错误。

六、实现要点

结点结构要存足够信息以 O(1) 算界：当前层号、当前代价、已选集合（位向量）、父指针（用于回溯构造方案）。
入堆前先剪：算界在入堆前做，别把注定被剪的结点塞进堆里再取出来。
终止条件：优先队列式在"堆顶界值已不优于当前最优"时即可停，不必等堆空。
空间控制：活结点最坏 O(2ⁿ)，大规模实例要考虑分支限界 + 深度限制（即迭代加深）。

易错点

界函数不可采纳（低估下界或高估上界），剪掉最优解。
求最大问题却用 lb ≥ best 剪枝，方向写反。
优先队列式忘记在所有儿子入堆后再判终止，导致多扩展大量结点。
布线问题用优先队列而非队列，虽然结果对但多花 log 因子。
只在叶子更新最优解，没有在内部结点用界提前终止。

这一章在整门课里的位置

本章与第 5 章是同一枚硬币的两面，共用解空间树与剪枝函数的设计方法，只是遍历次序不同。它的界函数设计直接借用第 3 章动态规划的松弛思想（背包的小数松弛）与第 4 章贪心的构造（按单位价值填满）。第 10 章的 A 与 IDA 可以看作"带启发函数的优先队列式分支限界"，本质上仍是本章框架。

本文是《算法设计与分析（89 讲）》第 6 章的知识点摘要。完整板书与代码见课程页；上一章回溯法，下一章概率算法。