贪心算法：活动选择问题以及贪心选择性质证明

贪心算法：活动选择问题以及贪心选择性质证明

引用

CSDN

1.

https://blog.csdn.net/weixin_50917576/article/details/135415206

什么时候使用贪心算法？

贪心选择特性

全局的最优解可以通过局部的最优（贪心）选择得到。

动态规划与贪心算法对比

• 动态规划：需要检查子问题的解。
• 最优子结构：问题的最优解包含了其子问题的最优解。例如，如果A是S的最优解，那么A' = A - {1}也是最优解。
• 贪心算法：并不总是能得到最优解。

贪心算法与动态规划的对比

• 相同点：最优子结构
• 不同点：贪心选择特性
• 如果贪心算法不是最优的：可以使用动态规划。

活动选择问题

给定一个集合 S = {1, 2, …, n}包含n个计划的活动，对每个活动，有开始时间$s_i$和结束时间$f_i$，选择出相互兼容的活动最大集合。

• 如果活动i被选中，它将在半开放的区间$[s_i, f_i)$中进行。
• 活动i和j兼容，当且仅当它们的时间区间不重叠。

问题分析

基本思想

对应伪代码

贪心选择性质证明

设E为问题所给的活动集合，且E中的活动是按照活动结束时间增序排列的，明显，活动$a_1$为最早结束的活动。
设A是问题的一个最优解，明显有A是E的一个子集。这里设A的第一个活动为k。

1. 若$k = 1$，即A的第一个活动就是最早结束的，故A是以贪心选择开始的最优解。
2. 若$k \neq 1$，设集合$B = (A - {a_k}) \cup {a_1}$，即用活动$a_1$替换掉活动$a_k$。
   又因为$a_1$的结束时间小于$a_k$，故$a_1$比$a_k$提前结束。另外由于A中的活动是相容的，故B中的活动也相容。
   又因为A中的活动个数和B中的活动个数相同，故B也是最优解(需要注意的是最优解一般不唯一)。
   所以B是一个以贪心选择活动$a_1$为开始后的最优活动。
   故最优解可以取最早结束的活动。(算法导论黑书证明到这里就结束了)

之后假设第k步成立，即按照算法选了$a_1, a_2, ..., a_k$，现在我们只要证明选$a_{k+1}$也是最优解的一部分即可。这是需要注意的是，对$a_{k+1}$需要满足相同性，且是选结束时间尽可能早的任务。
利用数学归纳法

1. A包含了算法选择的前k项活动，假设存在活动选择的最优解的即$A \cup B$，如下图所示。
   这里将未被选择的活动分为S1和S2两个部分。
   值得注意的是，B一定来自于S1，因为S2的所有活动都与A冲突，为了满足相容性，不能被选到。
   假设B不是S1的最优解，即S1存在有最优解B'的活动数多于B；
   那么第k步的最优解就变为$A \cup B'$，显然与开始$A \cup B$为最优解的假设是矛盾的，因此不成立。
2. 证明选结束时间最早的活动，也是最优解。
   在S1中，必定存在一个结束时间最早的活动，即$a_{k+1}$
   在A的第一个活动为k时的证明可知，算法的第一步的最优解包含结束时间最早的活动。
   因此S1存在最优解B包含了活动$a_{k+1}$。B和B都是S1的最优解。因此两者包含的活动个数相同。
   用B代替B，即$A \cup B$的活动与$A \cup B$的活动个数相同，因此最优解的性质不变。
   而B包含了$a_{k+1}$，故证明了$A \cup B$是最优的，所以根据数学归纳法，假设算法的前k项活动是最优的，选第k+1项也是最优解，命题得证。

教材习题

问题

16.1-2 假设我们不再一直选择最早结束的活动，而是选择最晚开始的活动，前提仍然是与之前选出的所有活动均兼容。描述如何利用这一方法设计贪心算法，并证明算法会产生最优解。

贪心选择性质证明

设E为问题所给的活动集合，且E中的活动是按照活动开始时间降序排列的，明显，活动$a_n$为最晚开始的活动。
设A是问题的一个最优解，明显有A是E的一个子集。这里设A的最后一个活动为k。

1. 若$k = n$，即A的最后一个活动就是最晚开始的，故A是以贪心选择开始的最优解，问题得证。
2. 若$k \neq n$，设集合$B = (A - {a_k}) \cup {a_n}$，即用活动$a_n$替换掉最后一个活动$a_k$。
   又因为$a_n$的开始时间大于$a_k$，故$a_n$比$a_k$晚开始。另外由于A中的活动是相容的，故B中的活动也相容。
   又因为A中的活动个数和B中的活动个数相同，故B也是最优解(需要注意的是最优解一般不唯一)。
   所以B是一个以贪心选择活动$a_n$为结束的最优活动。