贪心算法(Greedy Algorithm)理论篇_greedy算法优缺点参考文献

求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择。对于许多最优化问题，使用动态规划算法来求解最优解问题有点大材小用，可以使用更简单、更高效的算法，如贪心算法。贪心算法在每一步都做出当时看起来最佳的选择，也就是局部最优的选择，寄希望这样的选择能导致全局最优解。
贪心算法并不保证得到最优解，但很多问题确实可以求得最优解。贪心算法通常是自顶向下的设计：做出一个选择，然后求解剩下的那个子问题，而不是自底向上地求解出很多子问题，然后再做出选择。

贪心算法原理

贪心算法通过做出一系列选择来求出问题的最优解。在每个决策点，贪心算法做出在当时看似最佳的选择。这种启发式策略并不能保证总能找到最优解，但对有些问题确实有效。可以按照如下步骤设计贪心算法：
(1) 将最优化问题转换成这种形式：对其做出一次选择后，只剩下一个子问题需要求解。
(2) 证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的。
(3) 证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。
如何证明一个贪心算法是否能求解一个最优解问题？并没有普适的方法。但贪心选择性质和最优化子结构是两个关键要素。

贪心选择性质（Greedy-Choice Property）

贪心选择性质是指可以通过做出局部最优（贪心）选择来构造全局最优。也就是说，当进行选择时，只需要做出当前问题中看起来最优的选择，则不必考虑子问题的解。
在动态规划中，每个步骤都要进行一次选择，但选择通常依赖于子问题的解。因此，通常以一种自底向上的方式求解动态规划的问题：先求解较小的子问题，然后是较大的子问题。而在贪心算法中，总是做出当前看起来最佳的选择，然后求解剩下的唯一的子问题。贪心算法进行选择时，可能依赖之前的选择，但不依赖任何将来的选择或子问题的选择。因此，动态规划是先求解子问题然后才能进行第一次选择，贪心算法在进行第一次选择之前不求解任何子问题。
注意，必须证明每个步骤做出的贪心选择能生成全局最优解。否则，这个问题可能无法用贪心算法获取最优解。

最优子结构

如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。（与动态规划中最新子结构概念一致）
当使用贪心算法时，通常使用更为直接的最优子结构。通过使用贪心选择得到子问题后，接下来需要做的就是论证，将子问题的最优解与贪心选择组合在一起后能生成原问题的最优解。这种方法隐含地对子问题使用了数学归纳法，证明在每个步骤进行贪心选择会生成原问题的最优解。

贪心算法和动态规划

贪心算法和动态规划都利用最优子结构性质。
动态规划算法将问题划分为多个子问题，然后将这些子问题的最优解整合成原问题的一个最优解。在确定该将哪些子问题用于最优解时，要考虑几种选择。贪心算法只需考虑一个选择（即贪心的选择），进而完成贪心方法的过程。
贪心算法和动态规划最大的不同在于，动态规划会首先寻找子问题的最优解，然后在其中进行选择，则贪心算法是首先做出一次“贪心”选择（在局部看来最优的选择），然后求解选出的子问题，从而不必费心求解所有可能相关的子问题。

贪心算法的实现方法

贪心算法通常使用自顶向下的思想设计：做出一个选择，然后求解剩下的子问题，而不是自底向上地求解出子问题，然后再做出选择。在实现方式上，又可细分为基于递归的贪心算法和基于迭代的贪心算法。

拟阵和贪心算法

贪心算法的背后有一个相当复杂的理论，它是基于一种称为“拟阵”（matroid）的抽象组合结构。虽然该理论不能涵盖贪心方法适用的所有情况，但它确实覆盖了很多有实际意义的情况。而且，这种理论的扩展还覆盖了其他应用。更多拟阵相关的理论可参考《算法导论》一书或专业数据书籍。

参考

《算法导论》 第十六章 贪心算法 第三版 Tomas H. Cormen etc. 殷建平 等译
《算法设计与分析基础》 第九章 贪婪技术 第三版 Anany Levitin 著 潘彦 译