贪心算法证明

贪心性质

用贪心算法解决的题目需要满足以下性质：

• 最优子结构：一个问题的最优解包含其子问题的最优解。
• 贪心选择性：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

对比动态规划

DP满足

• 最优子结构：一个问题的最优解包含其子问题的最优解。
• 重叠子问题：在问题的求解过程中，很多子问题的解将被多次使用。

贪心算法设计

1. 设计贪心选择方法：
   • 贪心选择方法
   • 剩余子问题
2. 证明：对于 1 中贪心选择来说 所求解的问题具有最优子结构
3. 证明：对于 1 中贪心选择算法来说 所求解的问题具有贪心选择性
   • 归纳法：证明在每一步做得都比其它算法好 从而最终产生了一个最优解
   • 交换论证法：在保证最优性不变前提下 从一个最优解逐步替换 最终得到贪心算法的解
4. 按照 1 中设计的贪心选择方法设计算法

例子

例 Maximum Cardinality Disjoint Interval Problem

问题描述：给一些时间片段集合T={（a1，b1）（a2，b2），。。。，（an，bn）}，找出一个元素个数最多的子集S，子集中的每个元素的时间片段没有交叉。

Greedy Algorithm: 每次都选所有interval 中bi最小的那个，把（ai，bi）加入S，然后把（ai，bi）在T中删除，同时把T中所有和（ai，bi）有交叉的interval删除，然后再在T中找最小的bj，循环上面的操作，直到没有可以在添加的。

证明上面说的Greedy Algorithm是最优的。

下面就用第一个证明的步骤来证。

我们的Greedy Algorithm记为A，假设A不是最优的，那么就一定存在一个O，O是和A最相近的一个最优的算法，最相近是指和O和A的前K-1个选择都相同，第K个是不同的。

假设对于A，A第k个选择的是（ai，bi）；而O第K个选择的是（aj，bj）。从A的定义我们可以直到，bi<=bj。

现在我们构造一个O'，O' = O-（aj，bj）+（ai，bi）。

1）很显然，O'是这个问题的一个解，也就是说O'中的intervals没有重叠的。

在O'中，（ai，bi）前的intervals和A中的一样，所以前一部分没有重叠。在（ai，bi）后的intervals和O中的一样，所以也没有重叠，同时bi<=bj，所以（ai，bi）也不会和它相邻的重叠，所以O'中的所有intervals都没有重叠。

2）O'是一个最优解，因为他的intervals的个数和O一样。

综上，我们找到了一个最优解O'，它和A具有的共同的intervals有K个，这和我们前提假设最多有k-1个相矛盾，所以，A是最优的。证毕。