分享近期学习的内容:动态规划法
动态规划法 明确求最优解(一)概念
动态规划法用于求解具有最优子结构的多阶段决策活动的最优解,将原问题分解成若干子问题,列出并保存各种可能的子问题解,找到子问题的最优解,从而构造原问题的最优解。
必须含有的要素:
①最优子结构 :原问题的最优解所包含的子问题的解也是最优的,利用已解决过的子问题的最优解来求解原问题的最优解,可使用 ②递归 或循环解决问题。
无后效性:过程的发展仅与此阶段的状态有关,与此阶段前的阶段所经历过的状态无关。
多阶段决策活动:
活动的过程可分为若干个互相联系的阶段,在每个阶段都需作出决策(或采取措施),一个阶段的决策会影响下一阶段的决策,从而完全确定了一个活动的过程的路线。
各阶段采取的决策依赖于当前状态,又引起状态的转移。
各阶段的决策构成一个决策序列,称为一个策略。每个阶段都有若干个决策可供选择,因而有许多策略供选取。每个策略都可用数量衡量活动效果,策略不同效果不同。
将原问题分解成若干子问题的过程自顶向下与自底向上相同,该过程与分治法非常相似。
每次问题分解产生的子问题并不总是新问题,有些子问题会被重复计算多次,动态规划法将 ③子问题的解记录在表格中 ,每个子问题的解先在表中查找结果,节省大量的重复计算时间。
(二)时间复杂度
1.自顶向下O(2^n)
动态规划法自顶向下实现时,
规模从n到n-1时,表中没有n-1的解,查表的意义可以忽略不计,因此要继续向下递归,递归到第1层(或第0层)时才有解。
设每次分解为2个子问题,解空间形成一个二叉树,n为二叉树的深度,二叉树的每个结点都是一个子问题,都要计算(或查表)1次,共O(2^n)。
2.自底向上O(n^a)
动态规划法自底向上实现时,
第1层(或第0层)有解,中间解查表或计算可得。
设每次分解为2个子问题,解空间形成一个二叉树,n为二叉树的叶结点数量,a为二叉树的深度,自底向上合并解空间,每层执行n次循环,循环嵌套a层,时间复杂度O(n^a)。
以上是学习内容,如有错误或不足,望指正。 有一个问题想请教一下前辈,其实好像很多时候我都理解动态规划的含义,但是就是在做题或者实际应用的时候想不起如何使用,或者是想不到这样的递推式。
比如说上点难度的正则表达式,就好像很难定义动规数组到底是几个维度比较合适,递推关系怎么做。
楼主有这类的经验吗?
感觉很像那种,只会做过的、看明白解析的题。 客气了,我前天才刚学,称不上前辈,分享下心得而已混个发贴数。目前还未学到过这方面。
页:
[1]