返回：0400 算法设计与分析总目录 · 上一章：0403 Chap3 图算法基础 · 下一章：0405 Chap5 分治策略

1、学习目标

贪心算法每一步都做当前看来最好的选择。难点不在“选择一个局部最优”，而在证明这种局部选择不会破坏全局最优。

模块 要掌握的内容
贪心范式 局部选择、不可反悔、逐步构造
证明方法 交换论证、领先性证明、割性质
典型问题 区间调度、区间划分、延迟最小化
图算法 Dijkstra、Prim、Kruskal
拓展 最优缓存、聚类

2、贪心算法的判断

贪心适合的问题通常有：

  1. 最优子结构：局部选择后，剩余问题仍是同类问题。
  2. 贪心选择性质：存在某个最优解包含当前贪心选择。
  3. 选择不可反悔：一旦选择，就不再回头调整。

贪心最怕“看起来合理但没有证明”。遇到新题时，要先尝试找反例。

3、区间调度

问题：给定若干活动 [s_i, f_i]，选择最多数量的互不重叠活动。

贪心策略：

1
按结束时间从早到晚排序，每次选择与当前已选活动不冲突且结束最早的活动。

正确性直觉：结束越早，留给后面活动的空间越大。

交换论证：

  1. 设贪心选出的第一个活动为 g，它结束最早。
  2. 任取一个最优解的第一个活动 o。
  3. 因为 g 结束不晚于 o，用 g 替换 o 后仍然可行。
  4. 所以存在一个最优解包含 g。
  5. 递归处理剩余区间。

复杂度主要来自排序：O(n log n)。

4、区间划分

问题：给定若干课程时间段，用最少教室安排所有课程。

贪心策略：

  1. 按开始时间排序。
  2. 用小根堆维护每个教室当前结束时间。
  3. 新课程能接到最早结束教室后面就接，否则新开教室。
1
2
3
4
5
6
7
sort(intervals.begin(), intervals.end());
priority_queue<int, vector<int>, greater<int>> pq;

for (auto [s, f] : intervals) {
    if (!pq.empty() && pq.top() <= s) pq.pop();
    pq.push(f);
}

最少教室数等于任意时刻最大重叠区间数。贪心算法恰好维护了这个下界。

5、最小化最大延迟

单机调度问题：每个任务有处理时间 t_i 和截止时间 d_i，要求安排任务顺序，使最大延迟最小。

延迟：

1
L_i = completion_i - d_i

贪心策略：

1
按截止时间从早到晚执行。

交换论证：若两个相邻任务 i、j 中 d_i > d_j，但 i 排在 j 前面，则交换它们不会增加最大延迟。因此不断消除逆序，得到按截止时间排序的最优序列。

6、最优缓存

问题：缓存容量有限，未来请求序列已知，缺页时应该淘汰谁？

最优策略：

1
淘汰下一次使用时间最晚的对象。

这叫 Belady 最优算法。它不一定能在线使用，因为未来请求通常未知，但它提供了缓存替换算法的理论基准。

7、Dijkstra 最短路

适用于非负权图。

贪心选择：

1
每次从未确定顶点中选择当前 dist 最小的顶点，将其距离定型。

正确性依赖非负权：如果当前 dist[v] 已经最小，任何绕远路再回来都不会更短。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
dist[s] = 0;
pq.push({0, s});

while (!pq.empty()) {
    auto [d, v] = pq.top();
    pq.pop();
    if (d != dist[v]) continue;
    for (auto [u, w] : adj[v]) {
        if (dist[u] > d + w) {
            dist[u] = d + w;
            pq.push({dist[u], u});
        }
    }
}

复杂度 O((V+E) log V)。

8、最小生成树

最小生成树常见两个贪心算法：

算法 贪心选择 数据结构
Prim 从当前树跨出去的最小边 优先队列
Kruskal 全图当前最小且不成环的边 并查集

核心性质是割性质：

1
对任意割，跨越该割的最轻边是安全边，可以加入某棵 MST。

Kruskal 的流程：

  1. 所有边按权重排序。
  2. 从小到大尝试加入。
  3. 若两端点不在同一连通块，则加入并合并。

复杂度通常为 O(E log E)。

9、聚类

最大间距 k 聚类可以用 Kruskal 的思路：

  1. 初始每个点一个簇。
  2. 按边权从小到大合并。
  3. 合并到只剩 k 个簇时停止。
  4. 下一条跨簇最小边就是间距。

直觉：先把距离近的点合并，保留簇之间尽量大的分隔。

10、贪心证明模板

方法 适用
交换论证 排序类贪心，如区间调度、截止时间调度
领先性证明 每一步都证明贪心不落后于任意最优解
割性质 MST、网络结构选择
反证法 假设最优解不含贪心选择，再替换

写证明时尽量避免“显然最优”。把“为什么这个局部选择可以出现在某个最优解中”写出来。

11、易错点

易错点 修正
贪心策略只凭直觉 必须有交换论证或结构性质
区间调度按开始时间排序 正确策略是按结束时间
Dijkstra 用于负权边 Dijkstra 要求边权非负
MST 只选每个点最短边 要考虑全局连通和成环
Prim 和 Dijkstra 混淆 Prim 比边，Dijkstra 比路径

12、复盘清单

检查项 状态
能说明贪心选择性质 待复盘
能证明区间调度的结束时间贪心 待复盘
能用堆写区间划分 待复盘
能解释 Dijkstra 为什么不能有负权边 待复盘
能区分 Prim 和 Kruskal 待复盘
能写一个交换论证 待复盘