贪心算法(Greedy Algorithms)

贪心算法

适用于最优化问题的算法往往包含一系列步骤，每一步都有一组选择。贪心算法是使所做的选择看起来是当前最佳的，期望通过所做的局部最优解来产生出一个全局最优解。贪心算法对大多数优化问题来说可以产生最优解，但并不一定总是这样的。贪心算法的两个经典例子是最小生成树算法和Dijkstra单源最短路径算法。

1贪心策略的基本内容

贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点，做一个当时看起来最佳的选择。这种启发式的策略并不是总能产生最优解，但它常常能给出最优解。

一般地，根据以下步骤设计贪心算法：

（1）        将优化问题转化为这样的一个问题：先做出选择，再解决剩下的一个子问题。

（2）        证明原问题总有一个最优解是做贪心选择得到的，从而说明贪心选择的安全。

（3）        说明做出贪心选择后，剩余的子问题具有这样的性质：如果将所做出的选择与子问题的最优解联合起来，可得到原问题的一个最优解。

在贪心算法中，贪心选择性和最优子结构是两个关键特点。如果我们能够证明问题具有这两个性质，那么就可以设计出它的一个贪心算法。

1.1   贪心选择性

贪心选择性：一个全局最优解可以通过局部最优选择来达到。在每个决策点，我们只做当前看似最佳的选择，然后再解决做出选择之后出现的子问题。贪心算法所做的当前选择可能依赖于已经做出的所有选择，但不依赖于有待于做出选择的子问题的解。

我们必须证明在每一步所做的贪心选择最终能产生一个全局最优解。

1.2    最优子结构

对于一个问题来说，如果它的一个最优解包含了其子问题的最优解，则称该问题具有最优子结构。在贪心算法中，一般是在原问题的基础上做出一个贪心选择而得到一个子问题，我们要证明将子问题的最优解与所做的贪心选择合并起来后可以得到原问题的一个最优解。

 

Example 1：最小生成树

请见下一篇文章：最小生成树(Greedy Algorithms)

Example 2: Dijkstra单源最短路径

请见下一篇文章：Dijkstra单源最短路径(Greedy Algorithms)