动态规划的基本原理和递推方程

1. 动态规划的基本原理和递推方程

贝尔曼等所提出的动态规划最优化原理是：“一个过程的最优策略具有这样的性质，即无论初始状态和初始决策如何，从这一决策所导致的新状态开始，以后的一系列决策必须是最优的”。
如前所述，动态规划逆序决策过程中，总是从整个过程的终端开始计算，向始端逐阶段择优，其中每一个阶段都要考虑未来各阶段情况加以比较而选取决策，唯独终端的阶段决策时，只考虑终端这一阶段最有利即可。
同时，根据最优化原理可知，一个n 阶段的决策过程，如果所选取的最优策略，经过第i阶段si状态时，则从si至终点的最优策略，必然是整个最优策略的一部分。这样，就使多阶段决策过程寻找最优策略问题，具有逆推的性质。即求第i阶段至末阶段的最优策略时，可用当前i阶段的一个决策加上剩余阶段相应的最优策略，作为从i阶段至终点的一个比较策略，从中选取最优策略。据此，可建立动态规划的递推方程。
设（si）表示任一状态si开始至终点使用所有决策序列dk所得到的最小费用，则有

华北煤田排水供水环保结合优化管理

若把决策序列分为两部分，即在di上最小化和di+1，di+2，…，dn最小化，则式（3.3.1）可写为

华北煤田排水供水环保结合优化管理

式（3-27）中，第一项仅依赖di而与dk无关（k＞i），因此dk上的最小化对此项没有影响，而第二项si+1与di有关，随系统状态转移方程而定，即

华北煤田排水供水环保结合优化管理

故式（3-27）可写为

华北煤田排水供水环保结合优化管理

因为

华北煤田排水供水环保结合优化管理

将式（3-29）代入式（3-28）可得

华北煤田排水供水环保结合优化管理

式（si）和（si+1）分别代表第i阶段状态为si及第i+1阶段状态为si+1时的最优目标函数值。若阶段变量i=n，n-1，…，1，经历过程所有阶段，式（3-30）就成为一个递推方程，当i=1时，最优目标函数值（s1）也就是全过程最小总费用R*，即

华北煤田排水供水环保结合优化管理

上述递推方程的阶段编码次序和递推次序与实际过程状态转换方向相反，故称为逆序递推；如果阶段编码次序和递推次序与实际过程状态转换方向相一致时，故称为顺序递推。那么，逆序递推的式（3-30）变顺序递推可写为

华北煤田排水供水环保结合优化管理

全过程最优目标函数值为

华北煤田排水供水环保结合优化管理

递推方程计算时，可顺序递推，也可逆序递推。通常，当初始状态已知时，逆序递推较方便，当最终状态已知时，顺序递推较方便。但无论是顺序递推或逆序递推，都要采用前述逆序决策过程——选定系统前进方向后，逆此方向自终点向始点逐阶段寻优，达到整体最优。所以，逆序递推与逆序决策过程是两个不同的概念。

2. 动态规划算法详解

动态规划一般也只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。简单地说，问题能够分解成子问题来解决。
  
 将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解（这部分与分治法相似）。与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。通常可以用一个表来记录所有已解的子问题的答案。
  
 问题的一个最优解中所包含的子问题的解也是最优的。总问题包含很多个子问题，而这些子问题的解也是最优的。
  
 用递归算法对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
  
 ：很显然，这道题的对应的数学表达式是
  
 其中F(1)=1, F(2)=2。很自然的状况是，采用递归函数来求解：
  
 参考：
    http://blog.csdn.net/zmazon/article/details/8247015 
    http://blog.csdn.net/lisonglisonglisong/article/details/41548557 
    http://blog.csdn.net/v_JULY_v/article/details/6110269 
    http://blog.csdn.net/trochiluses/article/details/37966729

3. 动态规划之解题思路

一、定义
  
 动态规划（dynamic programming)简称DP，用于解决重叠子问题。
  
 二、解题步骤
  
 1、确定dp数组以及下标含义
  
 2、确定状态转移方程
  
 3、dp数组的初始化
  
 题目有两种可能，一种是要求背包恰好装满，一种是可以不装满（只要不超过容量就行）。
  
 - 恰好装满。只需要初始化dp[0] 为 0， 其他初始化为负数即可。
  
 - 可以不装满。 只需要全部初始化为 0，即可。
  
 4、确定遍历的顺序
  
 外层遍历物品，还是外层遍历容量；
  
 以及容量从大到小遍历，还是从小到大遍历。
  
 5、举例检验
  
 三、总结
  
 递归和动态规划都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存了子问题的解，避免重复计算。
  
 动态规划内容很多，将从以下方面进行学习：
  
 斐波拉契数列
  
 背包（0-1背包，完全背包）。。。。。
  
 参考资料： github分类详解