数据结构与算法 / 贪心算法

一、诞生原因

有如下场景：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。

为了达到上述目的，贪心算法是其中的一个解决方案。

例如，路径选择问题，从 S 城市至 E 城市，在只能路过 2 个城市的情况下，如何走的最短，如下图所示：

二、基本信息

英文全称：greedy algorithm

三、原理说明

每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。

转为解决上图的问题的语言：保证每次从当前城市走到下一个城市的路径最短，即：路径为 S ➡ A2 ➡ B1 ➡ E ，总长度为 1 + 1 + 2 = 4 。

四、缺陷说明

贪心算法每次计算时其结果都会受到之前 n 次结果的影响，有可能之前某一次的结果导致之后的结果都是较次的，从而得不到全局最优解。栗子：

按照贪心算法，路径为 S ➡ A2 ➡ B1 ➡ E ，总长度为 1 + 5 + 7 = 13，

但是实际上最佳路径为 S ➡ A3 ➡ B2 ➡ E，总长度为 5 + 2 + 1 = 8 。

五、实际应用

1、霍夫曼编码（Huffman Coding）

2、Prim 和 Kruskal 最小生成树算法

3、Dijkstra 单源最短路径算法

 

（SAW：Game Over！）