编辑“︁分支限界法”︁

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

== 核心思想 ==  
分支限界法的核心分为两部分：  
# '''分支'''：将问题分解为子问题（例如通过决策树的节点展开）。  
# '''限界'''：计算当前子问题的上下界，若不可能优于已知解，则剪枝。  

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

== 算法流程 ==  
1. **初始化**：创建根节点，放入优先级队列。  
2. **循环**：  
   a. 取出队列中最优节点（根据限界函数）。  
   b. 若节点为叶子且优于当前解，更新最优解。  
   c. 否则，生成子节点并计算限界值，保留可行节点。  
3. **终止条件**：队列为空或限界条件满足。  

=== 伪代码示例 ===  
<syntaxhighlight lang="python">  
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  
</syntaxhighlight>  

== 实际案例：0-1背包问题 ==  
'''问题描述'''：给定物品重量<math>w_i</math>和价值<math>v_i</math>，背包容量<math>W</math>，求最大价值组合。  

=== 分支限界法实现 ===  
<syntaxhighlight lang="python">  
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）  
</syntaxhighlight>  

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

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

== 与回溯法的对比 ==  
{| class="wikitable"  
|+ 分支限界法 vs 回溯法  
! 特性 !! 分支限界法 !! 回溯法  
|-  
| 搜索策略 || 优先级队列（如最小堆） || 深度优先搜索  
|-  
| 解目标 || 通常求最优解 || 可行解或全部解  
|-  
| 剪枝依据 || 上下界函数 || 约束条件  
|}  

== 可视化示例 ==  
<mermaid>  
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  
</mermaid>  
* 粉色节点为最优解路径。  

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:回溯与分支限界]]