贪恋有你的未来

四点以后，日程开始争宠

下午四点，我的桌上还压着五件事项。 两件只要半小时，一件六点前必须交，另两件做完很有价值，却会一口吞掉整个傍晚的时间。

人在这种时候很容易发明 greedy algorithm，只是通常没有给它起这个名字：我们往往会先做最短的，先做最急的，先做回报最高的，或者先把最烦的做掉。 依旧不同的标准，我们会有不同的选择结果。 那么那种方式是最优的呢？

我们建模一下。想象这些事情不再只是待办，而是一组会占据不同时间区间的 activities。 选了一个，就可能让另外几个再也塞不进日程。此时，“最短”听起来很节省，却可能正好横跨两个本来能够前后完成的任务； “最早开始”很积极，却可能把后面的整段时间堵住。 反而是那个最早结束的活动，会最先把时间轴还给未来。

这里有一个很细的转折。 我们并不是因为它眼前最好看而选它 而是因为它离开之后，未来仍保留了尽可能多的可能。

贪心策略贪的不只是当下，更是未来更多的可能与机遇。

--- 再把场景搬到背包。容量 50 kg，三件物品分别是：

- A：10 kg，价值 60； - B：20 kg，价值 100； - C：30 kg，价值 120。

若物品可以切开，按单位重量价值 value / weight 从高到低拿，局部规则一路正确。可一旦物品不准切，即0/1背包问题，同一规则会选择 A 与 B，总价值 160； 真正的最优解却是 B 与 C，总价值 220。

规则没有变笨。 世界只改了一个约束，原来的证明便失去了落脚处。

Greedy 最值得学的，正是这种“落脚处”。 它把问题分成 stages，每一步只留下一个选择，其他可能性从此退场。 于是算法必须回答一个略显严厉的问题：

我关上这些门以后，凭什么确定最优解没有被关在门外？

一个 greedy choice 因而拥有两层身份：

1. locally attractive：它由某个清楚的局部规则选出； 2. globally safe：存在证明说明，选择它不会损失全局最优性。

第一层让算法走起来。第二层让它走完之后仍然可信。

--- Greedy 的基本结构

Greedy algorithm 把问题视为一连串 stages。每个 stage 都进行一次当前看来最好的选择，并通常不再回头。

一份完整的 greedy 解答会说明：

- State：目前已经选择了什么，剩下什么； - Choice rule：下一步按哪个 key 或 ratio 选择； - Feasibility：怎样判断新选择不会破坏约束； - Discard rule：哪些候选项可以永久忽略； - Termination：什么时候停止； - Correctness hinge：为什么局部选择是 safe choice； - Complexity：排序、扫描、heap、Union-Find 等操作分别花多少时间。

常见的逻辑误区是：

“每次选择最优的选项，因此最后得到的是最优解。”

我们之前学习网络流的时候提过，一味的贪于眼前的流量最大化，最后导致是反而是整体的拥挤与瘫痪。

而我们要证明的恰好是：

在这个问题背景下的局部最优，为什么能推出全局最优？

--- 两把证明方式：Exchange 与 Staying Ahead

Exchange argument：你很棒，你不比他们差

Exchange argument 交换论证会从某个最优解 O 出发。找到它与 greedy solution G 的第一个不同位置，把 O 在这里的选择换成 greedy choice，并证明：

1. 交换后仍然 feasible； 2. objective value 不会变差； 3. 与 G 相同的 prefix 至少增长了一位。

不断交换后，O 会被改造成 G，同时从未变差。 既然起点已经最优，终点 G 也只能最优。

它的通用骨架是：

我们需要指出交换后为什么不会制造冲突，以及为什么 objective 没有下降。 即证明交换是有效的。同时整体又不变差。

exchange argument的逻辑就是： 你是健康的，同时你不比他们差。

Greedy stays ahead：与时俱进 Staying-ahead proof 比较 greedy solution 与任意可行解在每个 stage 的进度。

你通常要定义一个可比较的量，例如：

- 第 k 个活动的结束时间； - 第 k 座塔的位置； - 处理前 k 个任务后的最大 lateness； - 已经覆盖到的最右位置。

然后证明：

证明往往是 induction：

- base case：第一次选择由 greedy rule 直接保证； - inductive step：假设第 k - 1 步不落后，证明第 k 步仍不落后； - termination：既然每一步都不落后，其他方案不可能用更少选择完成，或取得更优目标。

greedy stays ahead的逻辑是： 与时俱进，每步不落下乘

两者只是从不同角度保存同一个东西：greedy choice 之后，最优未来依然存在。

下面我们用例子来学习一下两者的证明方式。

--- Activity Selection：最早结束的人，为未来留下最多空气

问题

给定 n 个 activities。活动 i 在时间 sᵢ 开始、fᵢ 结束。 两个时间区间不重叠时，它们 compatible。 目标是选择数量最多的 pairwise compatible activities。

一个很诱人的错误策略是“先选持续时间最短的活动”。 它看起来占用最少时间，却可能正好横跨两个本可同时选择的活动。 短，不代表不挡路。

正确策略是：

1. 我们按结束时间 fᵢ 非递减排序（常见的就是时间复杂度 O(nlogn)的merge sort）； 2. 按顺序扫描排序后的活动； 3. 若当前活动的开始时间不早于最后一个已选活动的结束时间，即两者不冲突时，选择它； 4. 否则冲突，我们舍弃这个选择。

Greedy choice 不是“最短”，而是“最早把时间轴还给未来”。

我们下面来证明这样的贪恋未来的策略为什么会保证全局最优。 Exchange argument

设 greedy 选择按结束时间排列为：

取任意最优解：

设 k 是二者第一次不同的位置。此时前 k - 1 个活动相同。因为 greedy 在所有与前缀 compatible 的活动中选择最早结束者，所以：

把 O 的 oₖ 换成 gₖ：

- gₖ 与共同前缀不冲突，因为 greedy solution 本身合法； - gₖ 不晚于 oₖ 结束，所以凡是能排在 oₖ 后面的活动，也能排在 gₖ 后面； - 活动数量没有减少。

交换后的方案仍然最优，却与 G 多共享一个位置。重复这个过程，最终可以得到 greedy solution。因此 greedy solution 也最优。

Complexity

- 排序：O(n log n)； - 单次扫描：O(n)； - 总时间：O(n log n)； - 若输入已经按结束时间排序，则扫描部分只需 O(n)。

只需保存“最后一个已选活动的结束时间”。若每次都重新检查全部已选活动，虽然答案仍对，复杂度分析却会平白长出一截。

一个约束变化，Greedy 便退场

若目标改为“最大化所选活动的总持续时间”，earliest finish 不再正确。 此时一个长活动可能比多个短活动更有价值，交换时也不能再说“每个活动贡献相同的 1”。

这类问题在课程中转向 DP（我们会单独讲解DP，这里暂不展开）：

同一张时间轴，目标函数一换，证明的地基也换了。

---

Cell Towers：让第 k 座塔尽量站得靠右

房屋位于一条直线上，一座 tower 能覆盖半径 r 内的房屋。目标是用最少 towers 覆盖全部房屋。

可以先思考一下。

solution: 先把房屋位置排序。找到最左侧尚未覆盖的房屋 x，把新 tower 放在 x + r。它恰好仍能覆盖 x，同时向右延伸得最远。随后跳过所有已覆盖房屋，重复。

Staying-ahead proof 这次我们使用staying ahead来证明： 设 greedy 的第 k 座塔位于 gₖ，任意其他可行方案的第 k 座塔位于 aₖ。证明：

Base case: 第一座塔为了覆盖最左房屋，最右只能放到 x + r，greedy 正好放在那里。

Induction: 假设第 k - 1 座 greedy tower 不比另一方案靠左，那么 greedy 覆盖到的最右位置也不更差。于是 greedy 的第 k 个未覆盖房屋不会比另一方案更靠左；把 tower 放到该房屋右侧 r 的位置后，第 k 座塔仍不会落后。

因此，若某个方案用 q 座塔覆盖全部房屋，greedy 用前 q 座塔至少覆盖同样远。Greedy 不可能需要更多 towers。

Complexity

- 房屋已经排序：O(n)； - 否则排序后扫描：O(n log n)。

--- 勿逐其相，见其精骨

只看 Activity Selection，很容易把 greedy 记成“按结束时间排序”；只看 Cell Towers，又容易把它记成“从左向右扫”。 我们聊到归约时谈到过面对不同相的问题，更重要的是根本的精骨。

把两题并排，才看见共同结构：

一个把边界压向左，一个把边界推向右，方向相反，逻辑却相同：当前选择把剩余 instance 留得不比任何其他方案更差。

这也是认知科学里 analogical comparison 真正有用的地方。 Gentner、Loewenstein 与 Thompson 在三个 negotiation-learning studies 中发现，初学者比较两个 cases，比把它们分开阅读更容易抽取可迁移的 relational schema；Gentner, Loewenstein & Thompson, 2003

下一次题目把 activities 换成广播时段、把 towers 换成充电站时，不必检索名词。

看边界怎样移动，未来怎样被保留。

--- Optimal Ordering：顺序本身就是答案

有些 greedy 题不选择 subset，而是给全部对象排顺序。这里 exchange argument 常常特别自然：只要某对相邻元素顺序不对，就交换它们，并证明 objective 改善或不变。 不断消除 adjacent inversions，最后得到目标排序。

Tape Storage

文件顺序存放在 tape 上。读取一个文件必须从 tape 开头一路扫描到它。文件 i 长度为 Lᵢ，被请求的概率为 pᵢ。目标是最小化 expected retrieval time。

对两个相邻文件 i, j 比较两种顺序。其他文件受到的等待时间相同，只需比较这两个文件贡献：

第一种不差于第二种，当且仅当：

也就是：

因此应按 pᵢ / Lᵢ 非递增排列。若所有请求概率相等，就退化为按文件长度从短到长。

这个 ratio 不是灵感拍出来的。它是把两个相邻元素交换后，目标函数亲自交出的答案。

Minimising Maximum Lateness

每个 job i 有 processing time ℓᵢ 与 deadline dᵢ。 所有 job 都必须完成，单机一次只能处理一个。 若完成时间为 fᵢ，lateness 是：

目标是最小化最大 lateness。

正确规则是按 deadline 递增排序，即 Earliest Deadline First。

证明仍看相邻 inversion：若相邻两个 jobs 满足 dᵢ dⱼ，却让 i 在 j 前，把它们交换。交换不会影响更早或更晚 jobs 的完成时间；而对这两项，较早 deadline 的 j 被提前，i 虽被推后，但它拥有更晚 deadline。可以证明两者的最大 lateness 不会增加。

不断交换所有 deadline inversions，最终得到 deadline-sorted order。

注意目标是 maximum lateness。若改成平均完成时间、带权等待时间或允许选择部分 jobs，规则都可能变化。 Greedy rule 从来不脱离 objective 单独存在。

Huffman Coding：每次合并两个最轻的未来

给定符号集合与频率 fₓ，希望构造 prefix code，使 expected codeword length：

最小。

Huffman algorithm：

1. 为每个符号建立一个叶节点，权重为频率； 2. 反复取出权重最小的两个树； 3. 建立新父节点，权重为两棵子树权重之和； 4. 把新树放回集合； 5. 直到只剩一棵树。

使用 min-heap 时，n - 1 次合并各含两次删除和一次插入，总时间为 O(n log n)。

为什么偏偏是最小的两个？

Huffman proof 的核心有两层：

1. 在某棵最优 prefix-code tree 中，频率最低的两个符号可以被安排为最深处的一对 siblings； 2. 把这对 siblings 合并为一个权重等于频率之和的 pseudo-symbol 后，剩余问题仍是同一种最优化问题。

第一层是 greedy-choice property，第二层是 optimal substructure。合并不是把问题弄丢，而是把两个一定可以一起沉到底部的叶子装进同一个信封，交给更小的实例继续处理。

Directed Graph Structure：先把环压扁

官方 Greedy slides 的图论部分还包括 SCC、condensation graph 与 topological ordering。它们未必都应被称为 greedy algorithm，但在课程题目中常作为后续算法的预处理。

Strongly Connected Components

在 directed graph 中，若 u 能到达 v，且 v 也能到达 u，二者位于同一个 strongly connected component。

- Tarjan：O(|V| + |E|)； - Kosaraju：两次 DFS，同样是 O(|V| + |E|)。

把每个 SCC 压缩成一个节点，跨 SCC 的边保留下来并去重，得到 condensation graph。它一定是 DAG：若压缩后仍有 directed cycle，环上的 components 本应互相可达，早就该合并成同一个 SCC。

Topological Ordering

DAG 的 topological order 是一个线性顺序，使每条边 (u, v) 都满足 u 在 v 前。

Kahn's algorithm：

1. 找出全部 in-degree 为 0 的 vertices； 2. 反复取出其中一个，放入 ordering； 3. 删除它的 outgoing edges； 4. 新出现的 in-degree 0 vertices 加入候选集合。

每个 vertex 与 edge 只处理常数次，因此时间为 O(|V| + |E|)。

若算法无法输出全部 vertices，图中存在 directed cycle。环上的每个点都在等前驱先离开，大家礼貌得近乎死锁。

Dijkstra：一旦落锤，距离不再改变

Problem

给定 directed graph G = (V, E)、source s 与非负 edge weights，求 s 到每个 vertex 的 shortest-path distance。

设：

- S：shortest distance 已经确定的 vertices； - d[v]：从 s 到 v、且 intermediate vertices 都在 S 中的最短已知路径长度。

初始化：

每一步：

1. 在 V \ S 中选择 d[v] 最小的 vertex v； 2. 把 v 加入 S，此后 d[v] 被视为最终答案； 3. 对每条 outgoing edge (v, z) 做 relaxation：

Correctness hinge

为什么当前最小的 tentative distance 可以永久落锤？

假设 v 是下一位加入 S 的 vertex，却存在更短路径 P 从 s 到 v。沿 P 从 s 出发，找第一个离开 S 的 vertex y。

到达 y 的路径前缀只使用 S 中的 intermediate vertices，因此算法当前已经知道一条到 y、不长于该前缀的路径：

由于后续 edges 非负：

而 v 是 V \ S 中 d 值最小者：

于是 d[v] ≤ weight(P)，与“P 比 d[v] 更短”矛盾。

非负权重就在这条链中工作。如果允许负 edge，离开 S 后路径可能突然降价，已经落下的锤子便可能砸错地方。

Complexity

令 n = |V|, m = |E|。

使用 array：

- 每轮线性扫描找最小 d，共 n 轮：O(n²)； - 每条 edge 最多 relaxation 一次：O(m)； - 总时间：O(n² + m)，simple graph 中可写为 O(n²)。

使用支持 decrease-key 的 augmented min-heap：

- n 次 extract-min：O(n log n)； - 至多 m 次 decrease-key：O(m log n)； - 总时间：O((n + m) log n)； - 若所有 vertices 从 s 可达，则 m ≥ n - 1，可简写为 O(m log n)。

课程 slides 特别提醒：Fibonacci heap 可给出 O(m + n log n)，但属于课程范围外的数据结构；若题目没有提供，不要只写一个更漂亮的 bound 然后把实现细节留给空气。

Minimum Spanning Tree：跨过 cut 的最轻边

Cut property

设 connected undirected graph 的 edge weights 两两不同。对任意非空真子集 S ⊂ V，令 e 是连接 S 与 V \ S 的最轻 edge，则 e 属于每一棵 MST。

证明用 exchange：

- 若某棵 MST T 不含 e，把 e 加入 T 会形成一个 cycle； - 该 cycle 必然还有另一条 edge e' 穿过同一个 cut； - 因为 e 是唯一最轻 crossing edge，w(e) < w(e')； - 用 e 替换 e' 仍得到 spanning tree，却总权重更小，矛盾。

这条 lemma 是 Kruskal 正确性的发动机。

Kruskal

1. 按 edge weight 递增排序； 2. 初始 forest 含所有 vertices，但没有 edges； 3. 依次检查 edges； 4. 若 edge 两端属于不同 connected components，就加入 forest 并合并 components； 5. 得到 n - 1 条 edges 后停止。

Union-Find 维护 connected components：

- Find(v) 返回所在集合代表； - Union(u, v) 合并两个集合。

课程使用 size heuristic 时，树高 O(log n)，所以 Find 与 Union 均为 O(log n)。排序 m 条 edges 需要 O(m log m) = O(m log n)；其余 Union-Find 操作也是 O(m log n)，总时间为：

若 edge weights 有 ties，Kruskal 仍能找到 MST，只是 MST 未必唯一。证明时不要继续声称“这条 edge 属于每一棵 MST”；安全版本是：存在一棵 MST 包含当前可选的某条最轻 crossing edge。

Prim 与 Kruskal 的分工

额外期末复习资料还点名了 Prim：

- Prim：维护一棵正在生长的 tree，每次选择连接 tree 与外部的最轻 edge； - Kruskal：维护一片 forest，每次选择不会制造 cycle 的全局最轻 edge。

两者都依赖 cut property。Prim 像从一座岛向外铺桥；Kruskal 则让很多小岛同时结盟，直到只剩一个国家。

k-Clustering：Kruskal 在还剩 k 个 components 时停下

Greedy slides 最后把 Kruskal 延伸到 maximum-spacing k-clustering。给定 complete weighted graph，希望把 vertices 分成 k 个 clusters，并最大化不同 clusters 之间最近一对 points 的距离，也就是 spacing。

算法几乎是 Kruskal：

1. 按 edge weight 递增处理； 2. 用 Union-Find 合并不同 components； 3. 当恰好剩下 k 个 components 时停止，不再把整张图连成一棵 tree。

为什么这时 spacing 最大？设算法产生 clusters C₁...Cₖ，下一条会连接两个不同 clusters 的 edge 权重为 d。当前 clustering 的 spacing 就是 d。任意另一种 k-clustering 若想拥有大于 d 的 spacing，就不能把算法停止前通过权重至多 d 的 accepted edges 连在一起的任何两点拆到不同 clusters；这些连接已经把 vertices 压成 k 个 components。另一方案也只有 k 个 clusters，因此只能逐个容纳这 k 个 components，无法得到更大的 spacing。

若输入是 n 个 points 的 complete graph，有 Θ(n²) 条 edges，排序主导：

总结一下我们讲的题目

| 题目结构 | 典型 Greedy rule | 证明 hinge | 常见陷阱 | |---|---|---|---| | 选最多个 compatible intervals | earliest finish | exchange | shortest interval、earliest start | | 覆盖直线上的点 | tower 放在最左未覆盖点右侧 r | stays ahead | tower 直接放在房屋上 | | tape expected access | 按 pᵢ / Lᵢ 递减 | adjacent swap | 只按概率或只按长度 | | minimize maximum lateness | deadline 递增 | adjacent swap | 按 processing time | | prefix coding | 合并两个最小频率 | sibling lemma + induction | 合并两个最大频率 | | non-negative SSSP | 最小 tentative distance | first vertex leaving S | negative edges | | MST | 最轻 safe edge | cut property | 把 shortest-path tree 当 MST |

表格用来检索，不用来代替证明。 题目一旦换 objective 或 constraint，我们需要重新检查 exchange 是否仍保持 feasibility 与 value。

考场写法：让阅卷者不必猜

COMP3121 官方材料强调 plain English algorithm description，而非代码或 pseudocode。一份稳定的 greedy 答案可以按以下顺序组织：

1. Algorithm

- 输入是否先排序，按哪个 key，ties 怎样处理； - 维护哪些 state； - 每次选择谁； - 怎样判断 feasible； - 何时停止； - 输出什么。

2. Correctness

先写 claim，再明确证明方法：

不要证明“算法做了它说会做的事”；要证明“它做完后为什么是最优”。

3. Time complexity

逐项核算：

然后再简化 dominant term。O(n log n) + O(n) 当然是 O(n log n)；但若题目已排序，就别替它再交一次排序税。

常见的遗漏细节

1. 规则没有说完整：只写“选择最小的”，没说按什么量、在什么候选集合中最小。 2. 证明只覆盖 intended solution：说明 greedy 输出合法，却没有比较其他可行解。 3. Exchange 后 feasibility 未证明：换完对象可能产生 overlap、cycle 或容量冲突。 4. Dijkstra 忘记 non-negative：正确性证明中最关键的不等式直接失效。 5. MST 与 shortest paths 混淆：MST 最小化整棵树总权重，不保证 root 到各点路径最短。 6. 复杂度只写最终答案：没有解释排序次数、heap operations 或每条 edge 被处理几次。

--- 合上文章以前，让记忆走一遍

我们先别回看上文，口头回答：

1. Activity Selection 为什么选 earliest finish，而不是 shortest duration？ 2. Dijkstra proof 中，non-negative weights 究竟用在哪一个不等式？ 3. Kruskal 加入一条 edge 时，哪个 cut 证明它是 safe 的？ 4. 笔者是不是帅哥？

如果第四位的回答是false，现在可以出门右转惹 如果可以说出算法步骤，却想不起那条 inequality、那个 first difference 或那个 cut，说明我们记住的是动作，还没有记住允许动作发生的理由。 我们可以重点重读一下证明的 hinge，比从头再扫一遍更有用。

---

Greedy 的外表是果断：选择、删除、不回头。

它的内核却很谨慎。 Exchange argument 证明我们随时可以把某个最优解拉回 greedy 的轨道； staying ahead 证明这条轨道从未落后； cut property 与 Dijkstra invariant 则把“安全”翻译成图上的精确条件。

“我做出这个局部选择以后，哪一种最优未来仍被保留下来了？”

不是所有的问题都适用于贪心策略，能回答它，greedy choice 才不是盲目的贪心。

最后一句话结束吧： 我贪恋的何止是当下，是你最有可能出现的未来。