贪心算法的两种证明方法

1. 先分清：一直领先，还是逐步交换

贪心算法每次做一个当前看起来最好的选择。证明的任务是说明：这些局部选择连在一起，为什么得到整体最优解。先确认输出合法，再证明没有合法方案能在题目的目标上更好。

课件原文 · PDF p13：Greedy stays ahead: prove that at every stage, no other sequence of choices could do better than our proposed algorithm.

中文：证明在每个阶段，其他选择序列在所比较的指标上都不能优于贪心。

课件原文 · PDF p13：Exchange argument: consider any alternative solution, and gradually transform it to the solution found by our proposed algorithm without making it any worse.

中文：考虑一个替代方案，逐步把它改成贪心方案，并保证每次修改不使它变差。可以从任意合法方案出发，也可以从一个最优方案出发。

2. 始终领先例子：用最少基站覆盖房屋

课件 Problem 原文 · PDF p33：Along the long, straight road from Balladonia (in the West) to Caiguna (in the East), houses are scattered quite sparsely, sometimes with long gaps between two consecutive houses. Telstra must provide mobile phone service to people who live alongside the road, and the range of Telstra’s cell tower is 5km. Task: Design an algorithm for placing the smallest number of cell towers alongside the road, that is sufficient to cover all houses.

中文：在从西边 Balladonia 到东边 Caiguna 的直路上，房屋可能相隔很远。每座基站的覆盖半径为 5 km。安排尽量少的基站，覆盖所有房屋。

1. 把房屋从西向东排序。原因：这样可以确定‘最左边尚未覆盖的房屋’。
2. 找到最左未覆盖房屋 h，把塔放在 h+d。原因：塔再往东就盖不到 h；在仍覆盖 h 的位置里，h+d 能把覆盖范围推得最远。
3. 这座塔的最右覆盖点是 h+2d。把范围内的后续房屋一并跳过。原因：它们已经被同一座塔覆盖，不需要另外建塔。
4. 重复，直到所有房屋被覆盖。若房屋已排好序，扫描 O(n)；否则排序与扫描合计 O(n log n)。这是实现代价，不是最优性的证明。

自写数值例子：房屋位置为 [1, 4, 9, 12, 16, 21, 24] km。假设这些位置离道路东端足够远，符合课件暂时采用的边界条件。

对照一个完整合法方案 A = [4,13,23]：三座塔最终也能覆盖所有房屋。做完相同步数时，6≥4、17≥13、29≥23。比较的是第 k 座塔的位置；两套方案最终都用三座塔，不要求这一组例子的塔数不同。

3. 始终领先证明：归纳以后，还要证明塔数最少

课件 Claim 原文 · PDF p36–37：For all k≥1, the kth tower in the greedy selection is at least as far east as the kth tower in any other valid selection.

中文：第 k 座贪心塔至少和任意合法方案的第 k 座塔一样靠东。下面把索引范围写准确：G 有 r 座，A 有 m 座；只在两者都存在第 k 座时比较，即 1≤k≤min(r,m)。塔按位置从西到东排列。

要证明的阶段性质：对任意完整合法方案 A，aₖ ≤ gₖ。
不是先假设贪心最优，而是先证明这个位置关系。

第 ⑥ 步的完整不等式链是课件 p37 的关键。每个符号都对应一个覆盖端点：

aₖ₋₁ + d ≤ gₖ₋₁ + d < hₖ = gₖ − d < aₖ − d
    ↑归纳假设        ↑触发新塔     ↑gₖ=hₖ+d   ↑反设 aₖ>gₖ

左边说明 hₖ 在 A 前 k−1 座塔的覆盖范围之外；右边说明 A 从第 k 座起都来得太晚。房屋 hₖ 在覆盖缺口里，A 就不是完整合法方案。

阶段关系：aₘ ≤ gₘ
未覆盖见证：hₘ₊₁ > gₘ+d ≥ aₘ+d
结论：不存在 m<r 的合法方案，因此 r=min{|A| : A 覆盖全部房屋}。

空输入不需要任何塔。上面的非空收尾将课件 p38 的 r−1 座反设推广为任意 m<r，属于补充推导；没有使用不存在的第 m+1 座替代塔。

4. 交换例子：磁带上为什么短文件先放

课件 Problem 原文 · PDF p41：A list of n files of lengths Lᵢ which have to be stored on a tape. Each file is equally likely to be needed. To retrieve a file, one must start from the beginning of the tape and scan it until the file is found and read. Task: Order the files on the tape so that the average (expected) retrieval time is minimised.

中文：把 n 个文件安排在磁带上，每个文件被需要的概率相同。读取某个文件时，要从磁带开头扫描到该文件末尾。选择一个顺序，使平均读取代价最小。以扫描长度计代价；固定读取速度只会乘一个常数，不改变最佳顺序。

E = (C₁+C₂+⋯+Cₙ)/n
T = C₁+C₂+⋯+Cₙ
  = nL₁+(n−1)L₂+⋯+2Lₙ₋₁+Lₙ

为什么第一个长度被乘 n？读取任何一个文件都必须先经过它，所以它在 n 个前缀里都出现。第二个只在后 n−1 个前缀里出现。越靠前，长度被重复计入的次数越多。

贪心规则：按文件长度从小到大排列。自写例子先从合法排列 [4,1,3] 出发，逐次换掉相邻逆序：

5. 交换证明：合法、差值、进展、收尾

课件 Claim 原文 · PDF p44：The scaled retrieval time nL₁+(n−1)L₂+(n−2)L₃+...+2Lₙ₋₁+Lₙ is minimised if L₁≤L₂≤...≤Lₙ.

中文：当文件长度按非递减顺序排列时，上面的缩放读取代价 T 最小。下面先用直接变换讲明白，再对应课件的反证版本。

第 ⑤ 步先用读取过程推导。设这两个文件之前已有扫描长度 P；P 是同一段前缀，在交换前后都不变：

Δ = T_after − T_before
  = (2P+x+2y) − (2P+2x+y)
  = y−x
若 x>y，则 Δ<0，因此 T_after<T_before；E_after−E_before=(y−x)/n<0。

同一差值也可以直接从课件的带权长度式算。i 是这两个文件中第一个的位置，K 是所有不受交换影响的贡献：

T_before = K+(n−i+1)x+(n−i)y
T_after  = K+(n−i+1)y+(n−i)x
T_after−T_before = y−x。

第 ⑥ 步的进展量：I(A) 是满足 p<q 且 Lₚ>Lq 的位置对数量，即逆序数。交换相邻的 x>y 后，其他文件仍在两者共同的左侧或右侧，涉及它们的逆序总数不变；只有 x 与 y 这一对消失。因此 I(A′)=I(A)−1。这是对课件 p45 的补充说明。

A₀=A → A₁ → ⋯ → Aₜ（长度非递减）
T(A₀) ≥ T(A₁) ≥ ⋯ ≥ T(Aₜ)=T(G)
A 任意，因此 T(G) ≤ T(A) 对所有合法 A 成立。
G 自身合法，所以它达到最小代价。

反证版本对应课件 p44：假设一个最优排列尚有相邻逆序 x>y；交换后仍合法且 T 严格更小，与‘已最优’矛盾。因此最优排列不能有逆序。等长的相邻文件交换差值为 0，不要求最优解唯一。

6. 同一题，也可以用两种方法证明

两种证明不是两类互斥的算法标签。以课件的活动选择为例：每次选当前兼容活动中结束最早的活动，目标是最大化选中的活动数量。课件 p20–26 用交换论证；下面的始终领先写法是补充推导。

课件 Problem 原文 · PDF p16：Instance: A list of n activities, with starting times sᵢ and finishing times fᵢ. Task: Find a largest number of pairwise compatible activities. Two activities are compatible if their intervals do not overlap.

中文：给出 n 个活动的开始与结束时间，选出最多的两两不冲突活动。本页自写例子使用正时长的半开区间 [s,f)，首尾相接允许兼容，所以判定为 s_next≥f_previous；若原题要求严格间隔，应相应改为严格不等式。

贪心 G=(A,C,E)，对照合法方案 O=(B,D,E)，二者都选 3 个活动。定义 s(x)、f(x) 为活动 x 的开始、结束时间；gₖ、oₖ 为两方案按时间排列的第 k 个活动。

s(oₖ₊₁) ≥ f(oₖ) ≥ f(gₖ)
⇒ oₖ₊₁ 在贪心第 k 步以后仍可选
⇒ 贪心若尚未选第 k+1 个，也不能终止
⇒ f(gₖ₊₁) ≤ f(oₖ₊₁)。

正时长使 oₖ₊₁ 的结束时间严格晚于贪心第 k 步结束时间，因此它也不是已经选择过的旧活动。最后若 O 比 G 多一个，O 的下一个活动仍与 G 兼容，贪心就不应结束，矛盾。所以 |G|≥|O|。这一步把‘结束时间更早’连接到了‘数量更多或相等’。

不断替换，直到 O 用完。G 不能先用完：若后缀仍有与共同前缀兼容的活动，算法还能继续选。于是 G 至少有 |O| 个。用最优 O 出发时，还可说每次替换保持同样的最优数量。

7. 一套可以套用的公式与证明模板

下面是根据课件整理的写作模板，不是一个能自动证明所有贪心算法的万能定理。需要把题目的比较指标、合法性理由、差值和收尾具体填进去。

始终领先模板
1. 固定任意合法方案 A；定义可比的第 k 步状态与指标 P。
2. 证明第 1 步 P(G₁) 不差于 P(A₁)。
3. 假设第 k−1 步关系成立，借此证明第 k 步关系。
4. 假设 A 最终更优，用阶段关系推出它不合法，或贪心不应终止。
5. 所以没有合法方案优于 G，且 G 合法。

交换模板（最小化目标 F）
1. 固定任意 A∈可行解集合。
2. 从 A 构造 A′，并逐项检查 A′ 仍合法。
3. 算 Δ=F(A′)−F(A)≤0。
4. 每次修改让分歧减少或一致前缀变长，并证明有限次结束。
5. 最终到达 G，或某个 B 满足 F(B)=F(G)。
6. F(G)≤F(A) 对所有合法 A 成立，所以 G 最优。

若从最优 O 出发：F(O′)≤F(O)=OPT；O′ 合法又使 F(O′)≥OPT，因此 F(O′)=OPT。每次修改仍最优。最后必须说明它能到达 G 或与 G 目标值相同的规范解。最大化版本反转目标不等号。

E_before = pₓ(P+Lₓ)+pᵧ(P+Lₓ+Lᵧ)+其他不变项
E_after  = pᵧ(P+Lᵧ)+pₓ(P+Lᵧ+Lₓ)+其他不变项
ΔE = E_after−E_before = Lᵧpₓ−Lₓpᵧ。
若 pₓ/Lₓ < pᵧ/Lᵧ，则 ΔE<0，应该把 y 换到前面。
所以最优顺序按 p/L 非递增排列。

8. 怎样选方法，哪里最容易证明漏了

9. 来源与例子范围

主要材料：本地 2026 T3 COMP3121/COMP9101 Module 2: Greedy Algorithms，Raveen de Silva，2-greedy.pdf。引用使用 PDF 实际页码；课件底部印刷编号比 PDF 页码小 1，例如 PDF p37 底部写 36。

房屋 [1,4,9,12,16,21,24]、对照塔 [4,13,23]、反设塔 18、文件 [4,1,3]、活动 A–E 和概率例子均为自写教学数值。带‘补充推导’的内容是对课件提纲的展开，不冒充新的课件原文。

这是现有 Week03 笔记旁的独立贪心专题页。导航归类便于回查，不把整套课件或本专题的内容当作官方第三周教学范围。