人工智能产品经理强制——揭示算法(贪婪算法)

楼主  收藏   举报   帖子创建时间:  2020-06-24 14:22 回复:0 关注量:0

人工智能产品经理有必要掌握一些算法。本文将从五个方面谈谈人工智能产品经理所需要的贪婪算法,希望能对你有所帮助。

去年,《新智元》上有一篇《清华毕业计算机教授遭持枪劫车,靠“贪心算法”追回秒杀美国警察》的报道。整个故事就像读一本微型小说,但是核心问题“贪婪算法”没有被清楚地陈述,所以有以下内容。

一、什么是贪心算法

贪婪意味着在做出选择时,我们应该总是选择对自己最有利的结果,并确保我们自身利益的最大化。

贪婪算法可以被简单地描述为:大的东西变小,小的东西变小。对于一个大问题,通过寻找子问题的重叠,把复杂的问题分成几个小问题。选择每个子问题的解,找出最优值,处理它,找出最优值,然后处理它。也就是说,贪婪算法是一种在选择的每一步都在当前状态下进行最佳或最优选择,从而获得最佳或最优结果的算法。

贪婪算法在解决问题时总是做出最好的选择。也就是说,在某种意义上,所做的只是局部最优解,而没有考虑整体最优解。贪婪算法不能获得所有问题的全局最优解,但它能为广泛的问题产生全局最优解或全局最优解的近似解。

二、贪心算法基本思路

第一步:建立一个数学模型来描述问题。

步骤2:将问题分成几个子问题。

第三步:求解每个子问题,获得子问题的局部最优解。

步骤4:将子问题的局部最优解合成原问题的解。

三、贪心算法的选择

所谓贪婪选择是指期望问题的全局最优解可以经过一系列局部最优选择。换句话说,当考虑做出哪个选择时,我们只考虑当前问题的最佳选择,而不考虑子问题的结果。

贪婪算法以迭代的方式做出连续的贪婪选择。每个贪婪的选择都将期望的问题简化成更小的子问题。对于一个具体的问题,要确定它是否具有贪婪选择的性质,必须证明在每一步中做出的贪婪选择最终导致问题的整体最优解。

让我们通过例子来看看如何选择贪婪算法。

四、贪心算法示例

看看《算法导论》中的经典例子:活动选择。

有n个活动a1、a2.需要在同一天使用同一个教室,且该教室只能同时用于一个活动。每个活动ai都有一个开始时间si和一个结束时间fi。一旦选择,活动ai占据半开放时间间隔[si,fi]。如果[si,fi]和[sj,fj]不相互重叠,ai和aj活动将于这一天在可以安排。问题是如何安排这些活动,以便尽可能多的活动可以在没有冲突的情况下进行(通过贪婪算法获得的结果1、4、8和11用红色标记)。

第一步:分析题目

目标函数计数(n)具有最多的活动。

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

第二步:选择解题思路

每次选择最早开始时间的活动

选择每次持续时间最短的活动

选择每次结束时间最早的活动

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

为了方便起见,我们使用不同颜色的线条来表示每个活动,线条的长度是活动所占用的时间段,蓝色的线条表示我们选择的活动。红线表示我们别无选择的活动。

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

证明(反证):

例如,我们选择了第10项活动(开始时间2点,结束时间13点);

要选择的活动2(开始时间3点,结束时间5点);

将出现上图所示的情况,这显然违反了约束条件。

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

证明(反证):

例如,我们选择了活动2(开始时间3点,结束时间5点);

要选择的活动1(开始时间1: 00,结束时间4:00);

将出现上图所示的情况,这显然违反了约束条件。

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

那么我们如何证明贪婪算法是正确的呢?

证明一个算法是错误的是非常简单的,但是证明它是正确的是非常困难的。对于贪婪算法的证明,一个是归纳,另一个是反证法。像上面的两个策略一样,我们实际上使用了反证法。

回到策略本身,以这种方式选择兼容的活动可以为计划外的活动留出尽可能多的时间。

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

数学模型具有最大目标函数数(n),约束条件为s[I]=f[j];

找出哪个活动的结束时间最早(这个主题显然是活动1);

求解哪个动态开始时间s[i]大于最后一个活动结束时间f[j];

将步骤3中获得的活动依次作为我们选择的活动。

上面的代码:

该代码的含义是:

定义活动编号n、活动开始时间、活动结束时间类型s[]、类型f[]、布尔逻辑判断a[];

定义进入算法的活动序列号,最后选择活动序列号一和活动序列号二;

I=1表示初始活动,j=1表示第一个活动的结束时间。

从活动2输入操作,有具体的操作规则:

判断条件:活动开始时间(I)最后活动结束时间(j)

[]为真,选择j

[]为假,未选择j

I增加1位,并继续判断,直到i=11

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

五、贪心算法应用

贪婪算法被广泛使用,尤其是电脑游戏的人工智能还是有些推荐的。

以经典的跳跃游戏为例:

1.标题描述

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

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

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

2.问题分析

首先,它被转换成一个数学模型:给定一个数组,数组中每个位置的个数代表当前位置I可以向前跳的距离num[i],然后判断它是否可以从第一个位置跳到最后一个位置。

这个问题的难点在于每次跳多远才合适?

如果我们能把num[i]从I的位置跳到尽可能远的j的位置,那么我们就能跳到中间的任何位置,但是我们具体跳到I和j之间的哪个位置才是真正合适的位置呢?

用贪婪的思想,我们的目标是判断我们是否能跳到最后一个位置。事实上,只要我们能保证跳到i-j之间更远的距离,那么这个位置就是最合适的位置。

打赏