贪心算法一定能得到最优解的证明【活动安排问题举例】

贪心算法一定能得到最优解的证明

按照老师说法是 分为三步：

1. 证明总存在一个以贪心选择开始的最优解。
2. 此问题具有最优子结构的性质。
3. 用数学归纳法，总结得到结论。

以活动安排为例，首先，我们按照按照活动结束时间非递增排序,即从小到大得到一个序列 E{1、2、…、n)，我们可以知道1这个活动是一定会被选到的，因为他的结束时间最早，我们可以有更多的时间去观看其他比赛。

假设具有一个最优解A,且A中的活动安排也是按照活动的结束时间非递增排序，即从小到大排序的，且他的第一个活动为K,这时候我们就需要重点比较K和1的关系了；
如果K = 1：我们就可以知道A就是满足以贪心选择开始的一个最优解，所以证明的结束了；这个就满足了第一个要求；
如果K != 1：我们就需要设一个解为B，这个B不包含A中的K这个活动，但是他包含A中的其他活动，且他的第一个第一个活动为E中的1，我们可以想象，这个是求解最多能够观看多少场比赛的问题，所以，由E的排序可知，活动1的结束时间比活动K的结束时间还要早，所以我们可以知道B也是一个最优解，且是一个由贪心选择开始的最优解，因为他们能观看的比赛场次都是相同的，都达到了最大值。得证第一个要求；

二、最优子结构的问题

在做了第一步贪心选择活动1之后，原问题简化为了，对E中所有与活动1相容的活动进行安排的子问题，用通俗的话说，就是现在1已经确定了，然后我们就需要对剩下的活动进行安排，但是这些安排有一个前提，就是他们的开始时间，大于等于1的结束时间。
所以，若A是原问题的最优解，则设A’＝A-{1} 是接下来的子问题的最优解，也就是活动开始时间＞1活动的结束时间的剩余的活动，设为E’，的最优解， 这时候我们可以用反证法，假设E’有一个解B’，B’比A’包含更多的活动，则B＝B’＋{1}，则容易知道B比最优解A还要包含更多的活动，与A的最优性矛盾，所以不存在这样一个B’，也就是得到
结论:每一次所做的贪心选择都将原问题简化为与原问题具有相同形式的子问题，得证，活动安排问题，具有最优子结构的性质。

三、用数学归纳法

通过数学归纳法可知，贪心选择算法最终产生原问题的最优解

PS:个人理解，且具体问题还需要具体分析。