vlambda博客
学习文章列表

漫画:5分钟了解什么是动态规划?


作者 | 调皮的阿广

来源 | 视学算法(ID:z872561826)


漫画:5分钟了解什么是动态规划?


漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?


动态规划,英文是Dynamic Programming,简称DP,擅长解决“多阶段决策问题”,利用各个阶段阶段的递推关系,逐个确定每个阶段的最优决策,并最终得到原问题的最优决策。


漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

注意:动态规划往往使用表格来存储中间结果

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

注意:每一步上几层台阶,都是一个决策问题!

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

说到这里,阿广你有没有发现几点问题?


1、将求F(10)这个问题,完美的分解成了F(9)和F(8),找到了局部的最优解,与贪心算法有点像呀。


2、既然F(10)=F(9)+F(8),那么F(9)=F(8)+F(7),依此类推,最终问题被逐渐降低了规模,越来越简单,这也是分治算法的思想。


漫画:5分钟了解什么是动态规划?

动态规划的三要素:


1、最优子问题

F(10)=F(9)+F(8),就是F(10)问题的最优子问题,局部的贪心完美的将问题分解,如果得到的F(9)和F(8)都是最优解,那么F(10)一定也是最优解了。


2、边界条件

分解到最后,一定是变成了规模最简单的问题,即F(1)和F(2),这两个问题不能再分解了,不过没关系,他们很简单,用你的小心心算就ok了。


3、状态转移方程(DP方程)

本问题的状态转移方程为:F(n)=F(n-1)+F(n-2),这就是解决问题的核心,使得状态能够“动”起来。

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

注意:相同颜色的部分代表相同的结果

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

可以看出来,动态规划算法的核心是DP方程。


所以说,状态转换方程(DP方程)就是算法的核心,那么设计DP方程,要有什么注意的呢?以下列出来几点!


1、最优化子问题

从上面的算法三要素中,可以看出,DP方程是最优子问题中归纳而来的。那么,什么才算“最优子问题”呢?就是说,不管之前决策是否是最优决策,都必须保证从现在开始的决策是在之前的基础上最优。具体的说,我们默认F(8)和F(9)就是最优的,在此基础上,得到最优的F(10)。


2、不影响后续决策

由于上一条我们看到,如果F(8)的决策会影响到F(9)和F(10)的决策,那么F(10)=F(9)+F(8)就不成立了,所以,要一定保证,每个阶段的决策仅受之前决策的影响,但不影响之后阶段的决策。


漫画:5分钟了解什么是动态规划?


典型应用1---01背包问题


漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

01背包问题的决策,就是判断第i件物品,装还是不装,哪种决策总价值最大?


那么,我们是否能够定义状态为s[i]呢,用来表示第i件物品决策的最大价值?


答案是不可以的,因为这个状态会影响到后面的决策,换种说法讲,装不装入一个物品,会影响到背包中的剩余空间,所以后面的决策当然会受影响。


漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

典型应用2---最长公共子序列问题(这一问题常被用于比较“相似度”)


漫画:5分钟了解什么是动态规划?

决策方式就是判断str1[i]和str2[j]的关系,关系不同,则DP方程不同。


漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

漫画:5分钟了解什么是动态规划?

原文链接:


(*本文为 AI科技大本营转载文章,转载请联系作者)



福利时刻



入群参与每周抽奖~


扫码添加小助手,回复:大会,加入福利群,参与抽奖送礼!

漫画:5分钟了解什么是动态规划?


AI ProCon 2019 邀请到了亚马逊首席科学家@李沐,在大会的前一天(9.5)亲授「深度学习实训营」 ,通过动手实操,帮助开发者全面了解深度学习的基础知识和开发技巧。还有  9大技术论坛、60+主题分享,百余家企业、千余名开发者共同相约 2019 AI ProCon! 5折优惠票抢购中!       


       


推荐阅读



你点的每个“在看”,我都认真当成了喜欢