贪心算法

概述

贪心算法在每一步都做出局部最优的选择，希望最终得到全局最优解。贪心算法并不总是正确的，但当问题具有贪心选择性质和最优子结构时，贪心策略可以高效地得到最优解。

---

1. 贪心算法的基本要素

1.1 贪心选择性质

贪心选择性质：通过做出局部最优选择（贪心选择），可以得到全局最优解。即存在某个最优解包含贪心选择。

1.2 最优子结构

最优子结构：做出贪心选择后，剩余的子问题的最优解与原问题的最优解一致。

1.3 贪心算法的证明框架

1. 贪心选择性质：证明存在最优解包含第一个贪心选择
   • 常用方法：交换论证（exchange argument）——假设最优解不包含贪心选择，通过交换证明修改后的解不变差
2. 最优子结构：证明做出贪心选择后，问题归约为更小的同类问题

---

2. 活动选择问题

2.1 问题定义

给定 \(n\) 个活动，每个活动有起始时间 \(s_i\) 和结束时间 \(f_i\)，选择最多的互不重叠活动。

2.2 贪心策略

按结束时间排序，依次选择与已选活动不冲突的最早结束活动。

def activity_selection(activities):
    """活动选择：按结束时间贪心"""
    # 按结束时间排序
    activities.sort(key=lambda x: x[1])
    selected = [activities[0]]
    last_end = activities[0][1]

    for start, end in activities[1:]:
        if start >= last_end:
            selected.append((start, end))
            last_end = end

    return selected

2.3 正确性证明

贪心选择性质：设 \(a_1\) 是结束时间最早的活动。存在最优解包含 \(a_1\)。

证明：设 \(O\) 是一个最优解，\(a_k\) 是 \(O\) 中结束时间最早的活动。由于 \(f_1 \leq f_k\)，将 \(a_k\) 替换为 \(a_1\) 后，\(a_1\) 不会与 \(O\) 中其他活动冲突，新解仍是最优解。\(\square\)

---

3. Huffman编码

3.1 问题定义

给定字符集及其频率，构造前缀无歧义的变长编码，使总编码长度最小。

3.2 算法

import heapq

def huffman(freq):
    """Huffman编码"""
    # 建立最小堆
    heap = [(f, i, None, None) for i, f in enumerate(freq)]
    heapq.heapify(heap)

    while len(heap) > 1:
        # 取出频率最小的两个节点
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        # 合并
        merged = (left[0] + right[0], -1, left, right)
        heapq.heappush(heap, merged)

    return heap[0]  # 根节点

时间复杂度：\(O(n \log n)\)

3.3 最优性

Huffman编码产生最优前缀码。

性质：

• 频率最低的两个字符在最优编码树中是兄弟（深度最大的叶子）
• Huffman编码的平均码长满足：\(H(X) \leq \bar{L} < H(X) + 1\)，其中 \(H(X)\) 是信息熵

graph TB
    R((100)) --> L((45))
    R --> RL((55))
    RL --> RLL((25))
    RL --> RLR((30))
    RLL --> A["a:12<br>编码:110"]
    RLL --> B["b:13<br>编码:111"]
    RLR --> C["c:16<br>编码:10"]
    RLR --> RLRR((14))
    RLRR --> D["d:5<br>编码:100"]
    RLRR --> E["e:9<br>编码:101"]
    L --> F["f:45<br>编码:0"]

---

4. 最小生成树

4.1 Kruskal算法

贪心策略：按边权从小到大排序，依次加入不形成环的边。

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def kruskal(n, edges):
    """Kruskal最小生成树"""
    edges.sort(key=lambda e: e[2])  # 按权重排序
    uf = UnionFind(n)
    mst = []
    total = 0
    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            total += w
            if len(mst) == n - 1:
                break
    return mst, total

时间复杂度：\(O(E \log E)\)（排序主导）

4.2 Prim算法

贪心策略：从任意顶点开始，每次加入连接已选集合与未选集合的最小权边。

def prim(n, adj):
    """Prim最小生成树"""
    visited = [False] * n
    min_heap = [(0, 0)]  # (权重, 顶点)
    total = 0
    edges_added = 0

    while min_heap and edges_added < n:
        w, u = heapq.heappop(min_heap)
        if visited[u]:
            continue
        visited[u] = True
        total += w
        edges_added += 1
        for v, weight in adj[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (weight, v))

    return total

时间复杂度：\(O(E \log V)\)（二叉堆），\(O(E + V \log V)\)（斐波那契堆）

4.3 割性质（Cut Property）

定理：对于图 \(G\) 的任意割 \((S, V \setminus S)\)，穿越该割的最小权边一定属于某棵最小生成树。

这是Kruskal和Prim正确性的统一证明基础。

---

5. 分数背包问题

5.1 问题定义

\(n\) 个物品，第 \(i\) 个重量 \(w_i\)、价值 \(v_i\)，背包容量 \(W\)。允许取物品的一部分。

5.2 贪心策略

按单位价值 \(v_i / w_i\) 降序排列，依次装入。

def fractional_knapsack(items, capacity):
    """分数背包：按单位价值贪心"""
    # items: [(value, weight), ...]
    items.sort(key=lambda x: x[0] / x[1], reverse=True)
    total_value = 0

    for value, weight in items:
        if capacity >= weight:
            total_value += value
            capacity -= weight
        else:
            total_value += value * (capacity / weight)
            break

    return total_value

时间复杂度：\(O(n \log n)\)

0-1背包 vs 分数背包

分数背包可以用贪心求解，但0-1背包（不允许分割物品）不能。0-1背包是NP-hard问题，需要动态规划。

---

6. 作业调度

6.1 最小化完成时间（SPT规则）

\(n\) 个作业在单台机器上处理，作业 \(i\) 的处理时间为 \(p_i\)，最小化平均完成时间。

贪心策略：按处理时间从短到长排序（Shortest Processing Time first）。

平均完成时间：

\[ \bar{C} = \frac{1}{n} \sum_{i=1}^{n} C_i = \frac{1}{n} \sum_{i=1}^{n} \sum_{j=1}^{i} p_{\pi(j)} \]

6.2 带截止日期的作业调度

\(n\) 个作业，每个有利润 \(p_i\) 和截止日期 \(d_i\)，每个作业需要单位时间。选择作业子集最大化总利润。

贪心策略：按利润降序，尽可能安排在截止日期前最晚的空闲时间槽。

---

7. 拟阵与贪心

7.1 拟阵（Matroid）

拟阵 \(M = (S, \mathcal{I})\)：

• \(S\)：有限集（基础集）
• \(\mathcal{I} \subseteq 2^S\)：独立集族

满足：

1. 遗传性：\(B \in \mathcal{I}, A \subseteq B \implies A \in \mathcal{I}\)
2. 交换性：\(A, B \in \mathcal{I}, |A| < |B| \implies \exists x \in B \setminus A, A \cup \{x\} \in \mathcal{I}\)

7.2 拟阵上的贪心算法

定理：对于加权拟阵（带权独立集族），贪心算法（按权重降序，依次加入保持独立性的元素）产生最大权独立集。

例：

• 图拟阵（边集，独立集=无环边集）\(\to\) Kruskal算法
• 均匀拟阵 \(\to\) 选择前 \(k\) 大元素
• 划分拟阵 \(\to\) 着色问题

---

8. 贪心失败的例子

8.1 0-1背包

物品：\(v_1=60, w_1=10\)；\(v_2=100, w_2=20\)；\(v_3=120, w_3=30\)。容量 \(W=50\)。

• 贪心（按 \(v/w\)）：选 1, 2 \(\to\) 总价值160
• 最优：选 2, 3 \(\to\) 总价值220

8.2 集合覆盖（近似）

贪心不能得到最优解，但可以得到 \(O(\ln n)\) 近似比的解，这是最优的（在 \(P \neq NP\) 假设下）。

8.3 硬币找零

面额 \(\{1, 3, 4\}\)，目标 \(6\)：

• 贪心：\(4 + 1 + 1 = 3\) 枚
• 最优：\(3 + 3 = 2\) 枚

何时可以用贪心

• 有明确的贪心选择性质和最优子结构时
• 问题可以建模为拟阵时
• 作为启发式方法获取近似解时
• 当不确定时，先尝试贪心，再用反例验证

---

参考资料

• Cormen et al., Introduction to Algorithms (CLRS), Chapter 16
• Kleinberg & Tardos, Algorithm Design, Chapter 4

相关章节：

• 算法基础
• 动态规划
• 图算法

---

评论