转载

矩阵连乘-动态规划-详解

动态规划法

以矩阵链ABCD为例
按照矩阵链长度递增计算最优值
矩阵链长度为1时，分别计算出矩阵链A、B、C、D的最优值
矩阵链长度为2时，分别计算出矩阵链AB、BC、CD的最优值
矩阵链长度为3时，分别计算出矩阵链ABC、BCD的最优值
矩阵链长度为4时，计算出矩阵链ABCD的最优值

给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

解答:我们按照动态规划的几个步骤来分析：

(1)找出最优解的性质，刻画其特征结构

对于矩阵连乘问题，最优解就是找到一种计算顺序，使得计算次数最少。

令m[i][j]表示第i个矩阵至第j个矩阵这段的最优解。

将矩阵连乘积简记为A[i:j] ，这里i<=j.假设这个最优解在第k处断开，i<=k<j，则A[i:j]是最优的，那么A[i,k]和A[k+1:j]也是相应矩阵连乘的最优解。可以用反证法证明之。这就是最优子结构，也是用动态规划法解题的重要特征之一。

(2)建立递归关系

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

当i=j时，A[i,j]=Ai, m[i,j]=0;(表示只有一个矩阵,如A1,没有和其他矩阵相乘,故乘的次数为0)  当i<j时，m[i,j]=min{m[i,k]+m[k+1,j] +pi-1*pk*pj} ,其中 i<=k<j

(相当于对i~j这段,把它分成2段,看哪种分法乘的次数最少,如A1,A2,A3,A4,则有3种分法:{A1}{A2A3A4 }、{A1A2}{A3A4 }、{A1A2A3}{A4 },其中{}表示其内部是最优解,如{A1A2A3}表示是A1A2A3的最优解),

也即：

矩阵连乘-动态规划-详解

(3)计算最优值

对于1≤i≤j≤n不同的有序对(i,j) 对于不同的子问题，因此不同子问题的个数最多只有o(n*n).但是若采用递归求解的话，许多子问题将被重复求解，所以子问题被重复求解，这也是适合用动态规划法解题的主要特征之一。

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

下面给出动态规划求解最优值的代码：

//也是要枚举求到的，但是如果我们之前先记录下这些小规模的情况，当求大规模的时候，直接提取就行了，因此体现了记忆搜索的说法  void MatrixChain(int *p,int n,int **m,int **s)  {    //m是最优值,s是最优值的断开点的索引,n为题目所给的矩阵的个数(下面例子中)  //矩阵段长度为1,则m[][]中对角线的值为0,表示只有一个矩阵,没有相乘的.  for(int i = 1;i<=n;i++) m[i][i] = 0;           //本题中n=6               for(int r = 2;r<=n;r++){//r表示矩阵的长度(2,3…逐渐变长)     for(int i = 1;i<=n-r+1;i++){      //从第i个矩阵Ai开始,长度为r,则矩阵段为(Ai~Aj)  int j = i+r-1;//当前矩阵段(Ai~Aj)的起始为Ai,尾为Aj  //求(Ai~Aj)中最小的,其实k应该从i开始，但先记录第一个值，k从i+1开始，这样也可以。  //例如对(A2~A4),则i=2,j=4,下面一行的m[2][4]=m[3][4]+p[1]*p[2]*p[4],即A2(A3A4)       m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];       s[i][j] = i;//记录断开点的索引  //循环求出(Ai~Aj)中的最小数乘次数       for(int k = i+1 ; k<j;k++){  //将矩阵段(Ai~Aj)分成左右2部分(左m[i][k],右m[k+1][j]), //再加上左右2部分最后相乘的次数(p[i-1] *p[k]*p[j])         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;  //保存最小的,即最优的结果  }//if       }//k      }//i  }//r  }//MatrixChain

上面代码中后面的k也相当于是从i到j-1递增的,只是单独把第一个(k=i)提了出来.

对于 p={30 35 155 10 20 25}:

矩阵连乘-动态规划-详解

计算顺序为：

矩阵连乘-动态规划-详解

对上例,共6个矩阵(A1~A6),n=6,当r=3时,r循环里面的是3个矩阵的最优解,i从1->4,即求的是

(A1A2A3),(A2A3A4),(A3A4A5),(A4A5A6)这4个矩阵段(长度为3)的最优解.当i=2时(A2A3A4)的最优解为{A2(A3A4) ,(A2A3)A4}的较小值。

矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。