AI产品经理必修:揭开算法的面纱(动态规划)

栏目: IT技术 · 发布时间: 4年前

内容简介:对于AI产品经理来说,掌握一些算法是必要的。本文从是什么、解决什么问题、应用场景、应用过程和相关案例等几个方面,讲述了AI产品经理必修的动态规划算法,希望对你有帮助。乔治·桑塔亚纳说过,“那些遗忘过去的人注定要重蹈覆辙。”这句话放在问题求解过程中也同样适用。不懂动态规划的人会在解决过的问题上再次浪费时间,懂的人则会事半功倍。要了解这句话,得从动态规划的含义说起。

对于AI产品经理来说,掌握一些算法是必要的。本文从是什么、解决什么问题、应用场景、应用过程和相关案例等几个方面,讲述了AI产品经理必修的动态规划算法,希望对你有帮助。

AI产品经理必修:揭开算法的面纱(动态规划)

乔治·桑塔亚纳说过,“那些遗忘过去的人注定要重蹈覆辙。”这句话放在问题求解过程中也同样适用。不懂动态规划的人会在解决过的问题上再次浪费时间,懂的人则会事半功倍。要了解这句话,得从动态规划的含义说起。

一、什么是动态规划?

quora上有这样一个问题:

How should I explain dynamic programming to a 4-year old?底下有个42K赞同的答案,是这样说的:
*writes down “1+1+1+1+1+1+1+1 =” on a sheet of paper*”What’s that equal to?”
*counting* “Eight!”
*writes down another “1+” on the left*
“What about that?”
*quickly* “Nine!”
“How’d you know it was nine so fast?””You just added one more”
“So you didn’t need to recount because you remembered there were eight!DynamicProgramming is just a fancy way to say ‘remembering stuff to save time later”

就不翻译了,相信大家都能看懂。

现在,我们来看一下动态规划的 官方定义

动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。

动态规划算法的基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

按照定义, 动态规划的原理是将一个问题分解成子问题,逐渐求解局部最优解并扩展,最终得出全局最优解 。但是我觉得的这个不是动态规划的核心思想,或者说,一个”大问题“之所以能用”动态规划解决,并不是因为它能拆解成一堆小问题, 而是这些”小问题“会不会被被重复调用。 

这个概念很重要,实际上很多问题都可以拆解成小问题来解决,例如我们之前讲的贪心算法,但这个区别决定了该选取哪种算法 。

二、动态规划能解决什么问题?

如果一个问题满足以下两点,那么它就能用动态规划解决。

(1)问题的答案依赖于问题的规模,也就是问题的所有答案构成了一个数列。举个简单的例子,1人有2条腿,2个人有4条腿,n个人有多少条腿?答案是2n条腿。这里的2n是问题的答案,n则是问题的规模,显然问题的答案是依赖于问题的规模的答案是因变量,问题规模是自变量。因此,问题在所有规模下的答案可以构成一个数列(f(1),f(2)…f(n)),比如刚刚“数腿”的例子就构成了间隔为2的等差数列(0,2.4….2n) 。

(2)大规模问题的答案可以由小规模问题的答案递推得到,还是刚刚“数腿” 的例子,显然f(n)可以甚于f(n-1) 求得: f(n)= f(n-1)+2

三、动态规划的应用?

应用场景:动态规划比较合适的就是来求最优问题的,比如求最大值,最小值等等。它可以显著的降低复杂度,节约计算时间。所有的导航系统都采用了动态规划。

我们就是以导航为例来看看动态规划吧。

比如,我们想找到从北京到广州的最短行车路线或者最快行车路线。当然,最直接的笨办法是把所有可能的路线看一遍,然后找到最优的。

这种办法只有在节点数是个位数的图中还行得通,当图的节点数(城市数目)有几十个的时候,计算的复杂度就已经让人甚至计算机难以接受了,因为所有可能路径的个数随着节点数的增长而成呈指数增长(或者说几何级数),也就是说每增加一个城市,复杂度要大一倍,显然我们的导航系统中不会用这种笨办法。

以上面的问题为例,当我们要找从北京到广州的最短路线时,我们先不妨倒过来想这个问题:假如我们找到了所要的最短路线(称为路线一),如果它经过郑州,那么从北京到郑州的这条子路线(比如是北京-> 保定->石家庄->郑州,称为子路线一),必然也是所有从北京到郑州的路线中最短的。

在实际实现算法时,我们又正过来解决这个问题,也就是说,要想找到从北京到广州的最短路线,先要找到从北京到郑州的最短路线。当然,聪明的读者可能已经发现其中的一个”漏洞”,就是我们在还没有找到全程最短路线前,不能肯定它一定经过郑州。不过没有关系,只要我们在图上横切一刀,这一 刀要保证将任何从北京到广州的路一截二,如下图:

AI产品经理必修:揭开算法的面纱(动态规划)

那么从广州到北京的最短路径必须经过这一条线上的某个城市(图中蓝色的菱形) 。我们可以先找到从北京出发到这条线上所有城市的最短路径,最后得到的全程最短路线一定包括这些局部最短路线中的一条,这样, 我们就可以将一个”寻找全程最短路线”的问题,分解成一个个小的寻找局部最短路线的问题。

只要我们将这条横切线从北京向广州推移,直到广州为止,我们的全程最短路线就找到了。这便是动态规划的原理。采用动态规划可以大大降低最短路径的计算复杂度。

四、动态规划的过程?

当要应用动态规划来解决问题时,归根结底就是将动态规划拆分成以下三个关键目标。

1. 建立状态转移方程

这一步是最难的,大部分人都被卡在这里。这步没太多的规律可说,只需抓住个思维: 当做已经知道f(1)~ f(n- 1)的值,然后想办法利用它们求得f(n)。

2. 缓存并复用以往结果

这一步不难,但是很重要。如果没有合适地处理,很有可能就是指数和线性时间复杂度的区别。在我们上面的例子中,每加入一条横截线,线上平均有十个城市,从广州到北京最多经过十五个城市,那么采用动态规划的计算量是 10×10×15,而采用穷举路径的笨办法是 10 的 15 次方,前后差了万亿倍。

3. 按顺序从小往大算

这里的“小和“大”对应的是问题的规模,在这里也就是我们要从f(0), f(1).到f(n)依次顺序计算。这点从导航的例子来看,似乎显而易见,因为状态方程基本限制了你只能从小到大一步步递推出最终的结果。

五、经典动态规划

我们来尝试用动态规划实现经典斐波那契数列

斐波那契数列: 0,1. 1,2,3,5,8, 13, 21,34.55, 89, 1443….

它遵循这样的规律:当前值为前两个值的和。

那么第n个值为多少?

我们用两种方法来做比较:

方法一:简单递归

AI产品经理必修:揭开算法的面纱(动态规划)

如上所示,代码简单易懂,然而这代码却极其低效。

下图通过展示求解f(6)的过程说明了其原因。如图,随着递归的深入,计算任务不断地翻倍!

AI产品经理必修:揭开算法的面纱(动态规划)

方法二:动态规划

先上代码。看不懂也没关系,看看如果完成这三个目标的就行了。

AI产品经理必修:揭开算法的面纱(动态规划)

目标1,建立状态转移方程(完成)。也就是前面的f(n)= f(n-1)+ f(n- 2)。

目标2,缓存并复用以往结果(完成)。在线性规划解法中,我们 把结果缓存在results列表 ,同时在results[il = rsutsti11 + resultsti 2]中进行了 复用 。这相当于我们只需完成图2中红色部分的计算任务即可,时间复杂度瞬间降为O(n) 。

AI产品经理必修:揭开算法的面纱(动态规划)

目标3,按顺序从小往大算(完成)。 for循环实现了从0到n的顺序求解,让问题按着从小规模往大规模求解的顺序走。

堪称完美!

本文由 @CARRIE 原创发布于人人都是产品经理。未经许可,禁止转载

题图来自Unsplash,基于CC0协议


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

PERL學習手札.

PERL學習手札.

簡信昌 / 上奇科技 / 20040816 / NT$ 390

1. 關於Perl 當你翻開這本書的時候,你也就進入了一個奇幻的世界。Perl確實是一種非常吸引人的程式語言,而之所以這麼引人入勝的原因不單單在於他的功能,也在於他寫作的方式,或說成為一種程式寫作的藝術。即使你只是每天埋首於程式寫作的程式設計師,也不再讓生活過份單調,至少你可以嘗試在程式碼中多一些變化。而且許多Perl的程式設計師已經這麼作了,這也是Perl的理念-「There is mor......一起来看看 《PERL學習手札.》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

html转js在线工具
html转js在线工具

html转js在线工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换