分支限界法：带约束的广度优先搜索

什么是分支限界法

分支限界法（Branch and Bound）是一种在解空间树上搜索问题解的算法，它通过广度优先或最小代价优先的方式探索节点，并利用限界函数提前剪去不可能产生最优解的分支，从而避免无效搜索。与回溯法的深度优先不同，分支限界法更适合求解最优化问题，如最短路径、最小耗费、最大收益等。

核心思想：把问题看作在一棵状态树中寻找满足约束的最优解。每一次“分支”都会生成若干子节点，扩展当前节点的所有可能选择；每一个节点包含一个“界限值”，如果该值不可能优于当前已找到的最优解，则“限界”剪枝，不再扩展该节点。

简单来说，分支限界法可以理解为带约束和剪枝的广度优先搜索。

为什么叫“带约束的广度优先搜索”

• 广度优先：算法在扩展节点时，按层或按优先级逐步生成子节点，与 BFS 的逐层展开类似。
• 带约束：每个节点不仅包含状态信息，还携带一个“代价/收益界限”。当扩展节点时，若其界限表明它不可能比已知最优解更好，就直接丢弃该节点（即剪枝），不会将其加入待处理队列。
• 目标明确：总是朝着可能包含最优解的方向优先搜索，利用界限值选择最有希望的节点最先扩展（若采用优先队列）。

这种“搜索 + 剪枝 + 优先扩展”的模式，使之成为求解组合优化问题的有力工具。

分支限界法的两种常见策略

1. 队列式（FIFO）分支限界法

采用普通队列管理活节点，严格按照层序扩展。每一次从队首取出一个节点，生成其所有子节点，将满足约束且界限优于当前最优的子节点加入队尾。当队列为空时，搜索结束。

特点：实现简单，但缺乏对“有希望节点”的优先判断，可能需要搜索较多节点。

2. 优先队列式（最小代价/最大收益）分支限界法

采用堆（优先队列）管理活节点，每次选择界限值最优（如代价最小或收益最大）的节点优先扩展。这样能更快地找到高质量解，从而更强的剪枝，减少总搜索节点数。通常用于求解最优化问题。

特点：搜索效率更高，很多实际问题（如旅行商、背包）都采用此策略。

算法通用步骤

1. 定义解空间树：确定问题的解如何表示为节点，以及分支的方式。
2. 设计限界函数：对于每个节点，计算其可能达到的最优收益（或最小代价）的估计值。这个估计值必须满足一定性质（如对于最大化问题，上界不小于真实最优值）。
3. 初始化：创建根节点，计算其界限，加入活节点表（队列或优先队列）。设置初始最优解为无穷差（或无穷大）。
4. 循环扩展：
   • 从活节点表中取出一个节点（若队列空则结束）。
   • 如果节点的界限差于当前最优解，直接丢弃（剪枝）。
   • 否则，检查该节点是否代表一个完整解？若是，更新当前最优解；若不是，产生它的所有子节点，对每个子节点计算界限，若满足约束且界限优于当前最优，则插入活节点表。
5. 输出最优解。

限界函数的设计要点

限界函数是分支限界法的灵魂。它必须满足：

• 高效性：计算速度快，否则得不偿失。
• 可行性：对于最大化问题，上限必须不小于该子树中任意叶子节点的真实值；对于最小化问题，下限不大于真实值。这样不会错误剪掉最优解。
• 紧致性：界限越接近真实可能值，剪枝效果越好。例如在0-1背包问题中，常使用贪心算法（可部分装入）求上界。

经典例题：0-1 背包问题

问题：给定 n 个物品，重量 w[i]，价值 v[i]，背包容量 C。要求选择若干物品装入背包，使得总重量不超过 C 且总价值最大。

解空间：每个物品选或不选，构成一棵二叉树。节点表示已对前 k 个物品做出决策，当前总重量 cw，当前总价值 cv。

限界函数（上界）：剩余容量按物品单位价值降序采用部分装入（即分数背包贪心），得到理想最大价值 ub = cv + 剩余容量能获得的最大价值。这个上界是真实最优值的上界（不会低估）。

优先队列策略：以 ub 为键值大顶堆，每次都扩展上界最大的节点，希望尽快找到高价值解，提升剪枝能力。

伪代码：

定义节点结构：(level, cw, cv, ub)
初始化根节点 level=0, cw=0, cv=0, ub=Bound(0,0,0)
最优解 best=0
活节点表采用大顶堆，按 ub 排序，插入根节点
while 堆不空：
    node = 堆顶弹出
    if node.ub <= best: 继续
    if node.level == n: 
        best = max(best, node.cv)
        continue
    // 左孩子：选择当前物品
    if node.cw + w[node.level] <= C:
        left_ub = Bound(node.level+1, node.cw + w[node.level], node.cv + v[node.level])
        if left_ub > best:
            插入 (level+1, cw+w[i], cv+v[i], left_ub)
    // 右孩子：不选
    right_ub = Bound(node.level+1, node.cw, node.cv)
    if right_ub > best:
        插入 (level+1, cw, cv, right_ub)
输出 best

其中 Bound(level, cw, cv) 计算的过程：从 level 开始，若当前物品重量可全部放入，则全取；否则放入部分使之填满。

示例：假设 n=4, C=7, w=[2,3,4,5], v=[3,5,6,10]，按单位价值排序后为 (5,10), (4,6), (3,5), (2,3)。优先队列扩展过程会迅速找到最优解价值 15（选物品1和3？实际计算），并剪掉大量节点。

经典例题：旅行商问题（TSP）

问题：给定城市距离矩阵，找一条经过所有城市恰好一次并回到出发点的最短回路。

解空间：排列树，节点表示已确定的部分路径。限界函数通常用当前已走距离 + 剩余未访问城市的最小生成树（或下界估计）。

界限设计：一个简单有效的下界是 lb = 当前路径长度 + Σ(每个未访问城市的最小关联边长的一半) 或采用归约矩阵法，保证是任何完整回路的下界。

优先队列：每次选择下界最小的节点扩展，快速找到较短回路，利用当前最短回路长度剪枝。

分支限界法 vs. 回溯法

总结

分支限界法将 BFS 的层级扩展与智能剪枝结合，通过为每个状态计算一个乐观/悲观界限，只探索有可能改善当前最优解的节点。对于最优化问题，它是比回溯法更高效的选择。掌握其关键在于如何根据具体问题设计出既简单又紧致的限界函数，使算法在解空间中精准剪枝，快速收敛到最优解。