第16章 贪心算法

导读

贪心算法（Greedy Algorithm）是另一种重要的算法设计策略。与动态规划不同，贪心算法在每步都做出当前看起来最优的选择（局部最优），希望通过一系列局部最优选择达到全局最优。贪心算法通常更简单、更高效，但只适用于具有"贪心选择性质"的问题。

本章将介绍贪心算法的设计思想，通过活动选择问题、Huffman编码、分数背包等经典问题来展示贪心策略的应用。我们还将讨论贪心算法与动态规划的关系和区别。

核心概念详解

16.1 贪心算法的基本思想

贪心算法的核心思想：

• 在每一步选择中，都做出当前看起来最优的选择
• 希望通过局部最优选择的序列能得到全局最优解
• 不回溯——一旦做出选择就不能更改

适用条件：

贪心选择性质（Greedy Choice Property）：全局最优解可以通过一系列局部最优选择得到

最优子结构：问题的最优解包含子问题的最优解

与动态规划的区别：

• 动态规划：先求解子问题，再选择
• 贪心算法：先做选择，再求解子问题
• 贪心不回溯，动态规划考虑所有可能

16.2 活动选择问题

问题描述：

给定n个活动{a₁, a₂, ..., aₙ}，每个活动有开始时间sᵢ和结束时间fᵢ。两个活动兼容如果它们的时间不重叠。求最大兼容活动集合。

贪心策略：

每次选择结束时间最早且与已选活动兼容的活动。

算法：

GREEDY-ACTIVITY-SELECTOR(s, f)
    n = s.length
    A = {a₁}           // 选择结束最早的活动
    k = 1
    for m = 2 to n
        if s[m] ≥ f[k]  // 活动m与最近选择的活动兼容
            A = A ∪ {aₘ}
            k = m
    return A

时间复杂度：O(n)（假设活动已按结束时间排序）

正确性证明：

使用"剪切-粘贴"技术证明贪心选择性质：

• 设A是最优解，a₁是结束最早的活动
• 如果A不包含a₁，设aₖ是A中结束最早的活动
• 用a₁替换aₖ，得到的解仍然兼容且大小相同
• 因此存在包含a₁的最优解
• 选择a₁后，问题归结为在剩余活动中选择

16.3 Huffman编码

问题描述：

设计前缀码（没有任何码字是另一个码字的前缀），使编码后的总长度最小。

贪心策略：

每次合并频率最低的两个节点。

算法：

HUFFMAN(C)
    n = |C|
    Q = C    // 最小优先队列
    for i = 1 to n - 1
        z = new Node
        z.left = x = EXTRACT-MIN(Q)
        z.right = y = EXTRACT-MIN(Q)
        z.freq = x.freq + y.freq
        INSERT(Q, z)
    return EXTRACT-MIN(Q)

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

最优性证明：

• 通过归纳法证明Huffman树是最优前缀码
• 关键引理：存在最优编码树，其中频率最低的两个字符是兄弟且在最深层

16.4 分数背包问题

问题描述：

n个物品，每个有重量wᵢ和价值vᵢ。背包容量W。物品可以分割。求最大价值。

贪心策略：

按单位重量价值vᵢ/wᵢ从高到低选择物品。

算法：

FRACTIONAL-KNAPSACK(v, w, W)
    按vᵢ/wᵢ降序排列
    V = 0
    for i = 1 to n
        if W == 0
            break
        if wᵢ ≤ W
            取整个物品i
            V += vᵢ
            W -= wᵢ
        else
            取物品i的一部分
            V += vᵢ · (W / wᵢ)
            W = 0
    return V

时间复杂度：O(n log n)（排序）

与0-1背包的区别：

• 分数背包：物品可分割，贪心有效
• 0-1背包：物品不可分割，需要动态规划

16.5 最小生成树

Kruskal算法：

MST-KRUSKAL(G, w)
    A = ∅
    for each vertex v in G.V
        MAKE-SET(v)
    按权重升序排列所有边
    for each edge (u, v) in sorted order
        if FIND-SET(u) ≠ FIND-SET(v)
            A = A ∪ {(u, v)}
            UNION(u, v)
    return A

Prim算法：

MST-PRIM(G, w, r)
    for each u in G.V
        u.key = ∞
        u.π = NIL
    r.key = 0
    Q = G.V    // 最小优先队列
    while Q ≠ ∅
        u = EXTRACT-MIN(Q)
        for each v in G.Adj[u]
            if v in Q and w(u, v) < v.key
                v.π = u
                v.key = w(u, v)

贪心选择：每次选择权重最小的安全边。

16.6 单源最短路径

Dijkstra算法：

DIJKSTRA(G, w, s)
    INITIALIZE-SINGLE-SOURCE(G, s)
    S = ∅
    Q = G.V
    while Q ≠ ∅
        u = EXTRACT-MIN(Q)
        S = S ∪ {u}
        for each vertex v in G.Adj[u]
            RELAX(u, v, w)

贪心选择：每次选择距离估计最小的未处理顶点。

注意：Dijkstra算法只适用于非负权边。

16.7 贪心策略的证明方法

证明贪心选择性质：

方法1：剪切-粘贴

• 假设最优解不包含贪心选择
• 用贪心选择替换，证明仍然最优
• 矛盾

方法2：归纳法

• 证明第一步贪心选择正确
• 假设前k步贪心选择正确
• 证明第k+1步也正确

方法3：交换论证

• 假设存在更优的解
• 通过交换操作将其转化为贪心解
• 证明交换不会使解变差

16.8 拟阵理论

拟阵（Matroid）是贪心算法正确性的理论基础。

定义：

拟阵M = (S, I)，其中：

• S是有限集合
• I是S的子集族，满足：

1. 空集属于I

2. 遗传性：若B∈I且A⊆B，则A∈I

3. 交换性：若A,B∈I且|A|<|B|，则存在x∈B-A使得A∪{x}∈I

贪心算法在拟阵上的正确性：

如果问题可以建模为拟阵上的最大权独立集问题，贪心算法保证最优解。

16.9 贪心算法的局限性

贪心算法不是万能的：

• 0-1背包问题：贪心不能保证最优
• 最短路径（负权边）：Dijkstra失效
• 旅行商问题：贪心给出近似解

16.10 贪心算法的变体

局部搜索：

从初始解出发，通过局部改进寻找更优解。

增量构造：

逐步构建解，每步添加最优元素。

递减构造：

从完整解出发，逐步删除最不优的元素。

重要知识点

知识点1：贪心选择性质的证明

证明贪心选择性质是贪心算法正确性的关键。常用方法包括剪切-粘贴、归纳法和交换论证。

知识点2：贪心与动态规划的选择

• 如果问题具有贪心选择性质，优先使用贪心
• 否则使用动态规划
• 贪心通常更简单高效

知识点3：拟阵与贪心的关系

拟阵理论为贪心算法提供了理论基础。如果问题可以建模为拟阵，贪心保证最优。

知识点4：贪心算法的效率

贪心算法通常比动态规划更高效：

• 活动选择：O(n)
• Huffman编码：O(n log n)
• 最小生成树：O(E log V)

知识点5：贪心策略的多样性

同一个问题可能有多种贪心策略，需要选择正确的：

• 活动选择：选结束最早的（正确）vs 选开始最早的（错误）vs 选最短的（错误）

常见误区

误区1：局部最优一定导致全局最优

贪心算法的局部最优选择只有在问题具有贪心选择性质时才能保证全局最优。不是所有问题都满足这个条件。

误区2：贪心算法总是比动态规划好

贪心只适用于特定问题。对于不满足贪心选择性质的问题，必须使用动态规划。

误区3：所有最优化问题都可以用贪心

许多最优化问题（如0-1背包、TSP）不具有贪心选择性质，贪心只能给出近似解。

误区4：贪心选择是唯一的

同一个问题可能有多种贪心策略，需要选择正确的。例如活动选择中，选结束最早的是正确的，选开始最早的则不是。

误区5：贪心算法不需要证明

贪心算法的正确性需要严格证明。直觉上"正确"的贪心策略可能实际上是错误的。

实践应用

应用1：数据压缩

Huffman编码是广泛使用的数据压缩算法：

• ZIP、GZIP等压缩格式
• JPEG图像压缩
• MP3音频压缩

应用2：网络设计

最小生成树用于：

• 网络布线设计
• 电路设计
• 聚类分析

应用3：调度问题

活动选择算法用于：

• 会议室调度
• 机器调度
• 航班调度

应用4：路由算法

Dijkstra算法用于：

• GPS导航
• 网络路由
• 游戏AI寻路

应用5：资源分配

贪心策略用于：

• 频带分配
• 任务分配
• 广告投放

16.11 贪心算法的更多经典问题

区间调度问题：

问题：给定n个区间[sᵢ, fᵢ)，选择最大数量的不重叠区间。

贪心策略：按结束时间升序，每次选择结束最早且与已选区间不重叠的区间。

这与活动选择问题本质相同。证明方法也类似——通过交换论证证明贪心选择性质。

任务分配问题：

问题：n个任务，每个有截止时间和惩罚。安排任务顺序使总惩罚最小。

贪心策略：按惩罚降序排列，尽量在截止时间前完成高惩罚任务。

最小延迟调度：

问题：n个任务，每个有处理时间和截止时间。最小化最大延迟。

贪心策略：按截止时间升序排列（最早截止时间优先，EDF）。

霍夫曼树的构建细节：

Huffman编码的完整流程：

统计每个字符的频率

创建n个单节点树，加入最小优先队列

重复n-1次：取出两个最小频率的树，合并为新树

从根到叶子路径即为编码

编码长度分析：

• 平均编码长度 = Σ freq[i] · depth[i]
• Huffman编码的平均长度不超过熵 + 1
• 是最优前缀码

16.12 贪心算法证明方法的深入分析

交换论证的详细步骤：

设G是贪心解，O是最优解

如果G = O，证毕

否则，找G和O中第一个不同的选择

证明可以将O中的选择替换为G中的选择，而不使解变差

重复替换，最终将O转化为G，且解不会变差

因此G也是最优的

归纳法的详细步骤：

基础：证明第一步贪心选择是正确的（存在包含该选择的最优解）

归纳假设：假设前k步贪心选择都正确

归纳步骤：证明第k+1步的贪心选择在剩余子问题中也是正确的

结论：所有步骤的贪心选择都正确，贪心解是最优的

两种方法的比较：

• 交换论证更通用，适用于大多数贪心问题
• 归纳法更直观，但需要明确子问题结构
• 选择哪种方法取决于问题的特性

16.13 贪心算法在近似算法中的角色

许多NP难问题没有精确的贪心解法，但贪心策略可以给出好的近似：

集合覆盖问题：

• 贪心策略：每次选择覆盖最多未覆盖元素的集合
• 近似比：H(n) ≈ ln n（调和数）
• 这是最优多项式时间近似比（除非P=NP）

旅行商问题（度量空间）：

• 基于MST的2-近似算法
• 先求MST，然后前序遍历
• Christofides算法：3/2-近似

顶点覆盖：

• 贪心策略：每次选择度数最大的顶点
• 近似比不保证常数
• 随机化2-近似：随机选边，加入两个端点

16.14 贪心算法在机器学习中的应用

决策树学习：

ID3/C4.5算法使用贪心策略：

• 每次选择信息增益最大的属性进行分裂
• 不保证全局最优，但实践中效果好

特征选择：

• 前向选择：每次添加最有用的特征
• 后向消除：每次移除最不重要的特征
• 贪心策略，可能陷入局部最优

聚类算法：

• K-means：贪心地分配点到最近的中心
• 贪心初始化（K-means++）：选择距离已有中心最远的点作为新中心

16.15 贪心与动态规划的选择指南

何时使用贪心：

• 问题具有贪心选择性质（可以证明）
• 局部最优选择不会排除全局最优
• 子问题的解不受当前选择的影响

何时使用动态规划：

• 问题不具有贪心选择性质
• 当前选择影响后续子问题
• 需要考虑所有可能的选择

实践中的判断：

先尝试贪心策略

如果能证明正确性，使用贪心

如果不能证明，尝试构造反例

如果存在反例，改用动态规划

本章小结

本章深入介绍了贪心算法的设计思想和应用。我们学习了：

基本思想：每步做局部最优选择，不回溯。

适用条件：贪心选择性质和最优子结构。

经典问题：活动选择、Huffman编码、分数背包、最小生成树、单源最短路径、区间调度等。

证明方法：剪切-粘贴、归纳法、交换论证的详细步骤和比较。

拟阵理论：贪心算法正确性的理论基础。

近似算法：贪心在NP难问题中的应用，集合覆盖、TSP、顶点覆盖等。

机器学习：决策树、特征选择、聚类中的贪心策略。

与动态规划的区别和选择：贪心不回溯，动态规划考虑所有可能。

贪心算法是一种简单而强大的算法设计策略。在适用的场景下，贪心算法通常是最优选择。即使不能保证最优，贪心策略也常常给出高质量的近似解。

关键术语

思考题

证明：在活动选择问题中，选择开始时间最晚的策略不能保证最优解。

设计一个贪心算法，找零钱问题（用最少的硬币凑成指定金额）。分析在什么硬币面额下贪心是最优的。

证明：如果所有边权重不同，图的最小生成树唯一。

设计一个贪心算法解决区间调度问题：给定n个区间，选择最大数量的不重叠区间。