[Algorithm] 貪婪演算法

演算法概念

貪婪不是一個演算法，是一種策略：每一步都選當下看起來最好的選項，不回頭、不後悔。Prim、Kruskal、Dijkstra、Huffman 都是貪婪，但解的問題各不相同。

要讓「每步選當下最好」得到全局最優，問題本身要有兩個性質：

1. 貪婪選擇性質：每步的貪婪選擇不會讓之後的最優解消失——局部最優能組合成全域最優。
2. 最優子結構：整體最優解包含子問題的最優解。

兩個條件缺一不可。實務判斷能不能用貪婪：先想一個貪婪策略，再找反例；找到反例就改用動態規劃。

找零例子：台灣面額（1、5、10、50、100、500）對貪婪友善，付 100 買 73、找 27，貪婪拿 10+10+5+1+1 剛好 5 枚是最少的。但換成 1、3、4 元找 6 元，貪婪選 4+1+1 = 3 枚，最優解 3+3 = 2 枚——這套面額上貪婪就壞了。

各適用情境

Prim（最小生成樹）

演算法策略

最小生成樹（MST）：連通加權無向圖，找出一棵包含所有節點、總邊權最小的樹。Prim 的招式是從任意節點出發，每次從「一端在樹內、另一端在樹外」的候選邊中挑最便宜的一條加入，直到所有節點都被吸進樹裡。像一棵樹不斷長大。

複雜度

用 min-heap 存候選邊。每條邊最多進 heap 一次共 $|E|$ 次、每次 $O(\log V)$ → 總共 $O(|E| \log |V|)$。適合稠密圖。

範例

題目：6 個節點 A–F，邊（含權重）：A-B(4), B-C(3), D-E(7), E-F(9), A-D(1), B-E(2), C-F(6), A-E(8), C-E(5)。從 A 出發求 MST。

圖解：

步驟：

MST = {A-D, B-E, B-C, A-B, C-F}，總權重 16。

import heapq

def prim(graph, start):
    in_tree = set()
    heap = [(0, start)]
    total = 0
    while heap:
        weight, node = heapq.heappop(heap)
        if node in in_tree:
            continue
        in_tree.add(node)
        total += weight
        for neighbor, w in graph[node]:
            if neighbor not in in_tree:
                heapq.heappush(heap, (w, neighbor))
    return total

Kruskal（最小生成樹）

演算法策略

跟 Prim 同樣解 MST，但招式不同：把所有邊按權重由小到大排序，依序看——加進去不會成環就加、會成環就跳過，直到用掉 $|V| - 1$ 條邊。判斷成環用 Union-Find（並查集）：兩節點已連通代表加了會成環。

複雜度

排序 $O(|E| \log |E|)$ 主導，Union-Find 每次操作攤銷近 $O(1)$。總共 $O(|E| \log |E|)$。適合稀疏圖。

範例

題目：跟 Prim 同一張圖。

圖解：

步驟：邊排序後：A-D(1), B-E(2), B-C(3), A-B(4), C-E(5), C-F(6), D-E(7), A-E(8), E-F(9)。

總權重 $1 + 2 + 3 + 4 + 6 = 16$，跟 Prim 結果一致。

def kruskal(nodes, edges):
    parent = {n: n for n in nodes}

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return False
        parent[ry] = rx
        return True

    edges.sort(key=lambda e: e[2])
    total = 0
    for u, v, w in edges:
        if union(u, v):
            total += w
    return total

Sollin / Borůvka（最小生成樹）

演算法策略

另一種 MST 招式。每一輪，所有分量同時各自找自己最便宜的跨分量邊，一次全部加進去、合併分量。重複直到只剩一個分量。1926 年發明、比 Prim/Kruskal 都早，天生適合平行運算。

複雜度

每輪分量數至少減半（每個分量都至少跟一個鄰居合併）→ 最多 $\lceil \log |V| \rceil$ 輪，每輪掃一遍 $|E|$ 條邊 → $O(|E| \log |V|)$。

範例

題目：跟 Prim/Kruskal 同一張圖。

圖解：

步驟：

第一輪：每個節點自成一分量，各挑自己最小的外連邊。

去重後本輪加入：{A-D(1), B-E(2), B-C(3), C-F(6)}，累計 12。合併後分量：{A, D}、{B, C, E, F}。

第二輪：兩個分量各找最小外連邊。

加入 A-B(4)、合併為一個分量 → 停止。總權重 $12 + 4 = 16$。

def sollin(nodes, edges):
    parent = {n: n for n in nodes}

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return False
        parent[ry] = rx
        return True

    total = 0
    num_components = len(nodes)
    while num_components > 1:
        cheapest = {}
        for u, v, w in edges:
            ru, rv = find(u), find(v)
            if ru == rv:
                continue
            for r in [ru, rv]:
                if r not in cheapest or w < cheapest[r][2]:
                    cheapest[r] = (u, v, w)
        for u, v, w in cheapest.values():
            if union(u, v):
                total += w
                num_components -= 1
    return total

Dijkstra（單源最短路徑）

演算法策略

從起點 $s$ 出發，找到所有其他節點的最短距離。每輪從「還沒確定最短距離」的節點中挑 dist 最小的那個 $u$，把它標為已確定，再透過它鬆弛鄰居的距離（若 dist[u] + w(u, v) < dist[v] 就更新）。「每次選目前最近的」就是貪婪。

正確性要求：所有邊權非負。有負邊時一個還沒確定的節點可能之後被更新、Dijkstra 的「確定就不改」假設就破了——要改用 Bellman-Ford。

複雜度

用 min-heap：$|V|$ 次 extract-min + 最多 $|E|$ 次 push，每次 $O(\log V)$ → 總共 $O((|V| + |E|) \log |V|)$。

範例

題目：有向圖 8 個頂點 0–7，13 條邊：

從頂點 4 出發。

圖解：

步驟（每輪選 dist 最小的未確定節點、鬆弛鄰居）：

逐輪口述：

1. 選 4（dist = 0），鬆弛 4→0 得 12、4→3 得 15、4→5 得 3。
2. 選 5（dist = 3，目前未確定中最小），鬆弛 5→7 得 $3 + 4 = 7$。
3. 選 7（dist = 7），鬆弛 7→6 得 $7 + 10 = 17$。
4. 選 0（dist = 12），鬆弛 0→1 得 21、0→2 得 20。
5. 選 3（dist = 15），嘗試鬆弛 3→5（25 > 3 不更新）、3→7（17 > 7 不更新）。
6. 選 6、2、1 都只是確定身份，無可更新。

按路徑長度遞增排序：

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    return dist

Huffman 編碼

演算法策略

資料壓縮：高頻字元用短編碼、低頻字元用長編碼。用前綴碼（沒有任何字元的編碼是另一個的前綴）保證解碼無歧義。

建 Huffman Tree 的招式：把每個字元做成節點、權重為頻率。每輪用 min-heap 取出最輕的兩個節點，合併成新節點（權重 = 兩子權重之和）塞回 heap。重複到只剩一個根。從根到葉的路徑（左 0、右 1）就是該字元的編碼。

複雜度

建 heap $O(n)$、合併 $n - 1$ 輪，每輪兩次 pop + 一次 push 共 $O(\log n)$ → 總共 $O(n \log n)$。

範例

題目：字元頻率 A

圖解：

步驟（每輪取兩個最小合併）：

編碼結果：

加權長度 $45 \cdot 1 + 12 \cdot 3 + 13 \cdot 3 + 5 \cdot 4 + 9 \cdot 4 + 16 \cdot 3 = 224$ bit。固定 3 bit 需要 $100 \cdot 3 = 300$ bit，Huffman 省 25% 以上。

import heapq

def huffman(freq):
    heap = [(f, i, c) for i, (c, f) in enumerate(freq.items())]
    heapq.heapify(heap)
    counter = len(freq)
    while len(heap) > 1:
        f1, _, left = heapq.heappop(heap)
        f2, _, right = heapq.heappop(heap)
        heapq.heappush(heap, (f1 + f2, counter, (left, right)))
        counter += 1

    codes = {}

    def build(node, prefix=''):
        if isinstance(node, str):
            codes[node] = prefix
            return
        build(node[0], prefix + '0')
        build(node[1], prefix + '1')

    build(heap[0][2])
    return codes

活動選擇（Activity Selection）

演算法策略

一間會議室、多場會議各有開始與結束時間，不能重疊，目標是選最多場。貪婪招式：按結束時間由早到晚排序，依序挑不衝突的。理由很直觀——越早結束留越多空間給後面。

複雜度

排序 $O(n \log n)$ 主導；掃一遍 $O(n)$。總共 $O(n \log n)$。

範例

題目：

圖解：

步驟：按結束時間排序 A(4) < B(5) < C(6) < D(7) < E(9) < F(10) < G(11)。

結果：A、D、G，共 3 場。

def activity_selection(activities):
    activities.sort(key=lambda a: a[2])  # (name, start, end)
    selected = []
    last_end = float('-inf')
    for name, start, end in activities:
        if start >= last_end:
            selected.append(name)
            last_end = end
    return selected

凸包（Graham Scan）

演算法策略

給平面一堆點，找最小凸多邊形把所有點包起來。像用橡皮筋圈釘子、收縮後的形狀。Graham Scan 的招式：

1. 找 $y$ 最小（平手取 $x$ 最小）的點當起點。
2. 其他點依對起點的極角排序。
3. 依序掃過去，維護一個 stack——新來的點造成「右轉」就把 stack 頂彈掉（它不是凸包點），形成「左轉」才 push。

判左轉右轉用外積：三點 $P_1, P_2, P_3$，

$\text{cross} = (P_2.x - P_1.x)(P_3.y - P_1.y) - (P_2.y - P_1.y)(P_3.x - P_1.x)$

$\text{cross} > 0$ 左轉（保留）、$\leq 0$ 右轉或共線（彈出 $P_2$）。

複雜度

排序 $O(n \log n)$ 主導；掃描每個點最多 push / pop 一次 → $O(n)$。總共 $O(n \log n)$。

範例

題目：5 個點 $P_0 = (0, 0)$、$P_1 = (4, 0)$、$P_2 = (5, 3)$、$P_3 = (2, 4)$、$P_4 = (2, 2)$（$P_4$ 在內部）。

圖解：

步驟：起點 $P_0$。極角排序後順序 $P_1 \to P_2 \to P_4 \to P_3$。

凸包 = $P_0, P_1, P_2, P_3$（$P_4$ 被正確排除）。

import math

def graham_scan(points):
    start = min(points, key=lambda p: (p[1], p[0]))
    points.remove(start)
    points.sort(key=lambda p: math.atan2(p[1] - start[1], p[0] - start[0]))

    stack = [start]
    for p in points:
        while len(stack) >= 2:
            cross = ((stack[-1][0] - stack[-2][0]) * (p[1] - stack[-2][1])
                   - (stack[-1][1] - stack[-2][1]) * (p[0] - stack[-2][0]))
            if cross <= 0:
                stack.pop()
            else:
                break
        stack.append(p)
    return stack

Bin Packing（近似解）

演算法策略

$n$ 個物品、大小 $s_i \leq C$，箱容量 $C$，目標用最少箱子。這題是 NP-Hard，貪婪只能給近似解：

• Next Fit (NF)：只看最後一個箱子，塞不下就開新箱。
• First Fit (FF)：從第一個箱子掃，第一個塞得下的就放。
• First Fit Decreasing (FFD)：先把物品由大到小排序再跑 FF。大的先進、小的填縫。

複雜度

• NF：$O(n)$
• FF / FFD：$O(n \log n)$（FFD 排序主導；FF 每次找可用箱平均 $O(\log n)$）

近似比：

範例

題目：物品 $[0.5, 0.7, 0.5, 0.2, 0.4, 0.2, 0.3, 0.1]$、$C = 1.0$，跑 FFD。

圖解：

步驟：排序後 $[0.7, 0.5, 0.5, 0.4, 0.3, 0.2, 0.2, 0.1]$。

3 個箱子。物品總大小 2.9、下界 $\lceil 2.9 / 1 \rceil = 3$ → FFD 打到最佳。

def first_fit_decreasing(items, capacity=1.0):
    items_sorted = sorted(items, reverse=True)
    bins = []
    for item in items_sorted:
        for b in range(len(bins)):
            if bins[b] + item <= capacity:
                bins[b] += item
                break
        else:
            bins.append(item)
    return len(bins)

貪婪的陷阱：0/1 背包

演算法策略（失敗示範）

背包容量 $W$、每件物品只能整件拿或不拿、最大化總價值。乍看貪婪可以按「性價比（價值/重量）」由高到低選——但這是錯的。

為什麼貪婪壞在這裡：貪婪選擇性質不成立。選了性價比最高的物品，剩下容量可能裝不下另一件「絕對價值更高」的物品。

範例

題目：背包容量 $W = 5$，三件物品：

貪婪按性價比：選 A（1）+ B（3）= 4 ≤ 5，總價值 16。剩 1 容量，裝不下 C。

最優解：A（1）+ C（4）= 5，總價值 18。

貪婪錯了 2。0/1 背包必須用動態規劃。

貪婪 vs 動態規劃

常見考法