跳轉到

7.1 分支限界法#

概念說明#

分支限界法（Branch and Bound, B&B）是解決 NP-hard 優化問題最通用的精確框架。它的基本架構是系統化的搜尋（通常是 DFS 或最佳優先），但在每個搜尋節點上多做兩件事：

  1. 分支（Branch）：把目前的子問題切成幾個更小的子問題。最常見的分支決策是「某個物品/頂點/變數：包含它 vs. 不包含它」。
  2. 限界（Bound）：為每個子問題計算一個下界（對最小化問題）——即「這個子問題即使繼續搜下去，最好也只能達到這個值」。若下界已不優於目前找到的最佳解，整個子樹直接捨棄（剪枝）。

限界函數的品質決定一切：估計越緊、剪枝越多。以 0/1 背包為例，常用下界是「鬆弛成分數背包」：剩餘容量允許裝入物品的分數部分，這個問題可用貪婪法在 O(n) 內解出，且其最優值是原問題的上界（對最大化而言），可作為限界估計。

分支限界法是商業求解器（如 Gurobi、CPLEX）的骨幹技術之一，與整數線性規劃結合成「分支切割法」（Branch and Cut），能解出驚人規模的精確實例。它的最大魅力在於模組化：只要能定義分支規則與限界函式，任何 NP-hard 優化問題都能套用同一個搜尋框架。

演算法步驟（以 0/1 背包最大化為例）#

  1. 維護一個優先佇列（max-heap），節點記錄：層數 i、已累積價值 v、剩餘容量 c、當前最佳可能上界 ub。
  2. 初始節點：i = 0、v = 0、c = W，計算其分數背包上界。
  3. 反覆取出上界最大的節點：若 ub ≤ 目前已找到的最佳解，剪枝結束（佇列中不可能更優）。
  4. 分支「不拿第 i 個物品」與「拿第 i 個物品（若放得下）」兩個子節點。
  5. 對每個子節點計算新的分數背包上界；上界 ≤ 最佳解者捨棄。
  6. 到達葉節點（i = n）時更新最佳解。
  7. 佇列空則輸出最佳解。

Python 程式碼範例#

import heapq

def frac_upper_bound(values, weights, i, cap):
    """分數背包上界：貪婪裝填剩餘容量"""
    total = 0.0
    order = sorted(range(i, len(weights)),
                   key=lambda k: -values[k] / weights[k])
    for k in order:
        if weights[k] <= cap:
            cap -= weights[k]
            total += values[k]
        else:
            total += values[k] * cap / weights[k]
            break
    return total

def knapsack_branch_and_bound(values, weights, W):
    n = len(values)
    # 依單位價值排序可加強剪枝
    idx = sorted(range(n), key=lambda k: -values[k] / weights[k])
    values = [values[k] for k in idx]
    weights = [weights[k] for k in idx]

    heap = [(-frac_upper_bound(values, weights, 0, W), 0, 0, W, [])]
    best_v, best_items = 0, []
    nodes = 0
    while heap:
        neg_ub, i, v, c, items = heapq.heappop(heap)
        ub = -neg_ub
        nodes += 1
        if ub <= best_v or i == n:
            best_v, best_items = max(best_v, v), items
            continue
        # 分支：拿第 i 個物品
        if weights[i] <= c:
            heapq.heappush(heap, (
                -(v + values[i] +
                  frac_upper_bound(values, weights, i + 1,
                                   c - weights[i])),
                i + 1, v + values[i], c - weights[i],
                items + [idx[i]]))
        # 分支：不拿
        heapq.heappush(heap, (
            -(v + frac_upper_bound(values, weights, i + 1, c)),
            i + 1, v, c, items))
    return best_v, best_items, nodes

values, weights, W = [40, 30, 50, 10], [4, 3, 6, 2], 8
print(knapsack_branch_and_bound(values, weights, W))

複雜度分析#

  • 最壞情況：O(2ⁿ) 個節點，每個節點的限界計算 O(n log n)，總計仍是指數——B&B 不改變最壞複雜度。
  • 實際表現：好的限界函式常使實際展開節點遠小於 2ⁿ，許多數百個物品的隨機背包實例可在毫秒級解出。
  • 空間：最佳優先搜尋需 O(節點數) 的佇列；改用 DFS 版本（深度優先 + 限界）可將空間降到 O(n)。
  • 加強手段：更緊的限界（拉格蘭日鬆弛、線性規劃鬆弛）、更好的分支變數選擇、支配性測試。

練習#

  1. 統計 B&B 在 n = 15~25 隨機背包實例上展開的節點數，與 2ⁿ 比較，計算剪枝率。
  2. 把限界函式換成「僅用剩餘物品價值總和」（較鬆的上界），比較剪枝率下降多少，體會限界品質的影響。
  3. 將分支限界法套用到 TSP：以「當前路徑長 + 最小出邊和」作為下界，對 10 個城市的實例求解，與暴力法答案比對。