分支定界算法¶

约 1411 个字 58 行代码预计阅读时间 11 分钟

分支定界（Branch and Bound, B&B）是一类处理组合优化问题的通用求解框架。它的目标往往是那些没有已知多项式算法、只能靠搜索的问题：0/1 背包、旅行商问题（TSP）、作业分派、整数规划等等。这些问题的解空间通常是指数级的，但分支定界通过「剪枝」避开大量注定无望的搜索子树，在实际数据上常常比朴素的枚举快几个数量级。

基本思想¶

分支定界可以看作是「带剪枝的搜索树遍历」。它把解空间组织成一棵隐式的搜索树：树根代表尚未做任何决策的状态，每向下一层就是对一个决策变量做一次赋值，叶子节点对应一个完整的可行解。

这棵搜索树的节点数是指数级的，但分支定界并不真的把它全部展开。每当访问一个节点时，它会计算一个界（bound）——一个对「以此节点为根的子树中能得到的最优解」的乐观估计。如果这个乐观估计都已经比当前已知的最好解更差，就直接剪掉整棵子树，根本不必往下搜。

把这个思想拆解一下，分支定界包含三个要素：

分支（Branching）：决定如何把当前子问题进一步分解成若干更小的子问题。通常是按某个决策变量的可能取值划分。
定界（Bounding）：对每个子问题计算一个代价下界（求最小）或上界（求最大）。松弛（relaxation）是最常见的定界手段——把难解的约束暂时放掉，求解松弛后的容易问题。
剪枝（Pruning）：如果某个子问题的界比当前最优解还差，就立即丢弃。

与回溯、DFS 的关系¶

分支定界和回溯法（backtracking）有紧密联系，都是搜索 + 剪枝，但有微妙区别：

回溯一般按 DFS 顺序遍历，剪枝依据往往是「约束违反」（infeasibility），目标通常是找到一个可行解或枚举所有可行解。
分支定界除了剪掉不可行的分支，还会用「界」剪掉虽然可行但不可能更优的分支。它更多用于求最优解。
分支定界不一定是 DFS。按「界最好」的顺序优先展开节点（Best-First Search, BFS 的优先队列版）是另一种常见策略。

简而言之：回溯是分支定界的特例；分支定界给搜索引入了「价值评估」，使得不同遍历顺序成为可能。

策略的选择¶

展开节点的顺序决定了分支定界的性格：

DFS（深度优先）：栈空间小、实现简单，但早期可能长时间卡在一条没希望的路径上才回退。
BFS（广度优先）：能更快找到接近最优的可行解，但节点爆炸时内存开销巨大。
最佳优先（Best-First / Least-Cost Search）：每次从「待处理节点队列」中取出界最好的那个展开，通常用优先队列实现。理论上能最早找到最优解，代价是节点比较开销。

工程实现里 DFS 和最佳优先的混合体最常见——先 DFS 快速得到一个不错的初始解（为后续剪枝提供一个紧的界），再用最佳优先精细搜索。

经典例题：0/1 背包的分支定界¶

以 0/1 背包为例演示分支定界的流程。给定 \(n\) 件物品、背包容量 \(W\)，最大化选中物品的总价值。

预处理：按「单位价值」\(v_i / w_i\) 降序排序物品，这样的顺序让松弛解（分数背包）能给出一个紧的上界。

分支：在搜索树的第 \(k\) 层对物品 \(k\) 做决策——「选」或「不选」。

定界：对于当前节点，假设前 \(k\) 件物品已经决定，剩余物品按单位价值从大到小装，直到装不下为止（可以切分装入——即松弛）。这个值是该子树上界的一个有效估计。

struct Item { int w, v; };

struct Node {
    int level;         // 当前已决策到第几层
    int profit;        // 已选物品的总价值
    int weight;        // 已选物品的总重量
    double bound;      // 上界估计
    bool operator<(const Node& o) const { return bound < o.bound; }   // 最大堆按上界
};

double compute_bound(const Node& u, int n, int W, vector<Item>& items) {
    if (u.weight >= W) return 0;
    double b = u.profit;
    int w = u.weight;
    int j = u.level + 1;
    while (j < n && w + items[j].w <= W) {
        w += items[j].w;
        b += items[j].v;
        ++j;
    }
    if (j < n) b += (W - w) * 1.0 * items[j].v / items[j].w;
    return b;
}

int knapsack_bb(vector<Item> items, int W) {
    int n = items.size();
    sort(items.begin(), items.end(),
         [](const Item& a, const Item& b) {
             return (double)a.v / a.w > (double)b.v / b.w;
         });

    priority_queue<Node> pq;
    Node u{-1, 0, 0, 0}, v;
    u.bound = compute_bound(u, n, W, items);
    pq.push(u);

    int best = 0;
    while (!pq.empty()) {
        u = pq.top(); pq.pop();
        if (u.bound <= best) continue;                // 剪枝
        if (u.level == n - 1) continue;

        // 分支 1：选第 (level+1) 件
        v.level  = u.level + 1;
        v.weight = u.weight + items[v.level].w;
        v.profit = u.profit + items[v.level].v;
        if (v.weight <= W && v.profit > best) best = v.profit;
        v.bound = compute_bound(v, n, W, items);
        if (v.bound > best) pq.push(v);

        // 分支 2：不选第 (level+1) 件
        v.weight = u.weight;
        v.profit = u.profit;
        v.bound  = compute_bound(v, n, W, items);
        if (v.bound > best) pq.push(v);
    }
    return best;
}

关键点：

排序让 compute_bound 的松弛解既快又紧。
优先队列按 bound 排序，实现最佳优先策略。
每次从队列取出节点后再次比较 bound <= best——因为在它入队之后，best 可能已经被更新到比它更大的值。

旅行商问题（TSP）¶

TSP 是经典的 NP-hard：给定 \(n\) 个城市两两之间的距离，求一条恰好访问每个城市一次并回到起点的最短回路。

分支：固定起点（例如 0），按访问顺序逐个把下一个城市加到部分路径中。

定界：当前路径已经走过的距离 + 对剩余城市构成的子问题的一个下界估计。常见的下界有： - 对未访问城市的最小生成树长度； - 对每个未访问城市，取它的两条最小出边的平均作为「必要代价」； - 对所有未访问城市的最小入/出边之和除以 2。

TSP 的分支定界在 \(n\) 几十到一百的规模上仍然可行，规模更大时需要 Held-Karp 动态规划（\(O(n^2 2^n)\)）或更复杂的启发式（LKH 等）。

一般流程¶

总结一下分支定界解题的通用流程：

定义搜索树：决定分支变量和节点状态。
设计界：计算要快、要尽量紧。松弛是最常见的思路——线性规划松弛、拉格朗日松弛、去掉某些约束。
维护当前最优：每找到一个更优的可行解就更新 best。
剪枝：bound <= best（最大化问题）或 bound >= best（最小化）时整棵子树丢弃。
选择展开策略：DFS、BFS、最佳优先。
尽早得到一个不错的可行解：初始的紧界能大幅提升剪枝效率。一种实用手法是先用贪心求一个可行解作为初始 best。

什么时候该用分支定界¶

分支定界的长处在于能给出最优解，这是一些启发式（模拟退火、遗传算法、贪心）做不到的。代价是最坏情况下仍然是指数级——对那些结构性不好、界估不紧的问题，B&B 可能退化到几乎等同于暴力枚举。

工程选型上可以按下面的顺序尝试：

问题规模小、结构简单 → 直接动态规划或暴力枚举；
问题 NP-hard 但规模中等、需要最优解 → 分支定界；
规模很大、只要近似最优解 → 启发式或元启发式；
能用线性规划 / 整数规划建模 → 交给现成求解器（CPLEX、Gurobi、SCIP）。

现成求解器本质上就是基于分支定界（加切割平面、加启发式），把工程化做到了极致。理解分支定界有助于写出更好的剪枝、更紧的界，也更能读懂求解器的行为。