外观
20 - 贪心算法:为什么局部最优有时能得到全局最优
前置阅读:02 - 如何把业务问题抽象成算法模型、08 - 排序算法怎么选、10 - 区间问题统一解法。
本文关注“为什么可以贪心”,区间端点、扫描线和会议室模型不在此重复展开。
摘要
一台机器收到多个固定时段的任务,怎样安排才能完成最多任务?每次选择最早结束的任务是一种贪心策略,但“给后续留下更多时间”的直觉还不够,必须证明这样选择不会丢掉最优答案。
贪心算法按某个规则逐步选择,并固定已经作出的决定,不再回退。局部最优是当前一步按该规则选出的最佳候选,全局最优是所有合法完整方案中目标值最好的方案。本文先用区间调度解释两者为何能联系起来,再用零钱兑换反例和 Huffman 编码说明这一联系的适用条件。
1. 区间调度
本例中,每个任务的起止时间固定,有正执行时长(start < end),不可拆分或中断;只有一台机器,任务之间没有前置依赖,目标是选择数量最多的互不重叠任务,而不是收益最高的任务。
时间采用半开区间 [start, end),即包含开始时刻、不包含结束时刻,因此 [1,4) 与 [4,6) 可以接续。已选任务的最后结束时刻记为 lastEnd;满足 start >= lastEnd 的任务称为当前的可行任务。
策略是每次选择最早结束的可行任务。它结束得越早,后续任务允许开始的时间就越早;按开始时间或时长排序则没有这个保证。完整输入输出和暴力基线见业务问题抽象,这里保留证明所需的模型。
下面是方法片段,需要放在类中、导入 java.util.List 并定义 Task(见第 5 节)。输入列表及元素须非 null,列表须支持排序,任务须满足上述条件;代码不校验任务区间,并会直接改变输入列表的顺序。
java
static int selectMost(List<Task> tasks) {
tasks.sort(java.util.Comparator.comparingInt(Task::end));
int count = 0;
int lastEnd = Integer.MIN_VALUE;
for (Task task : tasks) {
if (task.start() >= lastEnd) {
count++;
lastEnd = task.end();
}
}
return count;
}代码先按结束时间排序,再扫描一次。count 保存已选数量,lastEnd 保存最后一个已选任务的结束时刻;选中后更新它,跳过时保持不变。Integer.MIN_VALUE 是 int 的最小值,使第一个任务不受尚不存在的前驱限制。空列表返回 0。
2. 交换论证
交换论证是把一个最优方案中的选择替换成贪心选择,并证明替换后仍合法、目标值不变差。它不要求所有最优方案都采用贪心选择,只需证明至少存在一个这样的最优方案。
对非空任务集合,设贪心选出的最早结束任务为 G,任取一个最优方案,其按时间排列的第一个任务为 A:
- 因为
G最早结束,所以G.end <= A.end。 - 原方案中每个后续任务
B都满足B.start >= A.end,因此也满足B.start >= G.end,仍能接在G后面。 - 把
A换成G,只换了一个任务,数量不变,后续任务也不冲突。因此新方案仍然最优。
正时长条件还保证 G 不可能已经在原方案的后续位置:若它在 A 之后,便有 G.start >= A.end 且 G.end > G.start,与 G.end <= A.end 矛盾。这样替换不会重复选择同一个任务。
这证明了第一步可以安全固定,但还要解释后续步骤。选定 G 后,只保留 start >= G.end 的任务,剩下仍是同一类区间调度问题。如果最优方案的剩余部分不是这个子问题的最优解,就可以换成数量更多的剩余方案,使总数量增加,与原方案最优矛盾。因此可以对剩余问题重复同一论证,直到没有可行任务;空集合的答案为 0。由此才得到整个算法的正确性。
3. 贪心失效反例
假设每种硬币数量不限,面额为 [1,3,4],要凑出金额 6,目标是硬币数量最少。每次取不超过剩余金额的最大面额,会得到 4+1+1,共三枚;而 3+3 只需两枚。没有面额为 6 的硬币,所以两枚已经最优。
这里无法照搬区间调度的交换步骤:若把最优方案中的一枚 3 换成 4,总金额就改变了,还必须调整其他硬币。固定第一枚为 4 后,剩余金额 2 只能用两枚 1,已经排除了两枚硬币的最优方案。
因此“零钱兑换永远取最大硬币”只对某些币制成立,不能当成通用算法。
4. 识别贪心问题
上面的区间证明体现了两个条件:
- 贪心选择性质:存在一个最优解包含当前局部选择,所以可以安全固定这一步;区间证明中的替换建立了这一点。
- 最优子结构:固定选择后,完整最优解的剩余部分必须是剩余子问题的最优解,否则替换剩余部分就能改善完整方案。
剩余问题仍是同类问题,才能继续应用同一个选择规则。但仅有最优子结构还不够:零钱兑换也可以拆成剩余金额问题,却不能安全地先选最大面额。
除交换论证外,还可以用反证法(假设存在更好的方案,再推出矛盾)或保持领先法(逐步证明贪心方案在关键指标上始终不落后于其他方案)。选择哪种方法取决于问题结构。
一个实用判断流程是:
- 当前选择一旦作出,是否永不回退?
- 是否能把任意最优解转换为包含当前选择的另一个最优解?
- 转换后剩余部分是否仍是同类问题?
- 目标或约束稍作变化时,证明中的哪一步会失效?
如果只能解释“样例上每次取最大看起来最好”,就还没有建立贪心算法。
5. 完整可运行示例:区间选择与 Huffman 代价
下面的完整类对应文件名 GreedyDemo.java,只使用 Java 标准库。代码使用 record,按正式语言特性需要 Java 16 或更高版本。
schedule 返回具体任务列表,并先复制输入,因此不会改变调用方列表的顺序;它仍要求输入及元素非 null、任务满足第 1 节的模型,Task 构造器没有校验起止时间。
第二个方法计算 Huffman 编码的代价。先理解模型:给符号分配二进制码,且任何符号的码都不是另一个码的前缀,这叫前缀编码,解码时可以逐个确定符号边界。用二叉树表示编码时,符号在叶子上,从根走到叶子的 0/1 路径就是它的码;路径经过的边数称为叶子的深度,也就是编码长度。目标是在给定频率下最小化 Σ(频率 × 编码长度)。
huffmanCost 用小顶堆(堆顶保存最小值的优先队列)反复取出两个最小频率,合并为它们的和,再放回堆。它只计算总代价,不构造树或返回各符号的码字;合并为何对应编码代价,见第 6 节。
输入频率数组须非 null。代码拒绝负频率,忽略零频率;空数组或只有一个正频率时,没有合并,返回 0。单一符号的 0 对应允许空码字的树模型,实际编码格式若要求至少一位,需另定规则。使用 long 避免了 int 累加溢出,但代码没有检查 long 溢出,所有合并值和累计代价仍须在其范围内。
java
import java.util.*;
/**
* 可运行示例:贪心算法:为什么局部最优有时能得到全局最优。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class GreedyDemo {
record Task(int start, int end) {}
static List<Task> schedule(List<Task> input) {
// 复制输入,避免排序改变调用方持有的列表顺序。
List<Task> tasks = new ArrayList<>(input);
// 贪心标准:结束越早越优先;结束时间相同如何排序不影响最大数量。
tasks.sort(Comparator.comparingInt(Task::end));
// out 保存已选择的互不重叠任务,也便于调用方查看具体方案。
List<Task> out = new ArrayList<>();
// 尚未选择任务时,任何合法的 int 起点都可以被接受。
int end = Integer.MIN_VALUE;
// 每次选择最早结束的可行任务,为后续留下最大空间。
for (Task t : tasks) {
// 半开区间语义下,当前起点等于上个终点时不冲突。
if (t.start() >= end) {
out.add(t);
// 后续任务只需与最后一个已选任务比较,因为选择集按结束时间递增。
end = t.end();
}
}
return out;
}
static long huffmanCost(int[] frequencies) {
// 小顶堆保证每轮都能以 O(log n) 代价取出两个最小频率。
PriorityQueue<Long> q = new PriorityQueue<>();
for (int f : frequencies) {
// 频率为 0 的符号不会出现在编码中;负频率属于非法业务数据。
if (f < 0) throw new IllegalArgumentException("frequency must be >= 0");
if (f > 0) q.offer((long) f);
}
// 每次合并值就是这批叶子统一增加一层所产生的新增编码代价。
long total = 0;
// 反复合并两个最小频率,使高频符号尽量靠近树根。
while (q.size() > 1) {
long first = q.poll();
long second = q.poll();
long merged = first + second;
// 使用 long,避免大量频率累加时 int 溢出。
total += merged;
// 合并节点重新参与竞争,直到堆中只剩整棵树的根。
q.offer(merged);
}
return total;
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
System.out.println(
schedule(
List.of(new Task(1, 4), new Task(3, 5), new Task(5, 7), new Task(8, 9))
)
);
System.out.println(huffmanCost(new int[] { 5, 9, 12, 13, 16, 45 }));
}
}6. Huffman 思想
在二进制前缀编码、频率固定且不限制最大码长的模型下,Huffman Coding(Huffman 编码)反复合并频率最小的两个节点,构造最优前缀编码树。频率较高的符号若有较短的码,总编码代价就可能更低;但怎样安排整棵树,仍需要证明,不能仅凭这个直觉。
6.1 手工推演
对完整示例中的频率 [5, 9, 12, 13, 16, 45],手工推演如下。表中“堆中剩余值”按数值排序展示,不代表堆的内部存储顺序。
| 轮次 | 取出的两个最小值 | 合并值 | 累计代价 | 堆中剩余值 |
|---|---|---|---|---|
| 1 | 5、9 | 14 | 14 | 12、13、14、16、45 |
| 2 | 12、13 | 25 | 39 | 14、16、25、45 |
| 3 | 14、16 | 30 | 69 | 25、30、45 |
| 4 | 25、30 | 55 | 124 | 45、55 |
| 5 | 45、55 | 100 | 224 | 100 |
224 不是频率之和,而是所有字符“频率 × 编码长度”的总和。每次合并后,参与合并的叶子深度都增加 1,因此把合并值累加起来,恰好得到最终加权路径长度。
完整示例的区间部分依次选择 [1,4)、跳过 [3,5)、选择 [5,7) 和 [8,9)。因此两行预期输出为 [Task[start=1, end=4], Task[start=5, end=7], Task[start=8, end=9]] 和 224。这些是手工推演结果。
6.2 为什么选择两个最小值
考虑至少两个正频率符号的情况。二进制编码树可以去掉只有一个子节点的内部节点,这会缩短其下方所有码字而不破坏前缀性质。因此可以在每个内部节点都有两个子节点的树中寻找最优解。这样的树存在一对最深的兄弟叶子,即拥有同一个父节点的两个叶子。
设较小频率为 a,较大频率为 b,浅层深度为 d1,深层深度为 d2,其中 a <= b、d1 <= d2。把低频符号放深层、高频符号放浅层,代价变化为 (a*d2 + b*d1) - (a*d1 + b*d2) = (b-a)*(d1-d2) <= 0。因此可以通过交换,让两个最小频率占据最深的兄弟位置,而不增加总代价。存在这样的最优树,就说明这对符号可以安全合并。
把它们收缩为频率 a+b 的一个叶子,原树代价等于收缩后树的代价再加 a+b,因为这两个符号展开时各增加一层。若收缩后的树不是剩余问题的最优树,就能换成更好的树再展开,降低原树代价,产生矛盾。因此剩余部分也最优,可以继续合并两个最小值。这与区间调度一样,先证明当前选择安全,再证明剩余问题可以继续求解。
7. 复杂度、边界与测试
- 区间调度的排序是
O(n log n),扫描是O(n),结果列表最多占O(n)。 - Huffman 中令
n为输入频率数、m为正频率数。本实现逐个入堆,最多进行m-1次合并(m <= 1时没有合并);时间上界为O(n + m log(m+1)),常简写为O(n log n),堆空间为O(m),不超过O(n)。 - 区间若采用闭区间语义,
start == end是否冲突必须由业务定义,代码中的>=不能机械照搬。 - Huffman 适合已知或可估计频率的无损编码;频率快速变化时,静态树可能不再合适。
- 建议测试:空任务、完全重叠、首尾相接、相同结束时间;空频率、单一符号、含 0、超大频率与负频率。
区间调度可与枚举全部子集的基线做差分测试,即对同一输入比较不同实现的结果。返回具体方案时,还应检查任务是否来自输入、是否互不重叠;存在多个最优方案时,比较最大数量,不必要求任务集合完全一致。Huffman 可对极小频率集合枚举合并顺序,或在零频率、单一符号等规则一致的前提下与成熟库结果比较。
测试可以发现实现偏差,但有限样例不能替代正确性证明。零时长、反向区间及溢出输入需要先确定规则,不能把代码接受输入等同于算法保证正确。
8. 工程取舍
贪心的选择过程往往只需维护少量状态,但完整算法未必适合流式输入:本例区间调度仍需先获得全部任务并排序,Huffman 也需保存候选频率。尤其是任务陆续到达、未来输入未知的在线调度,不能直接沿用这里的离线最优性保证。目标或约束变化后,同样要检查原证明是否成立:
- “任务数量最多”改为“收益最高”,通常进入加权区间动态规划;
- 单资源改为多机器,或增加依赖和截止期,可能需要图算法、流算法(用网络流量表达分配)或整数规划(在整数决策变量和约束下优化),具体方法取决于完整模型;
- Huffman 的频率持续变化时,静态编码树需要重建或改用自适应方案;
- 线上近似调度还要处理公平性、饥饿(某些任务长期得不到执行机会)和资源隔离,这些不由当前数量最优的证明自动覆盖。
9. 容易踩的坑
- 看到最大、最小就直接贪心。
- 只用几个样例验证,没有正确性证明。
- 排序比较器与贪心规则不一致。
- 没有区分数量最优与具体方案的稳定性。本例正时长任务结束时间相同时,平局选择规则(tie-break)不影响最大数量,但可能改变选中的任务;若业务要求固定方案,需要另行约定。
- 实际目标包含多个权重,却优化了单一指标。
10. 总结
贪心算法的价值不在于选择快,而在于能证明当前选择不会排除全局最优解。
- 先写清目标与约束,局部最优不天然推出全局最优。
- 证明当前选择安全后,还要证明剩余部分最优,才能逐步得到完整最优解。
- 目标或约束变化时,回到证明中检查失效的步骤,再决定是否继续使用贪心。
当局部选择无法安全固定时,继续阅读动态规划的状态与转移。