分支限界法

分支限界法（Branch and Bound）是一种用于解决组合优化问题的算法框架，尤其适用于NP难问题。它通过系统地枚举候选解，并结合“限界”策略剪枝无效分支，从而高效地找到最优解。与回溯法不同，分支限界法通常使用优先级队列（如最小堆）来选择扩展节点，优先处理最有希望的路径。

核心思想

分支限界法的核心分为两部分：

1. 分支：将问题分解为子问题（例如通过决策树的节点展开）。
2. 限界：计算当前子问题的上下界，若不可能优于已知解，则剪枝。

数学上，限界函数可表示为： $f(x)\le U$ 其中$U$是当前最优解的上界，$f(x)$为当前节点的评估值。

算法流程

1. **初始化**：创建根节点，放入优先级队列。 2. **循环**：

  a. 取出队列中最优节点（根据限界函数）。  
  b. 若节点为叶子且优于当前解，更新最优解。  
  c. 否则，生成子节点并计算限界值，保留可行节点。  

3. **终止条件**：队列为空或限界条件满足。

伪代码示例

  
def branch_and_bound(root):  
    queue = PriorityQueue()  
    queue.put(root)  
    best_solution = None  

    while not queue.empty():  
        node = queue.get()  
        if node.is_leaf() and (best_solution is None or node.value < best_solution):  
            best_solution = node.value  
        for child in node.generate_children():  
            if child.bound < best_solution:  # 剪枝条件  
                queue.put(child)  
    return best_solution

实际案例：0-1背包问题

问题描述：给定物品重量$w_i$和价值$v_i$，背包容量$W$，求最大价值组合。

分支限界法实现

  
import heapq  

class Node:  
    def __init__(self, level, profit, weight, items):  
        self.level = level      # 当前决策层级  
        self.profit = profit    # 当前价值  
        self.weight = weight    # 当前重量  
        self.items = items      # 包含的物品索引  
        self.bound = 0          # 价值上界  

    def __lt__(self, other):  
        return self.bound > other.bound  # 最大堆  

def bound(node, W, w, v, n):  
    if node.weight >= W:  
        return 0  
    bound = node.profit  
    j = node.level + 1  
    total_weight = node.weight  
    while j < n and total_weight + w[j] <= W:  
        bound += v[j]  
        total_weight += w[j]  
        j += 1  
    if j < n:  
        bound += (W - total_weight) * (v[j] / w[j])  # 贪心估算剩余  
    return bound  

def knapsack(W, w, v, n):  
    queue = []  
    root = Node(-1, 0, 0, [])  
    root.bound = bound(root, W, w, v, n)  
    heapq.heappush(queue, root)  
    max_profit = 0  

    while queue:  
        node = heapq.heappop(queue)  
        if node.bound > max_profit:  
            level = node.level + 1  
            # 包含下一物品  
            if level < n:  
                left = Node(level, node.profit + v[level], node.weight + w[level], node.items + [level])  
                left.bound = bound(left, W, w, v, n)  
                if left.weight <= W and left.profit > max_profit:  
                    max_profit = left.profit  
                if left.bound > max_profit:  
                    heapq.heappush(queue, left)  
                # 不包含下一物品  
                right = Node(level, node.profit, node.weight, node.items)  
                right.bound = bound(right, W, w, v, n)  
                if right.bound > max_profit:  
                    heapq.heappush(queue, right)  
    return max_profit  

# 示例输入  
W = 10  
w = [2, 3, 5, 7]  
v = [10, 5, 15, 7]  
n = len(w)  
print(knapsack(W, w, v, n))  # 输出：22（选择物品0和2）

复杂度分析

• **最坏情况**：仍需遍历所有节点，时间复杂度与穷举相同（如$O(2^n)$）。
• **实际效率**：依赖限界函数的剪枝效果，通常远优于穷举。

应用场景

• 旅行商问题（TSP）：寻找最短环路。
• 作业调度：最小化完成时间。
• 整数规划：线性规划的离散优化。

与回溯法的对比

分支限界法 vs 回溯法

特性	分支限界法	回溯法
搜索策略	优先级队列（如最小堆）	深度优先搜索
解目标	通常求最优解	可行解或全部解
剪枝依据	上下界函数	约束条件

可视化示例

graph TD A[根节点: 价值=0, 重量=0] --> B[包含物品1: 价值=10, 重量=2] A --> C[不包含物品1: 价值=0, 重量=0] B --> D[包含物品2: 价值=15, 重量=5] B --> E[不包含物品2: 价值=10, 重量=2] D --> F[包含物品3: 价值=22, 重量=10] D --> G[不包含物品3: 价值=15, 重量=5] style F fill:#f9f,stroke:#333

• 粉色节点为最优解路径。

总结

分支限界法通过智能剪枝大幅提升搜索效率，适合求解组合优化问题。理解其限界函数的设计是关键，实际应用中需结合问题特性调整策略。