动态规划之矩阵链乘法

第一次见到这个算法在某同学的算法作业上 ->_-> 然后在算法导论上见到了这题，于是来划水个水（不是）。题干简化如下：

设A1,A2,…,An为矩阵序列，Ai为Pi-1*Pi阶矩阵，i=1,2,…,n. 确定乘法顺序使得元素相乘的总次数最少。

输入：向量P=<P0,P1,…,Pn>,n个矩阵的行数、列数

例：P=<10,100,5,50>

A1:10 * 100,A2:100 * 5,A3:5 * 50

我们可以通过计算发现，对于任意两个矩阵A，B，A * B的乘法总次数为：

$r . r o w * (b . c o l * a . c o l)$

具体代码原因如下：

//矩阵乘法
//c.data[i][j]=a.data[i][1]*b.data[1][j]+a.data[i][2]*b.data[2][j]+...
for(int i=1;i<=A.row;i++)
{
  for(int j=1;j<=B.col;j++)
  {
    C.data[i][j]=0
      for(int k=1;k<=A.col;k++)
        C.data[i][j]=A.data[i][k]*B.data[k][j];
  }
}

我们可以得到方案的总可能数： $\sum_{k=1}^{n-1}P(k)P(n-k) (n\geq2)$

可以得知，暴力解题的时间复杂度，不管放在什么情况下都是不符合题目要求的，因此，找到一个优秀的算法是很有必要的。

我们可以将一串矩阵A1,A2,…,An的计算数表示为M[1][n],即第一个矩阵到第n个矩阵的计算总数。

因此，对于任意一个长度大于1的矩阵串，我们可以分解为M[1][k]和M[k][1]，以此类推，直到分解到n个长度为1的矩阵。

对于这n个矩阵，我们可以得到递归式 $m[i,j]=min\{m[i,k]+m[k+1,j]+p_{i-1}p_kp_j \} (i<j)$ 来得到。

此时，已经可以使用递归的方式求解得到答案，但是算法的时间复杂度依旧为O(n^2)，而若利用自底向上的表格法代替递归，则可以将时间复杂度降低到O(n^2)

这里向大家介绍一下自底向上的表格法：

对于递归来说，令人诟病的问题在于有很多的计算过程需要重复花费时间。

而自底向上的表格法，则会自动保存每次计算的结果，当下次需要使用时，直接读取，消耗了内存空间，但是却加快了运行速度。

因此，我们可以写出如下关键代码

int** solve(int n,int p[]){
  int s[n][n];	//用于记录乘法顺序
  int m[n][n];
  for(int i=1;i<n;i++)
  {
    m[i][i]=0;			//i与i的乘法计算量为0
  }
  for(int l=2;l<n;l++)
  {
    //i=1时，计算m[i][i+1]的乘法计算量，以此类推，可以从最底层向最高层递进，直到得到m[1][n]的最小值。
    for(int i=1;i<n-l+1)
    {
      j=i+l-1;
      m[i][j]=MAXN;
      for(int k=i;k<j-1;k++)
      {
        q=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
        if(q<m[i][j])
        {
          m[i][j]=q;
          s[i][j]=k;
        }
      }
    }
  }
}

随后我们可以通过数组s来得到最优乘法顺序。

void show(int s[][],int i,int j){
  if(i==j)
    printf("A%d",i);
  else{
    printf("(");
    show(s,i,s[i][j]);
    show(s,s[i][j]+1,j);
    printf(")");
  }
}

最终代码如下：

#include<stdio.h>
int s[1000][1000];
int m[1000][1000];
void solve(int n,int p[]){
    int q=0;
    int j;
    for(int i=0;i<=n;i++)
    {
      m[i][i]=0;            //i与i的乘法计算量为0
    }
    for(int l=2;l<=n;l++)
    {
    //i=1时，计算m[i][i+1]的乘法计算量，以此类推，可以从最底层向最高层递进，直到得到m[1][n]的最小值。
      for(int i=1;i<=n-l+1;i++)
      {
          j=i+l-1;
          m[i][j]=99999999;
          for(int k=i;k<=j-1;k++)
          {
              q=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
              if(q<m[i][j])
              {
                  m[i][j]=q;
                  s[i][j]=k;
              }
          }
      }
    }
}

void show(int i,int j){
  if(i==j)
    printf("A%d",i);
  else{
    printf("(");
    show(i,s[i][j]);
    show(s[i][j]+1,j);
    printf(")");
  }
}

int main(){
  int n;
  int p[1000];
  printf("请输入n\n");
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
  {
    scanf("%d",&p[i]);
  }
  solve(n-1,p);
  show(1,n-1);
  return 0;

}

测试用例如下：

7
30 35 15 5 10 20 25

结果如下：

((A1(A2A3))((A4A5)A6))