首页 > Python算法 > 贪心算法 阅读数:28

贪心算法是什么

之前我们讲解了动态规划。当一个问题具有最优子结构时,可以使用动态规划求解。求解虽比一般的递归求解资源消耗小,但是我们通常还是要将每个子问题都求解出来。很多最优化问题还能不能简化呢?答案当然是肯定的。这就设计我们将要学习的另一种方法——贪心算法

上节教程的最长递增子序列问题中我们就进行了优化。针对最优子结构的动态规划设计,我们还有一种优化方法,就是我们要讲解的贪心算法。很多情况下,贪心算法在求解最优化问题时,更加简单有效。

其基本原理是,遵循某种既定原则,不断地选取当前条件下最优的选择来构造每一个子步骤,直到获得问题最终的求解。即在求解时,总是作出当前看来最好的选择。也就是说,不从整体最优上加以考虑,仅是求解局部最优解,以期望能找到全局最优解。

所以,本节教程我们讨论的贪心算法虽然与之前的动态规划类似,都是将原来的较大规模的问题拆分为规模较小的问题,依据大问题与小问题之间的递推关系,通过解决较小规模的问题,最终获得原始问题的求解。但是动态规划要通盘考虑各个阶段各子问题的求解情况,从全局的角度进行衡量,最终找到解决原始问题的最佳解决方案。

为了提高问题解决效率,避免针对相同子问题的重复计算,动态规划在解决问题的过程中会引入一张记录表,将子问题的解记录下来,可以供其他阶段求解时使用。因此,动态规划的核心是填充这张记录表,在填表的过程中,获得原问题的最优解。

贪心算法与动态规划的不同之处在于,贪心算法利用问题的贪心性质,简化了分解原始问题的过程,每次只关注在当前状态下可以获得的局部最优解,通过拼接各阶段的局部最优解获得最终问题的解。因为贪心选择可以依赖于以往所做的选择,但绝不依赖于未来所做的选择,也不依赖于子问题的解。故而贪心算法往往求解时与动态规划相反,采用自顶向下的方式,迭代作出贪心选择,不断化简问题规模。

利用贪心算法解题,需要解决两个问题。

1) 一是问题是否适合用贪心法求解,即所求解问题是否具有贪心选择性质。所谓贪心选择性质是指应用同一规则,将原问题变为一个相似的但规模更小的子问题,而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择,但不依赖于未做出的选择。

从全局来看,运用贪心策略解决的问题在程序的运行过程中无回溯过程。贪心选择性质的证明一般采用数学归纳法,证明每一步做出的贪心选择确实能导致问题的整体(全局)最优解,也有基于算法的输出,或使用一种“拟阵”结构等形式的证明。

2) 二是问题是否具有局部最优解,从而通过选择一个贪心标准,可以得到问题的最优解。

另外还有一个问题值得注意。贪心算法和动态规划都依赖于问题具有最优子结构性质,但并不是具有最优子结构性质的问题就可以用贪心算法求解。也就是说,贪心算法不总能对动态规划求解最优化问题进行优化。比如动态规划中我们提到的“0-1 背包问题”,由于无法保证背包总能完全塞满,闲置空间的浪费导致贪心算法并不总能适用。

利用贪心算法解题的思路如下:
  1. 建立对问题精确描述的数学模型,包括定义最优解的模型;
  2. 将问题分成一系列的子问题,同时定义子问题的最优解结构;
  3. 应用贪心算法原则可以确定每个子问题的局部最优解,并根据最优解模型,用子问题的局部最优解堆叠出全局最优解。

在本章中,我们重点关注以下 3 个实际问题: