动态规划

History does not occur again

算法总体思想

• 与分治算法类似

• 子问题往往不是互相独立的, （分治会重复计算）

• 保存已解决的子问题的答案，需要时找出即可（空间换时间）

基本步骤

• 找出最优解的性质并刻划其结构特征

• 递归地定义最优值

• 以自底向上的方式计算出最优值（递推）

• 根据计算最优值时得到的信息构造最优解

矩阵连乘问题

问题描述

• 给定 n 个矩阵{A₁, A₂,..., A_n}, 其中 A_i 与 A_i+1 是可乘的, i = 1, 2, ..., n-1

• 如何确定连乘积的计算次序，使得依次次序计算矩阵连乘积所需要的数乘次数最少

分析

• 矩阵乘法满足结合律->矩阵乘法可以有不同的计算次序

• 矩阵连乘的计算次序可以用加括号的方式来确定->若矩阵连乘已完全加括号，则其计算次序完全确定

• 完全加括号的矩阵连乘可递归定义为：

• 单个矩阵是完全加括号的；

• 矩阵连乘积 A 是完全加括号的，则 A 可表示为 2 个完全加括号的矩阵连乘积 B 和 C 的乘积并加括号，即 A=(BC)。

例，有四个矩阵 A,B,C,D，它们的维数分别是： A=50×10，B=10×40, C=40×30, D=30×5 连乘积 ABCD 共有五种完全加括号的方式

(A((BC)D)) 16000      (A(B(CD))) 10500((AB)(CD)) 36000      (((AB)C)D) 87500((A(BC))D) 34500

解决方法

• 穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找到一种数乘次数最少的计算次序。

• 复杂性分析： 用 p(n)表示 n 个矩阵链乘的穷举法计算成本，如果将 n 个矩阵从第 k 和 k+1 出隔开，对两个子序列再分别加扩号，则可以得到下面递归式：

• 
  
  

• 很明显，指数级增长，此方法不太可行

• 动态规划

• 将矩阵连乘积 A_iA_i+1…A_j简记为 A[i:j] ，这里 i≤j。考察计算 A[i:j]的最优计算次序。设这个计算次序在矩阵 A_k和 A_k+1之间将矩阵链断开，i≤k<j，则其相应完全加括号方式为(A_iA_i+1…A_k)(A_k+1A_k+2…A_j)-> A[i:j]的计算量：A[i:k]的计算量加上 A[k+1:j]的计算量，再加上 A[i:k]和 A[k+1:j]相乘的计算量

具体步骤

• 分析最优解的结构

• 特征：计算 A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和 A[k+1:j]的次序也是最优的

• 
  
  

• 建立递归关系

• 设计算 A[i:j]，1≤i≤j≤n，所需要的最少数乘次数 m[i,j]，则原问题的最优值为 m[1,n]

• 
  
  

• k 为断开位置

  m[i][j]实际是子问题最优解的解值，保存下来避免重复计算

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

• 计算最优值

• 根据递归公式，对角线的值为 0。其他值需要根据于断开位置 k 的值来得到，k $\in$ [i,j)，我们要遍历所有 k，就要访问所求值的所有同一行左边的值和同一列下方的值。因此，在代码中我们可以使用自底向上、从左到右的计算顺序来依次填充，最终得到右上角的值。

• 构造最优解

• 前面我们已经讲数据记录在了数组中，直接查表即可构造最优解

案例

• 求矩阵链 A₁A₂A₃A₄的最优运算次序。其中矩阵 A_i的大小为 p_i-1×p_i。其中 P(0) = 5，P(1) = 7，P(2) = 4，P(3) = 3，P(4) = 5

Java 代码实现

package MatrixChain;
public class Array {    /**   * 求解最优值   * @param p: 矩阵维数信息数组   * @param m: 存放最优值数组, 上三角形式   * @param s: 存放分割位置下标的数组   * @return 返回最优值   **/  public static int matrixChain(int[] p, int[][] m, int[][] s) {    int n = p.length - 1;    for (int i = 1; i <= n; i++)      // 本身为0      m[i][i] = 0;  // 初始化二维数组    for (int r = 2; r <= n; r++) {      for (int i = 1; i <= n - r + 1; i++) {         int j = i + r - 1;        // 先以i进行划分        m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];  // 求出Ai到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];  // 公式          if (t < m[i][j]) {            m[i][j] = t;            s[i][j] = k;          }        }      }    }    return m[1][n];  }    /**   * 输出 A[i:j] 的最优计算次序   * @param i、j: 连乘矩阵下标   * @param s: 存放分割位置下标的数组   **/  public static void traceback(int i, int j, int[][] s) {    // 输出A[i:j] 的最优计算次序    if (i == j) {      // 递归出口      System.out.print("A"+i);      return;    } else {      System.out.print("(");      // 递归输出左边      traceback(i, s[i][j], s);      // 递归输出右边      traceback(s[i][j] + 1, j, s);      System.out.print(")");    }  }    public static void main(String[] args) {    int[] p = new int[]{5, 7, 4, 3, 5};    int[][] m = new int[p.length][p.length];    int[][] s = new int[p.length][p.length];    System.out.println("最优值为： "+matrixChain(p, m, s));    traceback(1, p.length-1, s);  }}

最优值为： 264((A1(A2A3))A4)