AI产品经理必修——揭开算法的面纱（贪心算法）

去年“新智元”有一篇报道《清华毕业计算机教授遭持枪劫车，靠“贪心算法”追回秒杀美国警察》，整个故事像看微小说一样，可对于核心问题“贪心算法”是什么并没有说清楚，于是就有了下面的内容。

一、什么是贪心算法

贪心的意思在于在作出选择时，每次都要选择对自身最为有利的结果，保证自身利益的最大化，贪心算法就是利用这种贪心思想而得出一种算法。

贪心算法可以简单描述为：大事化小，小事化了。对于一个较大的问题，通过找到与子问题的重叠，把复杂的问题划分为多个小问题。并且对于每个子问题的解进行选择，找出最优值，进行处理，再找出最优值，再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。

贪心算法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

二、贪心算法基本思路

步骤一：建立数学模型来描述问题。

步骤二：把求解的问题分成若干个子问题。

步骤三：对每个子问题求解，得到子问题的局部最优解。

步骤四：把子问题的解局部最优解合成原来问题的一个解。

三、贪心算法的选择

所谓贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。

贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

我们下面通过示例来看一下贪心算法如何选择。

四、贪心算法示例

看一下《算法导论》中的经典例题：活动选择问题。

有n个需要在同一天使用同一个教室的活动a1，a2……an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行（标红的是我们利用贪心算法求出的结果1、4、8、11）。

第一步：分析题目

目标函数count（n）活动次数最多。

约束条件是下一个活动开始时间大于或等于上一个活动开始时间s[i]>=f[j]。

第二步：选择解题思路

• 每次选择开始时间最早的活动
• 每次选择持续时间最短的活动
• 每次选取结束时间最早的活动

第三步：证明上面哪种思路可以应用于本题

为了方便，我们用不同颜色的线条代表每个活动，线条的长度就是活动所占据的时间段，蓝色的线条表示我们已经选择的活动；红色的线条表示我们没有选择的活动。

1）如果我们每次都选择开始时间最早的活动，不能得到最优解

证明（反证法）：

例如我们选择了10号活动（开始时间2点，结束时间13点）；

2号活动待选择（开始时间3点，结束时间5点）；

则会出现上图所示的情况，这显然违背了约束条件。

2）如果我们每次都选择持续时间最短的活动，不能得到最优解

证明（反证法）：

例如我们选择了2号活动（开始时间3点，结束时间5点）；

1号活动待选择（开始时间1点，结束时间4点）；

则会出现上图所示的情况，这显然也违背了约束条件。

3）如果我们每次都选取结束时间最早的活动，能够得到最优解（采用的贪心策略）

那么怎么证明贪心算法是对的呢？

要证明一个算法是错的非常简单，要证明是对的却非常难。对于贪心算法的证明，一是使用归纳法，二是采用反证法。像上面两种策略，我们实际上就用到了反证法。

回到策略本身，按这种方法选择相容活动，能够为未安排的活动留下尽可能多的时间。

第四步：选好策略，那我们就来按照贪心算法的基本思路总结一下

1. 数学模型是目标函数count（n）最大，约束条件是s[i]>=f[j]；
2. 求解哪个活动结束时间最早（本题目显然是活动1）；
3. 求解哪个动开始时间s[i]大于上一个活动结束时间f[j]；
4. 把步骤三求出的活动依次取出，作为我们选取的活动

上代码：

这段代码的含义是：

1. 定义活动号n，活动开始时间、结束时间Type s[]，Type f[]，布尔逻辑判断A[]；
2. 定义进入算法的活动序号，最终选取的活动序号i，j；
3. 初始活动i=1，由于1号活动结束时间，所以选取j=1。

从2号活动开始进入运算，具体运算规则：

• 判断条件：活动开始时间（i）>上一个活动结束时间（j）
• A[]为true，j选中
• A[]为false，j不选择
• i自增1位，继续判断，直至i=11

上图直观展示了算法的整个运行过程。

五、贪心算法应用

贪心算法应用非常广泛，特别电脑游戏AI或者一些推荐。

以经典的跳跃游戏为例：

1.题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断是否能够到达最后一个位置。

2.问题分析

先转化为数学模型：给定一个数组，数组中每个位置的数字代表当前位置i能够向前跳跃num[i]的距离，然后判断是否能够从第一个位置跳到最后一个位置。

这道题的难点就在于每次跳多远的距离算合适呢？

如果从i的位置能跳num[i]距离最远能到达j的位置，那么这中间的任何一个位置我们都能跳到，但我们具体是跳到i–j之间的哪个位置才是真正合适的位置？

利用贪心的思想我们的目的是判断最后能否跳到最后一个位置，其实就是只要能保证在i–j之间跳到一个能够在下一次跳的更远的距离，那么这个位置就是最合适的位置。

本文作者 @CARRIE

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！