动态规划算法

0、 动态规划的思想方法

最优性原理

对于一个具有n个输入的最优化问题，其求解过程往往可以划分为若干个阶段，每一阶段的决策依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据。从而，一个决策序列在不断变化的状态中产生。这个决策序列产生的过程称为多阶段决策过程。

算法总体思想

• 动态规划算法与分治法类似，是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

• 如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

1、动态规划法的设计思想

• 斐波那契数

n=5时分治法计算斐波那契数的过程。

2、动态规划基本步骤

• 找出最优解的性质，并刻划其结构特征。
• 递归地定义最优值。
• 以自底向上的方式计算出最优值。
• 根据计算最优值时得到的信息，构造最优解。

3、动态规划算法设计步骤

• 划分子问题

用参数表达子问题的边界，将问题求解转 变成多步判断的过程.

• 确定优化函数

以该函数的极大(或极小)作为判断的依据，确定是否满足优化原则.

• 列出关于优化函数的递推方程 (或不等式)和边界条件

• 考虑是否需要设立标记函数

• 自底向上计算，以备忘录方法 (表格)存储中间结果

下文以矩阵连乘举例

3.1 动态规划算法的基本要素

最优子结构

• 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。

• 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。

• 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

使用动态规划技术的条件:优化原则

• 优化原则：

一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优的决策序列

反例： 求总长模10的最小路径

重叠子问题

• 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。

• 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。

• 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。

代码：非递归实现

public static void matrixChain(int [] p, int [][] m, int [][] s)
   {
      int n=p.length-1;
      for (int i = 1; i <= n; i++) m[i][i] = 0;
      for (int r = 2; r <= n; r++)     // r为计算的矩阵链长度 
         for (int i = 1; i <= n - r+1; i++) {      //n-r+1为左边界
            int j=i+r-1;             // 右边界j 
            m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];      // Ai(Ai+1..Aj) 
            s[i][j] = i; //记录分割位置
            for (int k = i+1; k < j; k++) {
               int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; //(Ai..Ak)(Ak+1..Aj)
               if (t < m[i][j]) {
                 m[i][j] = t;
                 s[i][j] = k;}
               }
            }
   }

算法复杂度分析：

算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n³)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n²)。

代码:递归实现

// 子问题ij
public static int RecurMatrixChain(int i, int j) {
        if(i==j) return 0;
        int u = RecurMatrixChain(i+1,j) +p[i-1]*p[i]*p[j];//
        s[i][j] = i;
        // k划分
        for(int k=i+1; k<j; k++){
            // 递归地找最优的次数
            int t = RecurMatrixChain(i, k) + RecurMatrixChain(k+1, j) + p[i-1]*p[k]*p[j];
            if(t < u){
                u = t;
                // 找到更好的解
                s[i][j] = k;
            }
        }
        return u;
    }

复杂性分析

• 递归实现的复杂性

复杂性高的原因：子问题重复计算

• 计算最优值

对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有

由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。

用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法

4、两种实现的比较

• 递归算法：时间复杂性高，空间较小
• 非递归算法：时间复杂性较低，空间消耗多

时间复杂性不同的原因：

• 递归动态规划算法的子问题被多次重复计算子问题计算次数呈指数增长
• 非递归动态规划算法每个子问题只计算一次子问题的计算随问题规模成多项式增长

5、备忘录方法

备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。

代码如下：

m<--0 //表示子问题还未被计算
private static int lookupChain(int i, int j)
   {
      if (m[i][j] > 0) return m[i][j];
      if (i == j) return 0;
      int u = lookupChain(i+1,j) + p[i-1]*p[i]*p[j];
      s[i][j] = i;
      for (int k = i+1; k < j; k++) {
        int t = lookupChain(i,k) + lookupChain(k+1,j) + p[i-1]*p[k]*p[j];
        if (t < u) {
          u = t; s[i][j] = k;}
        }
      m[i][j] = u;
      return u;
   }

6、备忘录方法与动态规划比较

• 动态规划是自底向上 ，备忘录方法是自顶向下，递归是自顶向下的。

• 动态规划每个子问题都要解一次，但不会求解重复子问题；备忘录方法只解哪些确实需要解的子问题；递归方法每个子问题都要解一次，包括重复子问题。

7、参考

• 算法设计与分析（第4版）

结束！