YI时间｜外刊｜MM-DFW｜机器学习系列
点击上方蓝字，关注给你写干货的松子茶
动态规划的概述
动态规划(Dynamic Programming), 在20世纪50年代由美国数学家Richard Bellman提出，作为多阶段决策过程最优化的一种通用算法设计之一，不仅解决特定类型的最优化问题，也包括某些非最优化问题。多阶段决策过程最优化诸多实际问题：有多个解，但要找到最优解。
动态规划算法步骤
设计一个动态规划算法，通常可以按以下几个步骤进行：
- 刻画最优解的结构特性；
- 递归定义最优解值；
- 以自底向上方式计算最优解值；
- 根据计算得到的信息构造一个最优解。
其中，第1至2步是动态规划算法的基本步骤。最优解值是最优解的目标函数的值。
动态规划算法的基本步骤
- 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。
- 选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。
- 确定决策并写出状态转移方程：状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。
- 写出规划方程(包括边界条件)：动态规划的基本方程是规划方程的通用形式化表达式。
动态规划的设计要素
-
最优化原理Principle of Optimality(最优子结构特性)指出：一个最优策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，其余决策必定构成最优策略。这便是最优决策序列的最优子结构特性。
无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。原理告诉我们，一个最优问题的任何实例的最优解是由该实例的子实例的最优解组成的。
一般来说，如果所求解问题对于最优性原理成立，则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获取各阶段间的递推关系式。
- 无后向性: 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
- 重叠子问题: 动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法,其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性。这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。
动态规划的实质是分治策略和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
动态规划求解问题的步骤
- 划分子问题：用参数表达子问题的边界，将问题求解转变成多步判断的过程。
- 确定优化函数：以该函数的极大(或极小)作为判断的依据，确定是否满足优化原则。
- 列出关于优化函数的递推方程(或不等式)和边界条件。
- 考虑是否需要设立标记函数。
- 自底向上计算，以备忘录方法(表格)存储中间结果。
动态规划算法的典型应用
- 投资问题
- 背包问题
- 最长公共子序列LCS
- 图像压缩
- 最大子段和
- 最优二分检索树
- 每对结点之间的最短路径(Warshall和Floyd算法)
- ……
欢迎评论哦，纠错评论建议均可
-THE END-
版权声明：以上内容为松子茶公众号原创作品，版权归属作者所有。未经作者授权，严禁转载或镜像，否则将依法追究相关行为主体的法律责任。欢迎各位朋友转发朋友圈分享。