集合覆蓋

Vibe Prompt

「幫我用貪婪演算法解決集合覆蓋問題：有 10 個城市與 5 個廣播站，每個廣播站涵蓋不同城市。找出最小廣播站集合。」

def set_cover(universe, subsets):
    """
    universe: 所有元素的集合
    subsets: {name: set_of_elements}
    """
    remaining = universe.copy()
    selected = []
    
    while remaining:
        best_name = None
        best_covered = 0
        for name, elements in subsets.items():
            if name not in selected:
                covered = len(remaining & elements)
                if covered > best_covered:
                    best_covered = covered
                    best_name = name
        if best_name:
            selected.append(best_name)
            remaining -= subsets[best_name]
        else:
            break
    return selected

universe = set(range(10))
subsets = {
    "站A": {0,1,2,3},
    "站B": {3,4,5},
    "站C": {5,6,7},
    "站D": {7,8,9},
    "站E": {0,4,9},
}

result = set_cover(universe, subsets)
print(f"選取廣播站: {result}")

# 貪婪不保證最佳但實務上夠用
print(f"涵蓋率: {len(set.union(*[subsets[r] for r in result]))}/{len(universe)}")

深入理解：貪婪集合覆蓋的近似比

貪婪的保證

雖然集合覆蓋是 NP-Hard 問題，但貪婪演算法有理論保證：

貪婪解 ≤ 最佳解 × $\ln(n)$，其中 $n$ 是最大集合大小

# 驗證近似比
def greedy_approximation_ratio(universe, subsets):
    greedy_sol = set_cover(universe, subsets)
    # 貪婪的解大小
    greedy_size = len(greedy_sol)
    # 理論上界
    max_set_size = max(len(s) for s in subsets.values())
    ln_bound = math.log(max_set_size) if max_set_size > 0 else 0
    print(f"貪婪解大小: {greedy_size}")
    print(f"理論上界: ≤ OPT × {ln_bound:.2f}")
    return greedy_size

何時用貪婪？何時用精確解？

| 問題規模 | 建議方法 | 原因 | |:--------:|---------|------| | 元素 < 50 | 整數規劃 (ILP) 精確解 | 可找到最佳解 | | 元素 50-500 | 貪婪演算法 | 夠好且快 | | 元素 > 500 | 貪婪演算法 | 精確解太慢 | | 需要保證最佳 | 分枝限定法 (Branch & Bound) | 可中斷取目前最佳 |

關鍵要點

✅ 集合覆蓋是 NP-Hard 問題，但貪婪給出 $\ln(n)$-近似解
✅ 每次選擇覆蓋最多未覆蓋元素的集合
✅ 貪婪在實務上通常表現遠優於理論保證
✅ 集合覆蓋是「最大覆蓋」問題的對偶
✅ 應用：工廠選址、感測器部署、病毒檢測

基礎範例

常見錯誤

程式碼範例

集合覆蓋：貪婪不一定最佳

到目前為止你看到的演算法（Huffman、Prim、Kruskal）都是「貪婪 = 最佳」的特例。但**集合覆蓋問題（Set Cover）**是告訴你真相的地方：貪婪不一定能得到最佳解。

為什麼集合覆蓋是 NP-hard？

想像你要在一個城市裡選最少的位置開便利商店，讓每個社區都至少有一間店在步行範圍內。這就是 Set Cover——從所有可能位置中選出一個子集，覆蓋所有需求點。

這個問題沒有人知道怎麼在多項式時間內求出最佳解。貪婪演算法（每次都選覆蓋最多未覆蓋需求的店）只能保證一個近似比：

$$\text{Greedy} \leq \ln(n) \times \text{OPT}$$

也就是說如果最佳解需要 5 間店，貪婪可能找到 5 × ln(100) ≈ 23 間。雖然不是最佳，但已經足夠實用了。

真實應用

| 領域 | Set Cover 的對應 | |:----|:---------------| | 雲端資源 | 選最少的主機型態來滿足所有 workload | | 廣告投放 | 用最少廣告預算覆蓋最多目標受眾 | | 感測器網路 | 放最少感測器監控整個區域 | | 基因定序 | 用最短的 DNA 片段組合出完整基因 | | 電路設計 | 用最少邏輯閘實作所有布林函數 |

這堂課你學到了四種貪婪演算法——Huffman（壓縮）、Prim/Kruskal（MST）、Set Cover（近似）。每一種都展示了貪婪策略在不同問題上的應用與限制。如果你對演算法的數學證明感興趣，下一門課的動態規劃將帶你進入另一個世界。