贪心选择性质

概述

贪心选择性质是指可以通过做出局部最优（贪心）选择来产生全局最优解的性质。这是贪心算法独有的核心性质，与最优子结构（动态规划和贪心算法共享）共同构成了贪心算法正确性的基础。验证贪心选择性质通常需要使用替换论证技术。

定义

贪心选择性质（Greedy-Choice Property）

一个最优化问题具有贪心选择性质，如果存在一个贪心策略，使得：

1. 做出局部最优选择后
2. 只剩下一个子问题需要求解
3. 该选择与子问题的最优解组合在一起，构成原问题的全局最优解

形式化地，设 $G$ 为贪心选择，$S$ 为最优解。若存在一个最优解 $S^{\ast }$ 包含贪心选择 $G$，则问题具有贪心选择性质。

核心性质

1. 与最优子结构的区别

贪心选择性质和最优子结构是两个不同的性质：

• 最优子结构：最优解包含子问题的最优解（动态规划和贪心算法共享）
• 贪心选择性质：可以通过局部最优选择来达到全局最优（贪心算法独有）

一个问题可能具有最优子结构但不具有贪心选择性质。例如，0-1背包问题具有最优子结构，但不具有贪心选择性质（不能通过贪心选择得到全局最优解）。

2. 活动选择问题中的贪心选择性质（Theorem 15.1）

在 活动选择问题 中，贪心策略是”选择最早结束的活动”。

Theorem 15.1：考虑任意非空活动子集 $S_k=\{a_i\in S:s_i\ge f_k\}$（即与活动 $a_k$ 兼容的所有活动），设 $a_m$ 是 $S_k$ 中结束时间最早的活动，则 $a_m$ 包含在 $S_k$ 的某个最大兼容子集中。

证明（替换论证）：

1. 设 $A$ 是 $S_k$ 的一个最大兼容子集，$a_j$ 是 $A$ 中结束时间最早的活动
2. 因为 $a_m$ 是 $S_k$ 中结束时间最早的活动，所以 $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\}$ 也是最大兼容子集
6. 故 $a_m$ 包含在某个最大兼容子集中

3. Huffman编码中的贪心选择性质（Lemma 15.2）

在 哈夫曼编码 中，贪心策略是”合并频率最低的两个字符”。

Lemma 15.2：设 $C$ 为字母表，$C$ 中每个字符 $c$ 的频率为 $f[c]$。设 $x$ 和 $y$ 是 $C$ 中频率最低的两个字符，则存在 $C$ 的一个最优前缀码，其中 $x$ 和 $y$ 的编码长度相同，且仅在最末一位不同。

证明（替换论证）：

1. 设 $T$ 是一棵最优前缀码树，$a$ 和 $b$ 是 $T$ 中深度最大的两个叶节点（兄弟关系）
2. 不失一般性，设 $f[x]\le f[y]$ 且 $f[a]\le f[b]$
3. 因为 $x$ 和 $y$ 是频率最低的两个字符，所以 $f[x]\le f[a]$ 且 $f[y]\le f[b]$
4. 交换 $x$ 和 $a$ 的位置：代价变化为 $(f[x]-f[a])(d_T(a)-d_T(x))\le 0$（因为 $f[x]\le f[a]$ 且 $d_T(a)\ge d_T(x)$）
5. 同理交换 $y$ 和 $b$ 的位置，代价不增
6. 因此，将 $x$ 和 $y$ 放在最深层作为兄弟节点，仍然是最优的

4. 贪心选择性质 vs. 最优子结构

特征	贪心选择性质	最优子结构
所属算法	仅贪心算法	贪心 + 动态规划
含义	局部选择可以导向全局最优	最优解包含子问题的最优解
验证方法	替换论证	反证法（剪切-粘贴）
子问题数量	通常只有1个	可能有多个

5. 贪心选择性质不成立的经典例子

• 0-1背包问题：选择单位价值最高的物品不保证全局最优
• 旅行商问题（TSP）：选择最短的边不保证全局最优
• 最短路径 vs. 最长路径：最短路径具有贪心选择性质（Dijkstra算法），但最长路径不具有

章节扩展

• 15.1 活动选择问题 — 贪心选择性质的典型应用
• 15.2 贪心策略要素 — 贪心算法设计要素的系统总结
• 15.3 哈夫曼编码 — 另一个贪心选择性质的应用
• 替换论证 — 证明贪心选择性质的核心技术

参见

• 最优子结构 — 与贪心选择性质共同构成贪心正确性基础
• 贪心算法 — 贪心算法完整方法论
• 动态规划 — 与贪心算法的对比
• 离线缓存 — 贪心选择性质的另一个应用