[AI工具宝典]AI产品经理必修——揭开算法的面纱（贪心算法）.pdfVIP

对于AI产品经理来说，掌握一些算法是必要的。本文将从五个方面，讲述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）如果我们每次都选取结束时间最早的活动，能够得到最优解（采用的贪心策略）

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

要证明一个算法是错的非常简单，要证明是对的却非常难。对于贪心算法的证明，一是使

用归纳法，二是采用反证法。像上面两种策略，我们实际上就用到了反证法。

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

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

数学模型是目标函数count（n）最大，约束条件是s[i]=f[j]；求解哪个活动结束时间

最早（本题目显然是活动1）；求解哪个动开始时间s[i]大于上一个活动结束时间f[j]；

把步骤三求出的活动依次取出，作为我们选取的活动

上代码：

这段代码的