分支限界算法详解（Python实现组合优化问题的高效解法）

核心思想

• 分支（Branching）：将问题分解为若干子问题（通常形成树状结构）。
• 剪枝（Pruning）：若某子问题的界不优于当前最优解，则丢弃该分支。

实战：用Python解决0-1背包问题

我们以经典的0-1背包问题为例：给定容量为W的背包和n个物品（每个有重量w[i]和价值v[i]），如何选择物品使总价值最大且总重量不超过W？

步骤1：定义问题数据结构

class Node:    def __init__(self, level, profit, weight, bound):        self.level = level      # 当前考虑第几个物品（从0开始）        self.profit = profit    # 当前已选物品的总价值        self.weight = weight    # 当前已选物品的总重量        self.bound = bound      # 该节点的上界（最大可能价值）

步骤2：计算上界（Bound）

上界用于判断是否值得继续探索该分支。我们采用贪心策略：先装满整件物品，最后一件可分割（虽然实际不能分，但这样得到的是理论最大值）。

def calculate_bound(node, n, W, items):    if node.weight >= W:        return 0  # 超重，无价值        bound = node.profit    total_weight = node.weight    j = node.level + 1        # 贪心添加剩余物品（允许分割最后一项）    while j < n and total_weight + items[j][0] <= W:        total_weight += items[j][0]        bound += items[j][1]        j += 1        # 如果还有空间，添加部分下一个物品    if j < n:        bound += (W - total_weight) * items[j][1] / items[j][0]        return bound

步骤3：主算法实现

import heapqdef knapsack_branch_and_bound(W, weights, values):    n = len(weights)    # 按价值密度（value/weight）降序排序    items = sorted([(weights[i], values[i]) for i in range(n)],                    key=lambda x: x[1]/x[0], reverse=True)        max_profit = 0    # 使用最大堆（Python heapq是最小堆，所以存负值）    pq = []        # 初始化根节点    root = Node(-1, 0, 0, 0)    root.bound = calculate_bound(root, n, W, items)    heapq.heappush(pq, (-root.bound, root))        while pq:        _, current = heapq.heappop(pq)                # 如果当前界小于等于已知最大利润，跳过（剪枝）        if current.bound <= max_profit:            continue                    # 到达叶子节点        if current.level == n - 1:            continue                    # 分支：考虑包含下一个物品        next_level = current.level + 1        w, v = items[next_level]                # 选择当前物品        with_item = Node(next_level,                          current.profit + v,                          current.weight + w,                          0)        if with_item.weight <= W:            if with_item.profit > max_profit:                max_profit = with_item.profit            with_item.bound = calculate_bound(with_item, n, W, items)            if with_item.bound > max_profit:                heapq.heappush(pq, (-with_item.bound, with_item))                # 不选择当前物品        without_item = Node(next_level,                             current.profit,                             current.weight,                             0)        without_item.bound = calculate_bound(without_item, n, W, items)        if without_item.bound > max_profit:            heapq.heappush(pq, (-without_item.bound, without_item))        return max_profit

步骤4：测试代码

# 测试数据weights = [10, 20, 30]values = [60, 100, 120]capacity = 50result = knapsack_branch_and_bound(capacity, weights, values)print(f"最大价值: {result}")  # 输出: 最大价值: 220

为什么选择分支限界？

相比暴力搜索（时间复杂度O(2^n)），分支限界算法通过智能剪枝大幅减少搜索空间。虽然最坏情况仍是指数级，但在实践中对许多组合优化问题（如旅行商问题、作业调度等）表现优异。

总结

本教程带你从零理解并实现了Python分支限界算法。关键点在于：

1. 设计合理的节点结构存储状态
2. 高效计算上界（Bound）
3. 利用优先队列（堆）管理待探索节点
4. 及时剪枝无效分支

掌握这个算法教程后，你可以尝试将其应用到其他NP难问题中。记住：好的上界函数是提升效率的关键！