第 74 课·回溯与搜索高级

分支限界法

branch-boundboundprunebnb

第 74 课 - 分支限界法

1. 学习目标

完成本课学习后，你应该能够：

  • 理解分支限界法的基本思想及其与回溯法的异同。
  • 掌握“限界函数”或“剪枝函数”的概念与作用。
  • 区分并使用两种主要的分支限界策略：广度优先（FIFO队列）与最优优先（优先队列）。
  • 应用分支限界法解决如0/1背包问题等经典优化问题。

2. 核心概念

分支限界法（Branch and Bound, BnB）是一种用于求解组合优化问题的系统算法框架。它的目标不是像回溯法那样找到所有解或某个特定解，而是找到问题的最优解（最大值或最小值）。

让我们用一个简单的比喻来理解：假设你在一个巨大的迷宫中寻找最短的出口路径。

  • 回溯法 就像是一个人用深度优先的方式，沿着一条路走到黑，碰壁了再回溯到上一个分叉点，尝试另一条路，直到走完所有可能的路。它的目标是找到路。
  • 分支限界法 则像是一个更聪明的探险队。他们每到一个分叉点，不仅会探索路径，还会评估每条已知路径的“潜力”（比如，已经走的距离加上估计到出口的最短距离）。他们会优先选择那些看起来最有希望、潜力最好的路径继续探索。如果一个分叉点的潜力已经比当前找到的最短路径还要差，他们就会直接放弃（限界）从这个分叉点出发的所有路径，从而节省大量时间。

核心要素：

  1. 状态空间树： 问题所有可能的解可以表示为一棵树（或图）。树的根节点代表初始状态，每个分支代表一个决策，叶子节点代表一个完整的解（或无效解）。
  2. 分支： 算法在每一层生成所有可能的子节点（即尝试所有选择）。
  3. 限界： 这是与回溯法最大的区别。算法会为每个活动节点（待扩展的节点）计算一个界限值（Bound）。这个值通常是一个乐观估计（对于最小化问题，是可能的最小代价下界；对于最大化问题，是可能的最大收益上界）。
  4. 剪枝/修剪： 如果一个活动节点的界限值表明，从它出发不可能得到比当前已找到的最优解更好的解，那么就彻底舍弃（剪枝）这个节点及其所有后代，不再进行扩展。

与回溯法的对比：

特性回溯法分支限界法
目标找到所有解或某个特定解找到最优解
遍历顺序通常是深度优先（DFS）通常是广度优先（BFS）或最优优先（用优先队列）
搜索策略系统地枚举，直到找到可行解或穷举完毕。有方向地搜索，利用界限函数引导搜索向可能产生最优解的子空间进行。
关键工具约束函数（判断是否可行）界限函数（判断是否有望优化）

3. 代码示例：0/1背包问题

0/1背包问题是分支限界法的经典应用场景：给定一组物品，每个物品有重量和价值，在限定的总重量内，我们如何选择，才能使得总价值最大？

我们将使用两种策略实现：1) BFS（队列），2) 最优优先（优先队列）。这里展示更优的最优优先策略。

import queue

class Item:
    """物品类"""
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value
        self.ratio = value / weight  # 价值重量比，用于计算上界

class Node:
    """节点类，代表状态空间树中的一个节点"""
    def __init__(self, level, value, weight, bound):
        self.level = level      # 当前考虑到了第几个物品（0-based）
        self.value = value      # 当前背包中的总价值
        self.weight = weight    # 当前背包中的总重量
        self.bound = bound      # 从该节点出发可能获得的最大价值上界

    def __lt__(self, other):
        # 让优先队列根据bound值从大到小排序（最大堆）
        return self.bound > other.bound

def bound(node, n, capacity, items):
    """计算以node为根的子树中，可能获得的最大价值上界"""
    # 如果当前重量已超容量，返回0（无效）
    if node.weight >= capacity:
        return 0
    
    value_bound = node.value
    total_weight = node.weight
    level = node.level + 1 # 从下一个物品开始考虑
    
    # 贪心：按价值重量比从高到低，尽可能多地装入剩余物品
    while level < n and total_weight + items[level].weight <= capacity:
        total_weight += items[level].weight
        value_bound += items[level].value
        level += 1
    
    # 如果还有剩余空间，用下一个物品的部分（分数背包）来填满，计算上界
    if level < n:
        value_bound += (capacity - total_weight) * items[level].ratio
    
    return value_bound

def knapsack_branch_and_bound(items, capacity):
    """分支限界法求解0/1背包问题（最优优先）"""
    # 按价值重量比降序排序物品，这有助于得到更紧的界限
    items.sort(key=lambda x: x.ratio, reverse=True)
    n = len(items)
    
    # 初始化根节点
    root = Node(-1, 0, 0, 0)
    root.bound = bound(root, n, capacity, items)
    
    # 使用优先队列（最大堆）
    pq = queue.PriorityQueue()
    pq.put(root)
    
    max_value = 0  # 记录当前找到的最大价值
    
    while not pq.empty():
        node = pq.get()
        
        # 如果当前节点的上界已经小于等于已知最大值，剪枝
        if node.bound <= max_value:
            continue
        
        # 如果不是根节点，更新最大价值
        if node.level > -1 and node.value > max_value:
            max_value = node.value
        
        # 如果已经是最后一个物品，无需再分支
        if node.level == n - 1:
            continue
        
        # 分支：考虑下一个物品（node.level + 1）
        next_level = node.level + 1
        
        # **选择1：不取该物品**
        left_child = Node(next_level, node.value, node.weight, 0)
        left_child.bound = bound(left_child, n, capacity, items)
        if left_child.bound > max_value: # 如果有希望，才加入队列
            pq.put(left_child)
        
        # **选择2：取该物品**（前提是总重量不超过容量）
        new_weight = node.weight + items[next_level].weight
        if new_weight <= capacity:
            right_child = Node(next_level, node.value + items[next_level].value, new_weight, 0)
            right_child.bound = bound(right_child, n, capacity, items)
            if right_child.bound > max_value: # 如果有希望，才加入队列
                pq.put(right_child)
    
    return max_value

# 测试代码
if __name__ == "__main__":
    # 物品列表 (重量, 价值)
    items = [
        Item(10, 60),
        Item(20, 100),
        Item(30, 120)
    ]
    capacity = 50
    max_val = knapsack_branch_and_bound(items, capacity)
    print(f"背包最大价值: {max_val}") # 预期输出: 220

4. 实践练习

练习1（基础）：理解与修改 修改上述代码的bound函数，使其适用于最小化问题。例如，旅行商问题（TSP）的最短路径。你需要考虑如何为当前路径计算一个下界（可能的最小剩余路径长度）。思考：应该如何修改比较逻辑和队列方向？

练习2（中等）：应用BFS策略 使用普通的FIFO队列（而不是优先队列）实现0/1背包问题的分支限界法。比较两种策略在相同问题实例下，访问的节点数量有何不同，并解释原因。

练习3（进阶）：任务分配问题 有N个任务和N个工人，每个工人完成每个任务的成本不同。我们需要将每个任务分配给一个工人，且每个工人只能被分配一个任务，目标是最小化总成本。这是一个最小化问题。请设计一个分支限界法求解。提示：

  • 状态空间树：根节点是空分配，每层代表为一个任务选择工人。
  • 限界函数：可以计算当前已分配任务的总成本，加上剩余未分配任务的最小可能成本（例如，每个任务都找当前可选工人中成本最小的，即使可能冲突）。
  • 当当前总成本 + 下界 >= 已知最优解时剪枝。

5. 常见错误

  1. 界限计算错误： 这是最关键也最容易出错的地方。界限必须是一个乐观估计（对最大化问题是上界，对最小化问题是下界）。计算错误会导致错误剪枝（剪掉了可能产生最优解的分支）或无法剪枝（算法退化为穷举）。
  2. 过度剪枝： 如果界限过于乐观（例如，在最大化问题中，界限值计算得远高于实际可能值），会导致很多本不该剪掉的分支被保留，算法效率下降。
  3. 忽略剪枝的必要性： 只使用分支而不进行有效的限界和剪枝，分支限界法就失去了优势，变成了低效的广度优先搜索。
  4. 策略选择不当： 对于某些问题，广度优先（BFS）的分支限界法可能需要存储大量节点，内存消耗巨大。而最优优先策略（优先队列）通常更快找到最优解，但实现稍复杂。应根据问题特点选择。
  5. 初始化和边界条件： 例如，在背包问题中，根节点的初始化、物品排序的逻辑、以及容量不足时的判断，都是容易出错的细节。

6. 小结

本节课我们学习了分支限界法：

  • 本质：它是一种在状态空间树中有方向地搜索最优解的算法框架。
  • 核心机制：“分支”生成候选解，“限界”（通过界限函数）评估候选解的潜力，并基于此进行“剪枝”，大幅减少搜索空间。
  • 策略选择：
    • 广度优先 (BFS)：使用队列，逐层展开，常与LC（最小成本）策略结合。
    • 最优优先：使用优先队列，始终沿着“最有希望”的路径探索，通常效率更高。
  • 关键点：设计一个有效且计算廉价的界限函数是成功应用分支限界法的关键。
  • 应用：适用于许多组合优化问题，如背包问题、旅行商问题（TSP）、任务分配、整数规划等。

掌握分支限界法，意味着你拥有了一件解决复杂优化问题的强大工具，它通过“评估未来”来指导“当前决策”，这正是算法智能的体现。下一课，我们将学习另一个强大的启发式搜索算法——A*搜索算法，它将界限（启发式）的思想与图搜索完美结合。

练习编辑器

rust
Loading...

继续学习

完成本课后，建议继续学习下一课「A* 搜索算法」 以巩固所学知识。