《算法导论》学习总结 — 18.第15章 动态规划(3) 基础入门2

建议先看看前言:http://www.wutianqi.com/?p=2298

这一节可以看到《算法导论》学习总结 — 16.第15章 动态规划(1) 基本入门的补充。

采用动态规划的最优化问题的两个要素:最优子结构重叠子问题

先看看最优子结构:

在第17篇总结时,装配线调度问题中,已经设计到了最优子结构,证明最优子结构问题可以用书上说的“剪贴技术”,即假设存在更优的解,来反正最优解矛盾。

再看看重叠子问题:

当一个递归算法不断的调用同一个问题时,我们说该最有问题包含“重叠子问题”。

上面这句话不好理解?

看看下面这个比较:

递归算法:自顶而下,对在递归树中重复出现的每个子问题都要重复解一次。

动态规划:自下而上,对每个只解一次。

结合第16篇总结的三角形求值例子,可以看得到,自下而上导致每个子问题只求解一次。

 

以上理论性有点强,我最开始学DP看的是HDOJ的课件,有兴趣的可以去看看。

在那里面,主要讲到了是找状态转移方程,在第16篇的三角形求值例子和第17篇的装配线调度例子,那些递归公式都是状态转移方程。

下面这段话好好理解:

——————————————————————–

动态规划的几个概念:
阶段:据空间顺序或时间顺序对问题的求解划分阶段。
状态:描述事物的性质,不同事物有不同的性质,因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。
决策:根据题意要求,对每个阶段所做出的某种选择性操作。
状态转移方程:用数学公式描述与阶段相关的状态间的演变规律。

动态规划是运筹学的一个重要分支,是解决多阶段决策过程最优化的一种方法。

所谓多阶段决策过程,是将所研究的过程划分为若干个相互联系的阶段,在求解时,对每一个阶段都要做出决策,前一个决策确定以后,常常会影响下一个阶段的决策。

动态规划所依据的是“最优性原理”。
“最优性原理”可陈述为:不论初始状态和第一步决策是什么,余下的决策相对于前一次决策所产生的新状态,构成一个最优决策序列。

最优决策序列的子序列,一定是局部最优决策子序列。
包含有非局部最优的决策子序列,一定不是最优决策序列。

动态规划的指导思想是:

在做每一步决策时,列出各种可能的局部解,之后依据某种判定条件,舍弃那些肯定不能得到最优解的局部解。这样,在每一步都经过筛选,以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝(从搜索角度看),效率会十分高。但它又不同于贪心法。贪心法只能做到局部最优,不能保证全局最优,因为有些问题不符合最优性原理。

——————————————————————–

 

看见有人说递归就是DFS,而DP就是BFS,感觉有那么一点意思,对于DP,就是从底层一层层的计算,然后在当层中选取最优,逐层最优以至总体最优。

 

其实这个还是多做一些题就好了(⊙o⊙),大家别认为我是做题控,其实说实在话,看N遍不如做一题,说白了,算法数学本一家,算法就是数学,走过高中的,都知道数学题得多做,尤其压轴题,看N遍不如做一遍,这个也是一样做几题就知道DP是神马东东了!

 

Tanky Woo 标签:

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《《算法导论》学习总结 — 18.第15章 动态规划(3) 基础入门2》有168个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注