A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.

In many problems, a greedy strategy does not in general produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time.

贪婪算法

在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

例如：之前讲过的狄克斯特拉和广度优先搜索都属于贪婪算法。

步骤

1. 建立数学模型来描述问题。
2. 把求解的问题分成若干个子问题。
3. 对每一子问题求解，得到子问题的局部最优解。
4. 把子问题的解局部最优解合成原来解问题的一个解。

NP完全问题

以难解著称的问题，判断NP完全问题很难。但还是有一些蛛丝马迹可寻：

1. 元素较少时运行速度很快，随着元素数量增加，速度会变得非常慢。
   2，涉及“所有组合”的问题，经常是NP完全问题。
2. 不能将问题分成小问题，必须考虑各种情况。
3. 如果涉及序列或集合且难以解决。
4. 问题可转换为集合覆盖问题或旅行商问题。

近似算法

有些问题（NP完全问题），没有任何算法可以足够快的解决这个问题。需要用到近似算法，可以得到非常接近的解。
贪婪算法就是一种简单易实现的近似算法。

一般判断一个近似算法优劣的标准如下：

1. 速度有多快。
2. 得到的近似解和最优解的接近程度。

备注：这里没有讲解具体的实例，介绍的非常基础，之后再算法进阶学习中进一步说明。