【内部资料】贪心法(Greed Method) 又称为贪婪算法

贪心法(Greed Method) 又称为贪婪算法，从某一起点开始，就是在每一个解决问题步骤中使用贪心原则，即采取在当前状态下最有利或最优化的选择，不断地改进该解答，持续在每一步骤中选择最佳的方法，并且逐步逼近给定的目标，当达到某一步骤不能再继续前进时算法停止，以尽可能快地求得更好的解。

贪心法的精神虽然是把求解的问题分成若干个子问题，不过不能保证求得的最后解是最佳的,贪心法容易过早做决定，只能求满足某些约束条件可行解的范围，不过在有些问题中却可以得到最佳解，经常用于求图的最小生成树 (MST) 、最短路径与霍哈夫曼编码等。

我们来看一个简单的例子(后面的货币系统不是现实的情况，只为了举例)，假设我们今天去便利商店买了几听可乐，总价是 24 元，我们付给售货员 100 元，并且我们希望不要找太多硬币，即硬币的总数量最少，该如何找钱呢? 假如目前的硬币有 50 元、10 元、5 元、1元 4种，从贪心法的策略来说，应找的钱总数是 76 元，所以一开始选择 50 元的硬币一，接下来就是 10 元的硬币两枚，最后是 5 元的硬币和1元的硬币各一枚，总共5 枚硬，这个结果也确实是最佳解答。

贪心法也适合用于旅游某些景点的判断，假如我们要从下图 中的顶点 5 走到顶点 3，最短的路径该怎么走才好呢?以贪心法来说，当然是先走到顶点 1 最近，接着选择走到顶点 2，最后从顶点 2走到顶点 3，这样的距离是 28。可是从图中我们发现直接从顶点5 走到顶点3 才是最短的距离。也就是说，在这种情况下，是没有办法以贪心法规则来找到最佳解答的。