页面树结构

2017-11-09 ApacheCN 开源组织,第二期邀请成员活动,一起走的更远 : http://www.apachecn.org/member/209.html


MachineLearning 优酷地址 : http://i.youku.com/apachecn

转至元数据结尾
转至元数据起始

猿爸爸把 1+1+1+1+1+1+1+1 = 写在纸上,问小猿(咦):

「它们加起来是多少哇?」

(数了一会…)「8 !」

猿爸爸在左边又加了个 1+,再问一次小猿:
「现在呢?」

(迅速地)「9 !」

「为什么小猿这么快就知道了呢?」

「因为你刚刚加了 1 啊~」

「所以只要记得之前的结果,就不用再计一次数啦。」

嗯,动态规划就是一种「先记住些事,方便后面节约时间」的神奇方法。


--------------------------------------------------------------------------
但是如果你觉得这个答案对你的胃口,那么恭喜你,你对 DP 的理解成功地达到了四岁小孩的水平……FYI:   How should I explain dynamic programming to a 4-year-old?


搞过ACM的水货答一下。 <http://www.zhihu.com/question/23995189/answer/35392247>
排名第一的答案本身已足够好了,但还是太过专业,不能传教于大众,故试着来个通俗的答案。
首先,动态规划是一种算法。那么,何谓算法?计算机书籍中不难找到其严谨的学术定义,大众可以简单理解为“解决某一类问题的核心思想”。

先谈动态规划的意义——望文生义,“动态”规划对应“动态”的问题:你并不知道问题的规模会有多大,而不论是个位数还是百万级,都能以较快速度(动态规划是一种泛用性算法,而泛用性算法与特定算法相比往往存在性能差距)将结果正确计算出来。这是对于计算机科学最直观的意义,当然我认为其对人生亦有一定指导意义,但那是见仁见智的事了。
动态规划这一思想的实质其实是以下两点:
1.分析问题,构造状态转移方程
2.以空间换时间

让我们结合一个简单例子来理解一下:
以乘法计算为例,乘法的定义其实是做n次加法,请先忘掉九九乘法表,让你计算9*9,如何得到81这个解?计算9*10呢?9*999……以及9*n呢?
1.分析问题,构造状态转移方程
“状态转移方程”的学术定义亦可简单找到(比如置顶答案),略去不表。光看“方程”二字,可以明白它是一个式子。
针对以上问题,我们构造它的状态转移方程。
问题规模小的时候,我们可以容易得到以下式子:

9*0=09*1=0+99*2=0+9+9;
……
可以得到:9*n=0+9+...+9(总共加了n个9)。严谨的证明可以使用数学归纳法,略去不表。
现在,定义dp(n)=9*n,改写以上式子:

dp(0)=9*0=0;
dp(1)=9*1=dp(0)+9;
dp(2)=9*2=dp(1)+9;
……
作差易得:dp(n)=dp(n-1)+9;这就是状态转移方程了。
可以看到,有了状态转移方程,我们现在可以顺利求解9*n(n为任意正整数)这一问题。

2.以空间换时间
虽然能解,但当n很大时,计算耗时过大,看不出状态转移方程dp(n)=dp(n-1)+9与普通方程9*n=0+9+...+9(总共加了n个9)相比没有任何优势。
这时,如果dp(n-1)的结果已知,dp(n)=dp(n-1)+9只需计算一次加法,而9*n=0+9+...+9(总共加了n个9)则需计算n-1次加法,效率差异一望即知。
存储计算结果,可令状态转移方程加速,而对普通方程没有意义。
以空间换时间,是令动态规划具有实用价值的必备举措。

 

动态编程在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态编程保存递归时的结果,因而不会在解决同样的问题时花费时间。一般地,动态编程可以将算法复杂度降为O(n)。

 

       动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。
       多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这种解决多阶段决策最优化问题的方法为动态规划方法。
  • 无标签