贪心算法证明
贪心算法证明
贪心性质
用贪心算法解决的题目需要满足以下性质：
- 最优子结构：一个问题的最优解包含其子问题的最优解。
- 贪心选择性：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
对比动态规划
DP满足
- 最优子结构：一个问题的最优解包含其子问题的最优解。
- 重叠子问题：在问题的求解过程中，很多子问题的解将被多次使用。
贪心算法设计
- 设计贪心选择方法：
- 贪心选择方法
- 剩余子问题
- 证明：对于 1 中贪心选择来说 所求解的问题具有最优子结构
- 证明：对于 1 中贪心选择算法来说 所求解的问题具有贪心选择性
- 归纳法：证明在每一步做得都比其它算法好 从而最终产生了一个最优解
- 交换论证法：在保证最优性不变前提下 从一个最优解逐步替换 最终得到贪心算法的解
- 按照 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是最优的。证毕。
