算法导论——贪心算法
求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择。对于许多最优化问题，使用动态规划算法来求最优解有些杀鸡用牛刀了，可以使用更简单、更高效的算法。贪心算法(greedy algorithm)就是这样的算法，它在每一步都做出当时看起来最佳的选择。也就是说，它总是做出局部最优的选择，寄希望这样的选择能导致全局最优解。本章介绍一些贪心算法能找到最优解的最优化问题。
贪心算法并不保证得到最优解，但对很多问题确实可以求得最优解。我们首先在16.1节介绍一个简单但非平凡的问题—活动选择问题，这是一个可以用贪心算法求得最优解的问题。首先考虑用动态规划方法解决这个问题，然后证明一直做出贪心选择就可以得到最优解，从而得到一个贪心算法。16. 2节会回顾贪心方法的基本要素，并给出一个直接的方法，可用来证明贪心算法的正确性。 16. 3节提出贪心技术的一个重要应用:设计数据压缩编码(Huffman编码)。在16. 4节中，我们讨论一种称为“拟阵\的组合结构的理论基础，贪心算法总是能获得这种结构的最优解。最后，16. 5节将拟阵应用于单位时间任务调度问题，每个任务均有截止时间和超时惩罚。
贪心方法是一种强有力的算法设计方法，可以很好地解决很多问题。在后面的章节中，我们会提出很多利用贪心策略设计的算法，包括最小生成树(minimum-spanning-tree)算法(第23章)、单源最短路径的djikstra算法(第24章)，以及集合覆盖问题的Chvatal贪心启发式算法(第35章)。最小生成树算法提供了一个经典的贪心方法的例子。
16.1 贪心选择
假如我们无需求解所有子问题就可以选择出一个活动加人到最优解，将会怎样?这将使我们省去递归式(16. 2)中固有的考查所有选择的过程。实际上，对于活动选择问题，我们只需考虑一个选择:贪心选择。
对于活动选择问题，什么是贪心选择?直观上，我们应该选择这样一个活动，选出它后剩下的资源应能被尽量多的其他任务所用。现在考虑可选的活动，其中必然有一个最先结束。因此，直觉告诉我们，应该选择S中最早结束的活动，因为它剩下的资源可供它之后尽量多的活动使用。(如果S中最早结束的活动有多个，我们可以选择其中任意一个)。换句话说，由于活动已按结束时间单调递增的顺序排序，贪心选择就是活动a,。选择最早结束的活动并不是本问题唯一的贪心选择方法，练习16. 1-3要求设计其他贪心选择方法。
当做出贪心选择后，只剩下一个子问题需要我们求解:寻找在a,结束后开始的活动。为什么不需要考虑在a1开始前结束的活动呢?因为s1 而且，我们已经证明活动选择问题具有最优子结构性质。令 Sk??ai?s:si?fk?为在ak结束后开始的任务集合。当我们做出贪心选择，选择 了a1后，剩下的S1是唯一需要求解的子问题。最优子结构性质告诉我们，如果a1在最优解中，那么原问题的最优解由活动a1及子问题S1中所有活动组成。 现在还剩下一个大问题:我们的直觉是正确的吗?贪心选择——最早结束的活动——总是最优解的一部分吗?下面的定理证明了这一点。 定理16. 1考虑任意非空子问题Sk，令am是Sk中结束时间最早的活动则a。在S*的某个最大兼容活动子集中。 证明 令Ak是Sk的一个最大兼容活动子集，且aj是Ak中结束时间最早的活动。若aj=am，则已经证明am在Sk的某个最大兼容活动子集中。若aj不等于am，令集合Ak'?Ak??aj???am?,即将Ak中的aj替换为am.Ak’中的活动都是不相交的，因为Ak中的活动都是不相交的，aj是Ak中结束时间最早的活动,而fm小于等于fj。由于Ak'?AK，因此得出结论Ak’也是Sk的一个最大兼容活动子集，且它包含am. 因此，我们看到虽然可以用动态规划方法求解活动选择问题，但并不需要这样做(此外，我们并未检查活动选择问题是否具有重叠子问题性质)。相反，我们可以反复选择最早结束的活动，保留与此活动兼容的活动，重复这一过程，直至不再有剩余活动。而且，因为我们总是选择最早结束的活动，所以选择的活动的结束时间必然是严格递增的。我们只需按结束时间的单调递增顺序处理所有活动，每个活动只考查一次。 求解活动选择问题的算法不必像基于表格的动态规划算法那样自底向上进行计算。相反，可以自顶向下进行计算，选择一个活动放人最优解，然后，对剩余的子问题(包含与已选择的活动兼容的活动)进行求解。贪心算法通常都是这种自顶向下的设计:做出一个选择，然后求解剩下的那个子问题，而不是自底向上地求解出很多子问题，然后再做出选择。 递归贪心算法 我们已经看到如何绕过动态规划方法而使用自顶向下的贪心算法来求解活动选择问题，现在我们可以设计一个直接的递归过程来实现贪心算法。过程RECURSIVE-ACTIVITY-SELECTOR的输人为两个数组s和f，表示活动的开始和结束时间，下标k指出要求解的子问题Sk，以及问题规模n。它返回凡的一个最大兼容活动集。我们假定输人的n个活动已经按结束时间的单调递增顺序排列好(公式(16. 1))。如果未排好序，我们可以在O(n Ign)时间内对它们进行排序，结束时间相同的活动可以任意排列。为了方便算法初始化，我们添加一个虚拟活动a0，其结束时间f0 =0，这样子问题So就是完整的活动集S。求解原问题即可调用RECURSIVE-ACTIVITY SELECTOR(s, f, 0, n)。 图16-1.显示了算法的执行过程。在一次递归调用RECURSIVE-ACTIVITY-SELECTOR ( s,f, k, n)的过程中，第2^}3行while循环查找Sk中最早结束的活动。循环检查ak+1,ak+2,...,an,直至找到第一个与ak兼容的活动am，此活动满足sm>=fk。如果循环因为查找成功而结束，第5行返回{am}与RECURSIVE-ACTIVITY SELECTOR Sk??，因此第6行返回?. 假定活动已经按结束时间排好序，则递归调用RECURSIVE-ACTIVITY-SELECTOR(s, f,0, n)的运行时间为O(n)，我们稍后证明这个结论。在整个递归调用过程中，每个活动被且只被第2行的while循环检查一次。特别地，活动ai在k 迭代贪心算法 我们可以很容易地将算法转换为迭代形式。过程RECURSIVE-ACTIVITY SELECTOR几乎就是“尾递归”:它以一个对自身的递归调用再接一次并集操作结尾。将一个尾递归过程改为迭代形式通常是很直接的，实际上，某些特定语言的编译器可以自动完成这一工作。如前所述，RECURSIVE ACTIVITY-SELECTOR用来求解子问题凡，即由最后完成的任务组成的子问题。 过程GREEDY-ACTIVITY-SELECTOR是过程RECURSIVE ACTIVITY-SELECTOR的一 个迭代版本。它也假定输人活动已按结束时间单调递增顺序排好序。它将选出的 活动存人集合A中，并将A返回调用者。 过程执行如下。变量k记录了最近加人集合A的活动的下标，它对应递归算法中的活动 ak。由于我们按结束时间的单调递增顺序处理活动，人总是A中活动的最大结束时间。也就 是说， (16.3) 第2~3行选择活动a1，将A的初值设置为只包含此活动，并将k的初值设为此活动的下标。第4~7行的for循环查找凡中最早结束的活动。循环依次处理每个活动am，am若与之前选出的活动兼容，则将其加人A，这样选出的am必然是S。中最早结束的活动。为了检查活动am是否与A中所有活动都兼容，过程检查公式(16.3)是否成立，即检查活动的开始时间sm是否不早于最近加人到A中的活动的结束时间fk。如果活动am是兼容的，第6~7行将其加人A中，并将k设置为m.GREEDY-ACTIVITY-SELECTOR(s,f)返回的集合A与RECURSIVE ACTIVITY SELECTOR(s,f,0,n)返回的集合完全相同。 与递归版本类似，在输人活动已按结束时间排序的前提下，GREEDY-ACTIVITY-SELECTOR的运行时间为O(n). 16. 2贪心算法原理 贪心算法通过做出一系列选择来求出问题的最优解。在每个决策点，它做出在当时看来最佳的选择。这种启发式策略并不保证总能找到最优解，但对有些问题确实有效，如活动选择问题。本节讨论贪心方法的一些一般性质。 16. l节中设计贪心算法的过程比通常的过程繁琐一些，我们当时经过了如下几个步骤: 1.确定问题的最优子结构。 2.设计一个递归算法(对活动选择问题，我们给出了递归式(16. 2)，但跳过了基于此递归式设计递归算法的步骤)。 3.证明如果我们做出一个贪心选择，则只剩下一个子问题。 4.证明贪心选择总是安全的(步骤3, 4的顺序可以调换)。