贪心算法（GREEDY ALGORITHM）证明实践

基础概念

贪心算法

Formal的解释这里就不介绍了，有兴趣的直接去wikipedia上理解。简单地来说，贪心算法就是在某种规律下不断选取局部最优解，从而达到全局最优。《挑战程序设计竞赛》中有一个很直观的解释：一直向前！

证明方法

既然贪心算法是利用规律选取局部最优解，那么我们选取规律所得出的全局解就不一定是全局最优解。因此，我们需要证明，我们所选这个规律是可以得出一个全局最优解的。注意这里所谓的可以得出最优解的规律，或者说策略，是可以有多种的。

此处讨论的证明方法指的是基本证明方法，针对贪心算法的具体版本将在实例分析部分给出。在数学上常用的证明方式主要是两种：Contradiction和Induction，[1]，下面通过具体实例来介绍这两种方法。

Induction

证明 n!<=nn

看似简单的一个证明，可能高中毕业的时候大家都会，上完大学，有小部分人就忘记了。所以如果没有问题的同学可以直接跳过这一部分。

步骤1，如果我们决定用Induction Method去证明一个命题，那么通常会先带入数字去试验：

1<=11 2<=22 3<=33 如果带入简单的几个数字命题都无法成立，那么这个命题显然是假命题了，否则接下来是步骤2。

步骤2，首先证明base case成立，即：

1!<=11 步骤3，假设对于 n=k(k>=n0) 时命题成立，然后证明 n=k+1 时命题也成立：

k!(k+1)<=(k+1)k(k+1) 由于 k!<=kk ， kk<(k+1)k ，因此 (k+1)!<=(k+1)(k+1) 成立，从而命题成立。

Contradiction

Contradiction method有时可以将看似困难的命题证明转化为简单的逻辑问题，在《The Art of Multiprocessor Programming》中有很多并发正确性命题，都是通过反证法来证明的。
假设我们需要证明的命题为：

质数是无限的

步骤1，提出这个命题的逆命题，即素数是有限的。

步骤2，假设这个逆命题是正确的，我们假设最大的素数为 k ，必然存在自然数 n ， n=2∗3∗5∗...∗k (分解质因数)。设 n′=n+1 ，那么对于 n′ 分解质因数，其质因数中必然不存在小于等于 k 的数（n+1与n的最大公约数为1）。此时有两种可能：

1. n′ 可能被大于 k 的质因数所分解。如我们假设最大的质因数为2，但是15 = 3 * 5，3和5为更大的质因数。
2. n′ 本身就是质数，即 n′=1∗n′ 。

显然与逆命题存在矛盾。

步骤3，逆命题为假命题，所以该命题为真命题。

实例分析

POJ 3190

此题大意为有 N 头牛，在一些畜栏中吃草，每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏，给定 N 头牛和每头牛开始吃草和结束吃草的时间，求使用最小畜栏数目和每头牛对应的畜栏。

贪心策略

对于这个题目，已知有两种贪心策略是正确的。

1. 将 N 头牛按照开始时间 t(i) 排序，每次选取牛集合 S 中的开始时间最早，并且与结束时间 f(i) 不冲突的元素，找到之后从集合 S 中删除或者标记元素。当找不到满足开始时间大于结束时间这一条件的元素时，重新从 S 中选取元素，直到 S 为空。
2. 将 N 头牛按照开始时间 t(i) 排序，首先将第一头牛存入集合 T 中，如果接下来的牛满足开始时间大于 T 中最早结束时间，那么取出这个元素，并更新其时间结束时间为当前牛的结束时间，然后重新存入集合中。否则直接将该当前牛存入集合中。

贪心算法证明

贪心算法的证明主要是两种思路。

第一种方法被称为staying ahead[2]，即保持领先，意义为如果我们运用某个策略，在算法的每一步中都使某个条件保持领先，那么最后可以利用这个领先条件来证明最优解。这种方法本质上结合了上面介绍的Induction和Contradiction方法。

接下来我们将这个方法应用到POJ 3190算法2的证明中。

1. 首先，我们需要确定一个领先条件，我们设这个领先条件为：在算法的每一步中，都选取最小开始时间的畜栏放入下一头牛。即 w(i)<=o(i) ， w 代表当前策略， o 代表最优策略，对于贪心算法的证明，基本假设是当前贪心策略至少和最优策略保证相同的效果。
2. 证明这个条件在算法的每一步中都成立。运用Induction method，首先证明base case的情况，我们首先从开始时间0开始存入牛，所以显然成立。接下来，证明前k头牛时成立，k+1时也成立。两种情况，第k+1头牛的开始时间 t(k+1) 小于集合 T 中的最小结束时间，那么直接存入集合，这个时候要么最小时间更新为第 k 头牛的结束时间，要么保持原来的结束时间。否则，如果第k+1头牛的开始时间 t(k+1) 大于集合 T 中的最小结束时间，更新集合 T 最小结束时间元素信息。因此接下来仍然可以直接选取最小结束时间的畜栏。
3. 接下来我们运用Contradiction method来证明我们的策略可以得到畜栏数最少的解决方案。由于我们已经证明每一步必定可选最小开始时间的畜栏，所以如果上述策略不成立，最优解 o 中一定存在某一畜栏，其中所有牛都可以被放入其他畜栏。那么，这些牛同样可以被放入到贪心策略解的畜栏中（因为我们证明了每一步选取的最小开始时间至少和最优解一致）。然而，在放入某一头牛的时候，如果其开始时间大于最小结束时间，那么一定已经被放入到之前的畜栏中去了，所以判定这些牛一定不能放入到原有的畜栏中去。
4. 至此，证明结束。算法2可以得到最优解。

第二种方法被称为exchange arguments[2]，即将最优解元素和当前贪心策略解元素逐个交换，交换的情况很多种[3]，可以是 o 中存在的元素， w 中不存在，也可以是顺序不同，如果不影响最优解效果，那么贪心策略成立。在我们的题目中，交换条件可以是放的畜栏不同。我们已知算法2是最优解，来证明算法1也是最优解。

交换 o 与 w 中的元素， o ， w 中如果存在放入的畜栏不同，只有一种情况：

c1 -------------|t1

c2 -------|t2

如果当前牛的开始时间 <t1 ，算法1将不会处理这个元素，而是在第二轮中将这个元素放入到 c2 中，而算法2直接将当前元素放入 c2 ，这种情况下两种算法结果相同。

如果当前牛的开始时间 >t1 ，算法1将元素放入 c1 ，然而算法2会将元素放入 c2 。但是这样的处理不会影响最优解，算法将元素放入到 c2 后， c2 也就一定只能存入开始时间在 t3 之后的元素，其他开始时间在 t3 之前的元素将会被放入 c1 。

c1 -------------|t1

c2 -------|t2      ------------|t3

而对于算法1而言：

c1 -------------|t1-----------|t3

c2 -------|t2

其他开始时间在 t3 之前的元素将会被放入 c2 ，并且这些元素的开始时间一定 >t1 ，所以放入 c1 和放入 c1 对算法最终的效果没有影响。因此，贪心策略成立

时间复杂度分析

下面简单分析一下这个题目的三种解法：

• 算法1解法1将元素放入set中，每次更新时，查找set，并且从中删除元素。放入元素复杂度， log(1)+log(2)...+log(n)=log(n!) 。遍历复杂度，我们假设最坏情况，每次遍历删除一个元素： 2log(n!)
• 算法1解法2元素存入数组中，每次遍历数组，标志已经删除的元素。排序： nlog(n) 。遍历，同样是最坏情况，每次前进一个元素（二分查找）： log(n)+log(n−1)+log(1)=log(n!)
• 算法2解法1维护一个最小堆，每次更新最小堆。排序： nlog(n) 。最小堆维护，最坏情况，每次都无法更新最小堆： log(n)+log(n−1)+log(1)=log(n!)

引用

[1].  http:///
[2].  /~mlh/algkon/
[3].  /courses/cs482/2007su/