替换论证

概述

替换论证（Exchange Argument）是证明贪心算法正确性的核心技术。其基本思路是：取任意一个最优解，找到它与贪心解的第一个不同决策点，将最优解中的选择替换为贪心选择，证明替换后的解仍然是最优的，然后通过归纳完成证明。替换论证与动态规划中的剪切-粘贴法（Cut-and-Paste）有相似之处，但适用场景不同。

定义

替换论证（Exchange Argument）

替换论证是一种证明贪心算法产生最优解的技术，其标准流程为：

1. 取最优解：设 $S^{\ast }$ 是问题的一个任意最优解
2. 找差异：找到 $S^{\ast }$ 与贪心解 $S_G$ 的第一个不同决策点
3. 替换：将 $S^{\ast }$ 在该决策点上的选择替换为贪心选择，得到新解 $S^{\prime }$
4. 证明不变：证明 $S^{\prime }$ 的代价不劣于 $S^{\ast }$（即 $S^{\prime }$ 也是最优解）
5. 归纳：对剩余子问题重复上述过程，最终将 $S^{\ast }$ 完全转化为贪心解

核心性质

1. 与剪切-粘贴法的区别

特征	替换论证（贪心）	剪切-粘贴法（动态规划）
适用算法	贪心算法	动态规划
证明目标	贪心选择包含在某个最优解中	最优解包含子问题的最优解
操作方式	替换最优解中的一个选择	替换最优解中的一个子解
归纳方向	从第一个决策点向后归纳	从最小子问题向上归纳

2. 应用一：活动选择问题（Theorem 15.1）

在 活动选择问题 中，证明”选择最早结束的活动 $a_m$ 是最优的”：

1. 设 $A=\{a_j,\dots \}$ 是一个最大兼容子集，$a_j$ 是其中最早结束的活动
2. 贪心选择 $a_m$ 是所有活动中最早结束的，所以 $f_m\le f_j$
3. 因为 $A$ 是兼容的且 $a_j$ 是 $A$ 中最早的，所以 $A$ 中所有活动与 $a_j$ 兼容
4. 因为 $f_m\le f_j$，所以 $A$ 中所有活动也与 $a_m$ 兼容
5. 将 $a_j$ 替换为 $a_m$，得到 $A^{\prime }=A\setminus \{a_j\}\cup \{a_m\}$，$|A^{\prime }|=|A|$，仍为最大兼容子集

关键洞察：替换后解的规模（兼容活动数）不变，因此仍然是最优的。

3. 应用二：哈夫曼编码（Lemma 15.2）

在 哈夫曼编码 中，证明”频率最低的两个字符 $x,y$ 在最优前缀码中是最深层的兄弟”：

1. 设 $T$ 是一棵最优前缀码树，$a,b$ 是 $T$ 中深度最大的兄弟叶节点
2. 因为 $x,y$ 频率最低，所以 $f[x]\le f[a]$ 且 $f[y]\le f[b]$
3. 交换 $x$ 和 $a$：代价变化为 $(f[x]-f[a])\cdot (d_T(a)-d_T(x))$
   • $f[x]\le f[a]$（频率更低的字符）
   • $d_T(a)\ge d_T(x)$（$a$ 在最深层）
   • 因此代价变化 $\le 0$，替换后代价不增
4. 同理交换 $y$ 和 $b$，代价不增
5. 最终 $x,y$ 成为最深层兄弟，且树仍然最优

关键洞察：替换后编码代价不增，因此仍然是最优的。

4. 应用三：离线缓存（Theorem 15.5）

在 离线缓存 中，证明 furthest-in-future 策略的最优性：

1. 设 FF 和 OPT 是两个策略，通过归纳保持四个不变性质
2. 在每一步，若 FF 发生未命中而 OPT 命中：
   • FF 驱逐的项 $e$ 在 OPT 的缓存中（或不在，分情况讨论）
   • 通过替换 OPT 的驱逐选择为 FF 的驱逐选择，证明性质保持
3. 关键步骤：将 OPT 缓存中的一项替换为 FF 刚加载的项，利用”FF 驱逐的是最远将来使用的项”这一事实，证明替换后不会增加后续的未命中次数

关键洞察：替换后 OPT 的未来未命中次数不增，因此累计未命中数仍然不超过 FF。

5. 替换论证的适用条件

替换论证成功的关键条件：

• 贪心选择与最优解的选择之间存在可比较的”优劣”关系
• 替换操作不会影响后续子问题的可行性
• 替换后解的目标函数值不会变差

当这些条件不满足时，贪心算法可能不正确。例如，0-1背包问题中，选择单位价值最高的物品后，剩余的背包容量可能导致无法装入其他高价值物品——替换后无法保证可行性。

章节扩展

• 15.1 活动选择问题 — 替换论证的典型应用
• 15.3 哈夫曼编码 — 替换论证的另一个应用
• 15.4 离线缓存 — 替换论证的第三个应用
• 贪心选择性质 — 替换论证所证明的核心性质

参见

• 最优子结构 — 动态规划中的对应证明技术（剪切-粘贴法）
• 贪心算法 — 贪心算法完整方法论
• 活动选择问题 — 替换论证的应用一
• 哈夫曼编码 — 替换论证的应用二
• 离线缓存 — 替换论证的应用三