分支限界法：从思想到装载问题的完整实践

分支限界法，说实话，是我在解决组合优化问题时最常用的武器之一。它和回溯法有点像，但目标完全不同——回溯法要找所有解，而分支限界法只找最优解。我当年刚接触时总觉得它俩差不多，直到在项目中栽了跟头才真正理解它们的区别。

分支限界法的基本思想

说白了，分支限界法就是「有策略地穷举」。它把问题的解空间组织成树形结构，然后一层层地搜索。但和回溯法不一样的是，它不会傻傻地走到底——它会用「限界函数」来砍掉那些不可能产生更优解的分支。

我个人习惯把它的核心步骤总结为三点：

• 分支：把当前节点扩展出所有子节点
• 限界：计算每个子节点的目标函数上界（或下界）
• 剪枝：如果某个节点的界限比当前最优解还差，直接扔掉

嗯，这里要注意：分支限界法通常用于求解最优化问题，比如最短路径、最大收益、最小成本这些。它和回溯法最大的区别在于——回溯法是深度优先，一条路走到黑；分支限界法是广度优先或按优先级扩展。

队列式分支限界 vs 优先队列式分支限界

这两种方式我都用过，各有各的适用场景。先说说它们的区别：

特性	队列式（FIFO）	优先队列式
节点扩展顺序	先进先出，按层遍历	按优先级（如界限值）出队
数据结构	普通队列	优先队列（堆）
搜索策略	广度优先	最佳优先
适用场景	解空间均匀，界限函数简单	需要快速找到最优解

队列式分支限界，说白了就是一层一层地搜。先处理完第1层的所有节点，再处理第2层。这种方式的好处是实现简单，但坏处是——如果最优解在很深的地方，你得等很久。

优先队列式分支限界，我更喜欢叫它「贪心式搜索」。每次从队列里挑出最有「希望」的节点来扩展。这个「希望」通常用界限函数来评估。我在项目中遇到的大多数优化问题，用优先队列式都能更快找到最优解。

装载问题：一个经典案例

装载问题，说白了就是：有一艘船，有若干个集装箱，每个集装箱有重量，船有最大载重量，问最多能装多少重量？

这个问题看起来简单，但它是0-1背包问题的变种，也是分支限界法的经典教学案例。我当年学的时候，老师就是用这个例子讲明白的。

问题描述：

• 有n个集装箱，重量分别为w₁, w₂, ..., wₙ
• 船的最大载重量为C
• 每个集装箱要么装要么不装（0-1决策）
• 目标：在不超过C的前提下，最大化总重量

用分支限界法解决装载问题的思路是这样的：

1. 把集装箱按重量从大到小排序（这样能更快剪枝）
2. 构建解空间树，每个节点代表一个决策（装或不装）
3. 计算每个节点的上界 = 当前已装重量 + 剩余集装箱中能装的最大重量
4. 如果上界 ≤ 当前最优解，剪枝

下面是我写的一个简化版实现，用优先队列式分支限界：

#include <stdio.h>
#include <stdlib.h>

// 节点结构
typedef struct {
    int level;      // 当前决策到第几个集装箱
    int weight;     // 当前已装总重量
    int bound;      // 上界
} Node;

// 优先队列（最小堆，按bound降序排列）
// 这里用数组模拟，实际项目中建议用堆
Node queue[1000];
int front = 0, rear = 0;

// 计算上界
int bound(Node node, int n, int C, int w[]) {
    int total = node.weight;
    int i = node.level + 1;
    // 贪心地装剩余集装箱
    while (i < n && total + w[i] <= C) {
        total += w[i];
        i++;
    }
    // 如果还有剩余，按比例装一部分（这里简化处理）
    if (i < n) {
        total += (C - total) * w[i] / w[i]; // 实际应为浮点，这里简化
    }
    return total;
}

// 分支限界主函数
int branchBound(int n, int C, int w[]) {
    int best = 0;
    
    // 根节点
    Node root = { -1, 0, 0 };
    root.bound = bound(root, n, C, w);
    queue[rear++] = root;
    
    while (front < rear) {
        Node curr = queue[front++];
        
        // 如果上界小于当前最优，剪枝
        if (curr.bound <= best) continue;
        
        // 到达叶子节点
        if (curr.level == n - 1) {
            if (curr.weight > best) {
                best = curr.weight;
            }
            continue;
        }
        
        // 扩展子节点
        // 1. 不装当前集装箱
        Node left = { curr.level + 1, curr.weight, 0 };
        left.bound = bound(left, n, C, w);
        if (left.bound > best) {
            queue[rear++] = left;
        }
        
        // 2. 装当前集装箱（如果不超过容量）
        if (curr.weight + w[curr.level + 1] <= C) {
            Node right = { curr.level + 1, 
                          curr.weight + w[curr.level + 1], 0 };
            right.bound = bound(right, n, C, w);
            if (right.bound > best) {
                queue[rear++] = right;
                if (right.weight > best) {
                    best = right.weight;
                }
            }
        }
    }
    
    return best;
}

int main() {
    int w[] = {40, 30, 25, 20, 15};
    int n = 5;
    int C = 100;
    
    int result = branchBound(n, C, w);
    printf("最大装载重量: %d\n", result);
    
    return 0;
}

知识体系总览

下面这张图是我自己画的，把分支限界法的核心脉络梳理了一遍。你看完应该能有个整体印象：

避坑指南

我曾经在做一个物流调度项目时，直接用队列式分支限界去解一个规模较大的装载问题。结果程序跑了两个小时还没出结果。后来我换成优先队列式，并且优化了bound函数的计算方式，15分钟就找到了最优解。

这里分享几个我踩过的坑：

• bound函数太粗糙：如果上界算得太松，剪枝效果差，搜索空间爆炸。我建议用贪心策略来估算上界。
• 忘记排序：装载问题中，先处理重量大的集装箱，能更快地逼近最优解，剪枝效率更高。
• 优先队列实现不当：用数组模拟优先队列在数据量大时性能很差。一定要用堆（heap）来实现。

分支限界法，说白了就是「聪明地穷举」。它不像回溯法那样一条路走到黑，也不像动态规划那样需要严格的状态转移方程。它介于两者之间——用限界函数来指导搜索方向，在解空间中快速定位最优解。我个人觉得，它是解决组合优化问题最实用的方法之一。

---

公众号:蓝海资料掘金营，微信deep3321