贪心算法

贪心法，又称贪心算法、贪婪算法、或称贪婪法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。

思想

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止[3]。

过程

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

贪婪算法可解决的问题通常大部分都有如下的特性：

• 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。
• 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
• 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。
• 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
• 最后，目标函数给出解的值。
• 为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。

【出处：百度百科，URL：贪婪算法]

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

贪心算法的基本思路：

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

实现该算法的过程：从问题的某一初始解出发；while能朝给定总目标前进一步do ,求出可行解的一个解元素；最后，由所有解元素组合成问题的一个可行解。

贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。

贪心法的应用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式

所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。其实很多的智能算法（也叫启发式算法），本质上就是贪心算法和随机化算法结合——这样的算法结果虽然也是局部最优解，但是比单纯的贪心算法更靠近了最优解。例如遗传算法，模拟退火算法。

【出处：NIST，URL：https://xlinux.nist.gov/dads/HTML/greedyalgo.html]

例题分析

案例1：

下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。

[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品A B C D E F G

重量35 30 60 50 40 10 25

价值10 40 30 50 35 40 30

分析：

目标函数：∑pi最大

约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)

（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？

（2）每次挑选所占重量最小的物品装入是否能得到最优解？

（3）每次选取单位重量价值最大的物品，成为解本题的策略。

值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。

贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。

可惜的是，它需要证明后才能真正运用到题目的算法中。

一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：

（1）贪心策略：选取价值最大者。反例：

W=30

物品：A B C

重量：28 12 12

价值：30 20 20

根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。

（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。

（3）贪心策略：选取单位重量价值最大的物品。反例：

W=30

物品：A B C

重量：28 20 10

价值：28 20 10

根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。

案例2：

上图示例，找到最大值得路径，根据贪婪算法，会选择7，12，6.但是实际得最大路径为7，3，99.因此贪婪算法有可能会收敛于局部最优解。

【出处：wiki，URL：https://en.wikipedia.org/wiki/Greedy_algorithm]

发展历史

描述

经典得贪婪算法有Dijkstra's algorithm, Huffman coding, Kruskal's algorithm, optimal merge, Prim-Jarnik algorithm.

该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，Prim算法又被称为DJP算法、亚尔尼克算法或Prim-Jarnik algorithm.。

1951年，David A. Huffman和他的麻省理工学院信息理论同学们选择了学期论文。Robert M. Fano教授为寻找最有效的二进制代码问题分配了一份学期论文。Huffman无法证明任何代码是最有效的，他打算放弃并开始研究最终的结果时，他碰到使用频率排序二叉树的想法，并迅速证明这种方法是最有效的。这样做，Huffman超过了与信息理论发明家克劳德香农合作开发类似代码的范诺。与自顶向下Shannon-Fano编码不同，从底层构建树保证了最优性。1952年，于论文《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）中发表了这个编码方法。

Kruskal算法是一种用来查找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪心算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。

Edsger Dijkstra在1959年在ARMAC计算机上写出了Dijkstra算法，它来搜索最短路径的算法。Dijkstra是经典得贪婪算法之一。

在1968年，人工智能研究员尼尔斯·尼尔森(Nils Nilsson)试图改进机器人Shakey所做的路径规划，这个机器人原型可以通过在一个包含障碍物的房间进行导航。这种寻路算法，Nilsson称之为A1，是当时最著名的Hans Berliner于1979算法的更快版本，用于在图中找到最短路径。Bertram Raphael建议对这个算法进行一些重要的改进，并调用了修改后的A2。然后Peter E. Hart引入了一个论证，建立了A2，只有微小的变化，才能成为寻找最短路径的最佳算法。

1985 Richard Korf Iterative deepening A* (IDA*)是一种图遍历和路径搜索算法，它可以在一个加权图中找到指定的起始节点和一组目标节点的任何成员之间的最短路径。它是迭代深化深度优先搜索的一个变体，它借用了一个启发函数来评估剩余的成本，以从a *搜索算法获得目标。由于它是深度优先的搜索算法，它的内存使用率低于A*，但与普通的迭代深化搜索不同，它专注于探索最有希望的节点，因此不会访问。与A*不同，IDA*不使用动态编程，因此经常会多次访问相同的节点。1993年，Korf, R. E. (1993).对BFS进行延伸，提出RBFS，将A*储存空间减小为线性增长。

主要事件

发展分析

瓶颈

一个正确的贪心算法拥有很多优点，比如思维复杂度低、代码量小、运行效率高、空间复杂度低等，是信息学竞赛中的一个有力武器。缺点：贪心法的缺点集中表现在他的“非完美性”。通常我们很难找到一个简单可行并且保证正确的贪心思路，即使我们找到一个看上去很正确的贪心思路，也需要严格的正确性证明。这往往给我们直接使用贪心算法带来了巨大的困难。

未来发展方向

在求解一个问题的过程中，如果再每一个阶段的选择都是当前状态下的最优选择，即局部最优选择，并且最终能够求得问题的整体最优解，那么说明这个问题可以通过贪心选择来求解，这时就说明此问题具有贪心选择性质。然而如何，可以更简单得来证明一个问题具有贪心选择性质也是可以考虑得地方。

Contributor: Ruiying Cai