White's Studio.

Algorithm Dynamic Programming

Algorithm
2018/11/03 Share

动态规划

定义：

​ 简单来说动态规划是用来解决算法性能问题。

​ 然而，能用动态规划的算法是很有局限的，动态规划能解决 最优子结构 问题， 其他类似的问题需要自己去归纳。 最优子结构问题 是指那种局部最优能够决定全局最优解的问题。简单来说，就是问题能够分解问子问题解决。

​ 最优子结构问题，优点是写法清晰简单；但通常都会有一个通病，就是会重复解决同样的子问题，重复解决子问题就会带来巨大的开销。

​

​ 一个简单的例子就是斐波那契数列的递归算法：

1
2
3
4
5
6
7
8
public class Fibonacci {
  public Fibonacci(int N) {
    if (N <= 1)
      return 1;
    else
      return fibonacci(N - 2) + fibonacci(N - 1);
  }
}

​ 事实上这样的写法，N 越来越大时，由于每次都要重新冲N =1 开始计算，时间是指数倍增长。 

而动态规划，就能解决这个问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 动态规划
public class Fibonacci {
  public Fibonacci(int N) {
    int i;
    int lastNum, resultNum, lastLastNume;
    lastNum = resultNum = lastLastNume = 1;
    for (i = 2; i <= N; i++) {
      resultNum = lastNum + lastLastNume;
      lastLastNume = lastNum;
      lastNum = resultNum;
    }
    return resultNum;
  }
}

​ 我们每次计算会记录上一次计算结果，以便这个已计算过的树不用重复计算。

​ 上述例子是用一个 int 变量保存上一次计算结果，动态规划也常用数组，矩阵，树等结构保存中途的计算结果。 

以下来看“矩阵乘法的最优安排”这个例题。 


题目：

​ 给定n个矩阵：A1,A2,…,An，其中Ai与Ai+1是可乘的，i=1，2…，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。

​

​ 要解决这个题目，我们需要掌握几个知识点。

​ 矩阵乘法：

​ 前提：矩阵乘法必须满足 矩阵 A 的宽 = 被乘矩阵 B 的长

​ 定理1：设矩阵 A 为 x* y (长* 宽/ 行数 * 列数)， B 为 y * z，A*B = C 矩阵等于 x* z，

​ 定理2：乘法相乘次数 = x y z 

由此可知，矩阵的乘法是不满足交互律的，(AB)C !== A(BC)，所以才会有最少相乘次数。



根据题目入手，相邻的矩阵必须会满足矩阵乘法的规则，相邻的矩阵相乘后，附近矩阵必须会与新矩阵相邻，满足“前提”，而解题的方法就是在于不断组合尝试相邻矩阵的，计算每次组合的乘法次数。

​ 就以矩阵 A1, A2, A3 为例，

​ 设 m(1,2)为A1*A2的相乘次数，m(3,3)为A3的相乘次数，

​ 而(A1A2 ) A3 的相乘次数= A1的长 A3的长 * A3的宽

​ 这里我们直接定义一个数组c 代表矩阵的宽（列数）， A1的宽 = c1， A2的宽 = c2 …….

​ 且这里有个关系： c1等于A2的长（行数）， A1的长用 c0表示

​ 所以 ：(A1A2 ) A3 的相乘次数 = c0 c2* c3

​ (A1A2 ) A3 的相乘总次数 = m(1,2) + m(3,3) + c0 c2* c3 

这里的m(3,3) = 0 , 对于m(k,k)  来说，都是0。

​ 因此我们可以得出一个一般性的结论：

  1. 对于$A_{left} A_{left+1} ….A_{right}​$ 的矩阵乘法，其相乘次数为

  1. 单独的$A_k$乘法次数记为 0：

算法上也很好实现 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
   *
   * @param p 列数的数组
   * @param i 相乘的开始
   * @param j 相乘的结尾
   * @return
   */
  public static int MatrixChainOrder(int p[], int i, int j) {
    if (i == j)
      return 0;
    int min = Integer.MAX_VALUE;
    for (int k = i; k < j; k++) {
      int temp = MatrixChainOrder(p, i, k) + MatrixChainOrder(p, k+1, j) + p[i-1] * p[k] * p[j];
      if (temp < min) {
        min = temp;
      }
    }
    return min;
  }

​ 但是这样就会有和上面斐波那契数列递归实现的同样问题，

​ 且其结构跟斐波那契数列的递归实现是很像的，我们可以判断其实最优子结构问题，所以尝试用动态规划来解决这个问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
  public static int MatrixChainOrder(int p[], int n)
  {
      /* For simplicity of the program, one extra row and one
      extra column are allocated in m[][].  0th row and 0th
      column of m[][] are not used */
      int m[][] = new int[n][n];

      int i, j, k, L, q;

      /* m[i,j] = Minimum number of scalar multiplications needed
      to compute the matrix A[i]A[i+1]...A[j] = A[i..j] where
      dimension of A[i] is p[i-1] x p[i] */

      // cost is zero when multiplying one matrix.
      for (i = 1; i < n; i++)
          m[i][i] = 0;

      // L is chain length.
      for (L=2; L<n; L++)
      {
          for (i=1; i<n-L+1; i++)
          {
              j = i+L-1;
              if(j == n) continue;
              m[i][j] = Integer.MAX_VALUE;
              for (k=i; k<=j-1; k++)
              {
                  // q = cost/scalar multiplications
                  q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                  if (q < m[i][j])
                      m[i][j] = q;
              }
          }
      }

      return m[1][n-1];
  }

总结

​ 动态规划，主要是解决递归算法的性能问题。

它将问题重新组合成子问题。为了避免多次解决这些子问题（带来巨大的时间复杂度开销），它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，不会在解决同样的问题时花费时间。  

 动态规划只能解决 最优子结构 问题。最优子结构 问题是指 局部最优 能决定全局最优解。简单来说就是问题能被分解成子问题解决。

参考资料

https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/https://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html

完）

原文作者: White

原文链接: http://yuchenzhen.github.io/2018/11/03/Algorithm-Dynamic-Programming/

发表日期: November 3rd 2018, 5:43:39

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 动态规划
    1. 1.1. 定义：
Total : 31
2019
2018
Java Binary_Tree Python Node.js RPC git List Leetcode Leedcode LeetCode LintCode Node.js dubbo electron Java Spring-boot hexo 脑洞题 消息队列 Leetcode Java 数据结构，二叉树 Algorithm