【算法分析与设计】第8篇：贪心策略的理论基础与拟阵模型

在动态规划中我们在每一步都要综合考量多个子问题的结果才能做出决策。贪心算法则截然相反每一步只取当前看起来最好的那个选项做完决定就不再回头。这种“活在当下”的策略听起来过于草率但在相当广泛的一类问题中它竟然能导出全局最优解。这是为什么理论上的答案藏在拟阵这个优美的代数结构之中。一、贪心策略成立的两个条件讨论贪心算法时我们仍然会提到最优子结构但它的含义与动态规划中略有不同。在贪心语境下最优子结构指的是做出一个贪心选择后剩余的子问题与原问题具有相同的形式且子问题的最优解与贪心选择合并即可得到原问题的最优解。但真正使贪心区别于动态规划的是另一个更强的条件——贪心选择性质全局最优解可以通过一系列局部最优选择得到。换言之存在至少一个全局最优解它包含贪心算法在第一步所选的元素。证明贪心选择性质的通用策略是“交换论证法”假设存在一个不包含贪心选择的最优解通过将其中某个元素替换为贪心选择可以构造出一个不差于原最优解的新解且新解包含贪心选择。一次应用后问题规模缩减归纳即得全部。需要特别强调的是与动态规划不同贪心算法并不需要所有子问题都是最优的——它只需要证明那个被贪心选择覆盖的子问题存在最优解。二、拟阵贪心正确性的代数根基许多贪心算法的正确性可以统一地归结到拟阵结构上。拟阵的定义源自线性代数中“线性无关”概念的抽象化由Whitney于1935年引入。一个拟阵M(S,I)M(S,I) 由一个有限非空集合 SS 和 SS 的一族子集 I⊆2SI⊆2S 构成II 中的元素称为独立集。拟阵必须满足三条公理空集独立性∅∈I∅∈I。遗传性若 A∈IA∈I 且 B⊆AB⊆A则 B∈IB∈I。即独立集的任意子集仍是独立集。交换性若 A,B∈IA,B∈I 且 ∣A∣∣B∣∣A∣∣B∣则存在 x∈B∖Ax∈B∖A 使得 A∪{x}∈IA∪{x}∈I。这是拟阵最核心的性质它保证了从较小的独立集可以“扩充”到较大的独立集。对于带权拟阵给定权重函数 w:S→Rw:S→R我们希望找出总权重最大的独立集。针对此问题的贪心算法极为简洁将 SS 中元素按权重降序排列依次检查每个元素若加入后仍保持独立性则选取。这个算法的正确性由以下定理保证定理对于任意带权拟阵上述贪心算法得到最大权独立集。证明思路概述设贪心算法输出 G{g1,g2,…,gk}G{g1​,g2​,…,gk​}按选取顺序设任一最优解 O{o1,o2,…,om}O{o1​,o2​,…,om​} 也按权重降序排列。利用交换性可证明 ∣G∣∣O∣∣G∣∣O∣且对任意 iiw(gi)≥w(oi)w(gi​)≥w(oi​)因此 GG 同为最优解。详细推导涉及多步构造但核心均依赖交换性公理。拟阵的优美之处在于它将众多看似不相关的问题纳入统一框架。图论中的最小生成树问题对应图拟阵SS 为边集独立集为不含环的边集若干任务在截止时间前调度的最大收益问题对应单位时间调度拟阵。它们之所以能用贪心求解根本原因就在于其可行解空间满足上述三条公理。三、实例展开Huffman编码Huffman编码是最优前缀码的构造算法它在信息论与数据压缩中具有基础地位。给定字符集 CC 及每个字符 cc 的出现频率 f(c)f(c)目标是构造一棵二叉树将字符放在叶节点上使得 ∑c∈Cf(c)⋅dT(c)∑c∈C​f(c)⋅dT​(c) 最小其中 dT(c)dT​(c) 表示字符 cc 在树中的深度编码长度。贪心策略反复合并当前频率最低的两个节点将它们作为一个新节点的左右孩子新节点的频率为两者之和并将其放回候选集合。直到只剩一个节点即为Huffman树的根。正确性证明贪心选择性质设 xx 和 yy 是当前频率最低的两个字符。需证明存在一棵最优前缀树使 xx 与 yy 成为深度最大的兄弟叶节点。用交换论证法取任意最优树 TT设深度最大的两个兄弟叶节点为 aa 与 bb。由于 f(x)≤f(a)f(x)≤f(a) 且 f(y)≤f(b)f(y)≤f(b)交换 xx 与 aa、yy 与 bb 不会增加总代价且新树仍为最优。由此可知存在最优树以 xx 和 yy 为兄弟叶节点。最优子结构合并 xx 与 yy 得到新字符 zz 且 f(z)f(x)f(y)f(z)f(x)f(y) 后原问题归约为在字符集 (C∖{x,y})∪{z}(C∖{x,y})∪{z} 上构造最优前缀树。子问题的最优树加上将 zz 展开为 xx 与 yy 的操作即得原问题最优树。Huffman编码虽然没有直接用拟阵表述其结构为独立系统但非拟阵但它的证明逻辑与拟阵上的贪心分析完全同构先证贪心选择存在于某个最优解再证贪心选择后子问题保持同构归纳即得全局最优。四、贪心、拟阵与动态规划的分野何时应该采用贪心策略一个实用的判据是若问题结构能被证明为拟阵则贪心必然正确若不具备拟阵结构但贪心选择性质成立仍需独立证明若两者均不成立则必须诉诸动态规划或搜索。拟阵理论的价值不在于覆盖所有贪心问题而在于为贪心正确性提供了可形式化验证的充分条件。下一篇我们将目光投向算法分析中一个独特的技术——平摊分析。它不直接设计算法而是提供了一种更精细的成本核算方式让我们得以揭示某些操作序列中“单价”与“均摊价”的本质差异。