分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net
动态规划（Dynamic Programming，DP）是将多阶段决策问题进行公式化的一种技术，是算法设计方法之一。
动态规划的原理
动态规划是一种解决多阶段决策问题的优化方法，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系逐个求解。
动态规划求解的基本步骤
采用动态规划求解的问题一般要具有以下3个性质：
（1）最优性原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优性原理。
（2）无后效性：即某个阶段的状态一旦确定，就不受这个状态以后决策的影响。也就是说，某个状态以后的过程不会影响以前的状态，只与当前状态有关。
（3）有重叠于问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用。
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的活动路线。
动态规划的设计都有着一定的模式，一般要经历以下几个步骤：
（1）划分阶段：按照问题的时间或空间特征把问题划分为若干个阶段。在划分阶段时注意划分后的阶段一定是有序的或者是可排序的，否则问题无法求解。
（2）确定状态和状态变量：将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
（3）确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来推导出本阶段的状态。所以如果确定了决策，状态转移方程也就可以写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策和状态转移方程。
（4）寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。一般情况下只要解决问题的阶段、状态和确定状态转移决策，就可以写出状态转移方程（包括边界条件）。
在实际应用中可以按以下几个简化的步骤进行设计：
（1）分析最优解的性质，并刻画其结构特征。
（2）递归地定义最优解。
（3）以自底向上或自顶向下的记忆化方式计算出最优值。
（4）根据计算最优值时得到的信息构造问题的最优解。
注意：动态规划是一种求解思路，注重决策过程，不同的问题得到的模型可能不一样，关键是掌握其原理，利用递推关系求最优解。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/232276.html原文链接：https://javaforall.net
