详解贪心算法

什么是贪心算法？

贪心算法（Greedy Algorithm）是一种基于每一步都选择当前最优解的算法设计思想。它在每个阶段总是做出在当前看来最优的选择（局部最优解），而不回溯或考虑整个问题的全局最优性。它期望通过这样逐步构建最终的解决方案，使整个问题的解达到最优。

不过，贪心算法并不适用于所有问题。要确保贪心算法能够获得全局最优解，问题必须具备以下两个特性：

1. 贪心选择性质：通过局部最优选择可以推导出全局最优解。
2. 最优子结构：问题的全局最优解可以从它的子问题的最优解构成。

贪心算法的特点

1. 局部最优：每一步都选择当前最好的解决方案，而不考虑将来的结果。
2. 全局最优：希望通过一系列局部最优的选择来得到整体问题的最优解。
3. 不可回溯：一旦作出选择，就无法回退并修改之前的决定。

贪心算法的应用场景

贪心策略适用于一些特殊的问题，通常有两个条件：

1. 贪心选择性质：局部最优的选择可以导致全局最优。
2. 最优子结构：问题的最优解可以通过若干子问题的最优解组合而成。

贪心算法的基本思路

贪心算法的关键在于每一步做出最优选择。在求解问题时，贪心策略的基本步骤通常为：

1. 构造贪心选择：在当前阶段找到最佳选择，不考虑之后的影响。
2. 验证贪心选择的可行性：做出的选择必须满足问题的约束条件。
3. 问题分解：将剩余的子问题继续分步解决，直到问题解决完毕。

由于每次都选择局部最优解，贪心算法通常具有较快的执行速度和较低的时间复杂度。然而，选择局部最优解不一定总是能带来全局最优解，所以使用贪心算法时需要仔细分析问题。

贪心算法的经典应用

1. 活动选择问题

问题描述：假设有多个活动，每个活动都有特定的开始和结束时间。要求选择最多不重叠的活动，使得能够安排的活动数量最多。

贪心策略：每次选择结束时间最早且不与之前选择的活动冲突的活动。这一策略能够最大限度地为后续活动留出时间，从而容纳更多活动。

详细步骤：

• 首先将活动按结束时间升序排序。
• 从第一个活动开始，选择每一个不与已经选中活动冲突的活动。

举例：

活动  | 开始时间 | 结束时间
A     |   1     |   4
B     |   3     |   5
C     |   0     |   6
D     |   5     |   7
E     |   3     |   9
F     |   5     |   9

按照贪心策略，首先选择结束时间最早的活动 A（1,4），接着选择活动 D（5,7），最后选择活动 F（5,9）。因此，我们可以选择最多 3 个活动。

贪心选择证明：选择最早结束的活动可以为后续活动留下最多的时间，从而有机会安排更多活动，这是贪心策略的核心思想。

2. 最小硬币找零问题

问题描述：给定一些硬币面额，例如 1 元、2 元和 5 元，要求用最少数量的硬币来凑出某个金额。

贪心策略：每次选择面额最大的硬币，尽量减少剩余的金额。

详细步骤：

• 根据贪心策略，首先从剩余金额中扣除最大面额的硬币。
• 继续对剩下的金额使用同样的策略，直到凑齐所需的金额。

举例：
假设要凑 11 元，硬币面额为 1 元、2 元和 5 元。按照贪心策略的步骤：

• 选择 5 元（剩余 6 元），
• 再选择 5 元（剩余 1 元），
• 最后选择 1 元（剩余 0 元）。

共使用了 3 枚硬币（2 个 5 元和 1 个 1 元），这种选择是最优的。

局限性：贪心算法并不总是适用于找零问题。例如，若硬币面额为 1 元、3 元和 4 元，而你需要凑 6 元时，贪心算法会选择 4 元 + 1 元 + 1 元，总共 3 枚硬币，但其实只需要两枚 3 元硬币。所以问题的硬币面额配置必须具有特定的结构，才能保证贪心算法的最优性。

3. 霍夫曼编码问题

问题描述：霍夫曼编码用于对字符进行压缩编码，要求频率出现较高的字符使用较短的编码，而频率较低的字符使用较长的编码，以减少总的编码长度。

贪心策略：每次从字符集中选择出现频率最低的两个字符，将它们合并为一个节点，然后继续合并，直到只剩下一个根节点为止。

详细步骤：

• 首先将字符按照频率升序排序。
• 每次取频率最小的两个字符，将它们合并为一个新的节点，新的节点频率为两个字符频率之和。
• 重复该过程，直到生成一棵霍夫曼树。

举例：
假设字符集为：

字符  |  频率
A     |  45
B     |  13
C     |  12
D     |  16
E     |   9
F     |   5

贪心策略先选择频率最低的 E 和 F，合并为一个新节点（频率为 14）。接着继续选择频率最低的 C 和新节点，依次合并，最终构建出一棵最优的霍夫曼树。

贪心选择证明：由于每次选择的都是频率最低的字符进行合并，这样可以保证最短的编码分配给出现频率较高的字符，从而达到压缩的目的。

贪心算法的正确性

为了确保贪心算法能找到问题的最优解，需要验证两个关键性质：

1. 贪心选择性质：证明每一步做出的局部最优选择在全局也是合理的。
2. 最优子结构：证明通过解决子问题可以逐步构造出全局最优解。

例如，活动选择问题和霍夫曼编码问题都具备贪心选择性质和最优子结构，因此使用贪心算法可以得到最优解。但像“背包问题”中的 0-1 背包问题，它的选择过程依赖于后续的物品，因此贪心策略不总是能找到最优解。

贪心算法的优缺点

优点：

• 高效性：贪心算法通常每一步只需要做出简单的选择，时间复杂度较低。例如，活动选择问题的时间复杂度是 O(n log n)，主要是排序的时间。
• 简单性：实现较为直接，通常不涉及复杂的数据结构或回溯。

缺点：

• 局限性：并非所有问题都适合用贪心算法。对于不能分解为最优子结构的问题，贪心算法很难找到全局最优解。
• 需要分析：对于某些问题，必须首先证明贪心策略是最优的才能放心使用。贪心算法本身没有回溯和检查步骤，因此一旦贪心选择错误，可能无法挽回。

总结

贪心算法是一种非常高效的算法思想，在能够满足贪心选择性质和最优子结构的问题中，它能够快速找到问题的最优解。然而，并不是所有问题都适合贪心算法，在使用前需要仔细分析问题的结构。