admin 管理员组文章数量: 893698
【动态规划的方法论】
Dynamic Program
动态规划(dynamic programming)与分治法相似,都是通过子问题的解来求解原问题。 但是分治是将原问题划分为不同的子问题,再将他们组合,从而求出原问题的解。但是动态规划是子问题会重叠,也就是说不同的子问题会有相同的子子问题。在这个情况下,如果用分治会做很多无用功,而动态规划就是每个子问题只求解一次,避免了重复求解。
动态规划通常用来求解最优化问题(optimization problem)。这类问题可能会有很多可行的解,但是我们往往只需要知道最优解的值是多少,不关心他是如何组织的,即每一步是什么,或者我们只需要得到一个解即可。the optimal solution
应用动态规划求解要满足两个要素:
-
最优子结构(optimal substructure): 也就是说,原问题的最优解可以由子问题的最优解得到。所谓的 “剪切-粘贴” 方法,其实就是 反证法。如果子问题的次优解是原问题的最优解中的内容,那么将子问题的最优解代替子问题的次优解,我们将得到一个更优的全局解,所以子问题的最优解将是原问题最优解的组成内容。
-
重叠子问题: 即子问题有相同的子子问题。有了最优子结构之后,它与分治的区别是要有重叠子问题,使用递归自上而下计算会导致有些子问题被重复计算,通常来说,这样的子问题是很多的,而且会被重复计算很多次,这样才需要动态规划去避免一个子问题的重复求解。
由这两个条件可以看出,当我们解决一个问题时,看是否能用动态规划解决就是看满不满足这两个条件,如果满足,一般解题时就可以多往动态规划上靠靠了。但是这两个条件有时不是这么容易看出来的,所以需要多做相关联系,见识哪些情况用动态规划的可能性大一些,这样就可以从用动态规划解题去反推如何才能满足这两个条件了。动态规划,我认为最难的就是定义状态和状态转移 ,只要这两个工作做好了,下面的编码以及避免重复求解就简单了。
动态规划算法利用了以上两个性质,将重叠的子问题只求解一次,存入表中,之后再遇到相同的子问题只需要查表即可。记忆化搜索,这就是为什么DP必须满足重叠子问题的原因。
四个步骤来设计一个动态规划算法:
- 刻画一个最优解的结构,定义状态,初始条件与边界。
- 递归的定义最优解的值,状态转移。
- 计算最优解的值,通常采用自底向上的算法,避免重复求解。
- 利用计算的信息构造出一个最优解。
动态规划两种等价实现方法:
-
带备忘录的自顶向下法(top-down with memorization):原本解决满足上面两条性质的问题,使用递归的方法,但是递归树中有很多重复的子问题,我们重复求解了这些子问题,所以导致复杂度为 O ( 2 n ) O(2^n) O(2n),在带备忘录的自顶向下方法中,我们仍然是递归计算,不过我们每计算出一个子问题的解就保存下来,之后再遇到相同的子问题,就可以直接返回已经算好的值了,不需要重复计算。
-
自底向上法(bottom-up method):递归的方法是原问题调用子问题的解,构造原问题的最优解,而此时子问题的最优解尚未得到,所以要继续得到子问题的最优解。自底向上的办法就是先计算最小子问题的解,然后一步步构造更大子问题的最优解,最后得到原问题的最优解,此时所有子问题的最优解都已经计算完毕。
以上两种方法具有相同的渐进运行时间,带备忘录的方法可能会没有真正计算所有子问题,但是他有函数调用的开销;自底向上的方法会计算所有的子问题,但是没有函数调用的开销,一般来说,自底向上的方法有着更小的系数。
一个刻画问题空间的好经验是:保持子问题空间的尽可能简单,只在必要时才扩展它。
动态规划和贪心的区别
-
动态规划先求子问题的最优解,然后构造原问题的最优解。贪心是直接求解原问题的最优解。
-
动态规划通过比较若干局部最优解,去掉次优解,得到更高一级的局部最优解,从而一步步构造出原问题的最优解。贪心是每次只做一个选择,一旦选择便不再改变,后阶段的最优解是基于前一阶段的最优解,所以往往只能得到次优解。
贪心其实可以看成动态规划的两个子问题中,一个子问题的最优解已经很明确了,剩下其实只要解决一个子问题即可,那个已经很明确的子问题我们可直接加入答案。
动态规划是一个很有意思的算法思想,它的状态定义和状态转移有时真的非常巧妙,虽然做不出来,看到答案时,也会直呼内行。我现在也还是不大会做DP的题,不过我现在都是按照上面那四步去套,比起以往完全没头绪,还是好很多,只是后面写出来的代码不够简洁,所以学动态规划要自己想,要多看解答,这样才能更好的培养意识。加油吧!
注:上述内容为《算法导论》第三版相关内容总结,感兴趣的同学可以去看书哦!
本文标签: 动态规划的方法论
版权声明:本文标题:【动态规划的方法论】 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.freenas.com.cn/jishu/1687605002h120229.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论