求解最优化问题的算法通常需要经过一系列的步骤,在每一个步骤都面临多种选择。对于许多最优化问题,使用动态规划算法有些杀鸡用牛刀了,可以使用更简单、更高效的算法。贪心算法(greedy algorithm)就是这样的算法,它在每一步都做出当时看起来最佳的选择。也就是说,它总是做出局部最优的选择,寄希望这样的选择能够导致全局最优解。 ——《算法导论》
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优解上加以考虑,他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
很多问题可以用动态规划来解决,但如果我们能够证明一直做出贪心选择就能得到最优解的话,我们就能得到一个贪心算法。
设计贪心算法的过程包括如下步骤:
- 确定问题的最优子结构
- 设计一个递归算法
- 证明如果我们做出一个贪心选择,则只剩下一个子问题
- 证明贪心选择总是安全的
- 设计一个递归算法实现贪心策略
- 将递归算法转换为迭代算法
在以上过程中我们可以看到,贪心算法是以动态规划为基础的(在思考问题方面)。比如在动态规划中,我们会定义子问题 S(i,j),然后我们发现,如果总是做出贪心选择,则可以将子问题限定为 S(k) 的形式。也就是通过贪心选择来改变最优子结构,使得只有一个子问题被留下。 每一个用贪心算法解决的问题中,几乎总有一个更繁琐的动态规划算法。
更一般地,我们可以将贪心算法地设计提炼为如下更直接的步骤:
- 将最优化问题转化为如下形式:对其做出一个选择后,只剩下一个子问题需要解决。
- 证明做出贪心选择后,原问题总是存在最优解,即贪心选择总是安全的。
- 证明做出贪心选择后,剩余的子问题满足如下性质:其最优解与贪心选择组合即可得到原问题的最优解。
🔶 贪心选择性质
当进行选择时,我们直接做出在当前问题中看来是最优的选择,而不必考虑子问题的解。这也是贪心算法与动态规划的不同之处。
在动态规划中,每个步骤的选择通常依赖于子问题的解。因此,我们通常以一种自底向上的方式(分析的时候自顶向下,实现的时候自底向上)求解动态规划问题。在贪心算法中,我们总是做出当时看来是最佳的选择,然后求解剩下的唯一的子问题。贪心算法选择时可能依赖之前做出的选择,但不依赖任何将来的选择活着子问题的解。因此贪心算法在求解第一次选择前不求解任何子问题。一个动态规划算法是自底向上进行计算的,而一个贪心算法通常是自顶向下的,进行一次又一次贪心选择,将问题实例变得更小。
❇️ 贪心问题解决思路 (摘自leetcode)
那么对于原始的复杂问题,如何能够知道他是否能被贪心解决呢?
- 首先,我们需要将原始问题拆解成子问题,明确子问题的局面以及局面中可进行的操作。实际上不止贪心问题,很多问题都需要这样的拆解过程。
- 然后我们需要考虑子问题的最优,是否能保证全局最优。如果能的话,我们就可以只考虑如何解子问题,否则就可能需要动态规划或者搜索解了。
- 最后,我们需要考虑如何使子问题最优,可能有些问题存在乍一看可行的策略,但是我们仍然需要仔细思考甚至证明。以保证没有漏掉什么细节情况。
对于第三点,很多同学这里会经常犯错。比如以为贪心做法是对的,但是实际上有问题。例如错误地用贪心解决 01 背包问题(子问题最优,原问题不一定最优)等。所以如果我们觉得某道题目存在贪心策略,最好自己证明一下正确性再实现。
贪心算法的现实应用
- 数据压缩编码(Huffman 编码)
- 最小生成树(minimum-spanning-tree)
- Dijkstra 最短路径算法