一、问题描述

给定一个矩阵序列<A₁,A₂,…,A_n>，计算乘积A₁A₂…A_n。要求找出一个加全部括号的方式，使得标量乘法的次数最小。

加全部括号：

性质1，A₁A₂…A_n相乘，必须满足前一个矩阵的列数等于后一个矩阵的行数。

证明：假设A_i的列数为p_i，i=1,…,n。下面我们来看各矩阵的行数。

当n=2时，根据矩阵乘法的定义可知，A₁的列数等于A₂的行数。因此，A₂的行数等于p1。

当n=3时，因为A₁A₂相乘得到的新矩阵的列数为p₂，而A₁A₂和A₃可以相乘，因此A₃的行数为p₂。

依次类推，A_i(i≥2)的行数为p_i-1，得证。

性质2，序列中的任何n个相邻矩阵都可以直接相乘，n≥2。

证明：

根据性质1可知，任意两个相邻矩阵都可以相乘，即n=2时，满足上述性质。

n=3时，假设我们选择任意相邻矩阵A_i-1A_iA_i+1，根据矩阵性质，A_i-1A_i得到的新矩阵为p_i-2×p_i，而A_i+1为p_i×p_i+1，因此A_i-1A_i得到的矩阵可以与A_i+1相乘，即A_i-1A_iA_i+1可以相乘。由于这三个矩阵是任意选择的，因此，n=3时，满足上述性质。

依次类推，对于任意n>=2，均满足上述性质。得证。

 

加全部括号具体步骤如下：

步骤一：选取相邻的两个矩阵，加括号；

步骤二：将步骤一中的括号看做一个新的矩阵，放回原先位置，得到一个新的序列；

步骤三：如果新序列中矩阵个数等于1，则结束，否则，返回步骤一。

也可以按照下面步骤进行加括号：

步骤一：如果当前序列只有一个矩阵，则不需加括号，否则将整个序列最外层加一个括号，使其成为一个新序列；

步骤二：检查序列里面是否有两个以上矩阵；

步骤三：如果是，则在这些矩阵中找一个分界点，将其分为两个新序列，对这两个新序列分别从步骤一开始重复执行上述步骤。

 

对于任意两个矩阵A_iA_i+1相乘，其乘法次数为p_i-1p_i p_i+1，不同的加全部括号，所需要的乘法次数可能相差很大。

假设现在有三个矩阵A₁A₂A₃相乘，维数分别为：10×100，100×5，5×50。

1、如果我们采用如下方式加全部括号：

(（A₁A₂）A₃)

则

首先计算（A₁A₂），乘法次数为p₀p₁ p₂，得到新矩阵的维数为p₀× p₂

计算(（A₁A₂）A₃)，乘法次数为p₀p₂ p₃，

总的计算次数为p₀p₁ p₂+ p₀p₂ p₃=10×100×5+10×5×50=7500

 

2、如果我们采用如下方式加全部括号：

(A₁（A₂ A₃）)

则

首先计算（A₂ A₃），乘法次数为p₁ p₂ p₃，得到新矩阵的维数为p₁× p₃

计算(A₁（A₂ A₃）)，乘法次数为p₀p₁ p₃，

总的计算次数为p₁ p₂ p₃+ p₀p₁ p₃=100×5×50+10×100×50=75000

 

第二种方式需要的次数是第二次的10倍！

 

二、问题分析：

由前面可知，一个序列如果只有一个矩阵，则只有一种方式加全部括号，如果有两个或两个以上的矩阵，则必然可以看做两个子序列的乘积，且这两个子序列也是加全部括号。我们用cost(i,j)表示序列A_i…A_j在最优加全部括号时的标量乘积次数，则

http://s12/middle/70ec9a6fhb9ed2baf748b&690

其中p_i-1p_k p_j为子序列A_i…A_k与A_k+1…A_j相乘时的标量相乘次数。

三、问题求解

每一对满足1≤i≤j≤n的i和j都对应原问题的一个子问题，子问题个数为http://s3/middle/70ec9a6fhb9ed3616ea92&690，其中第一项表示i<j时的子问题个数，后一项表示i=j时的子问题个数。如果采用递归方法求解，则每个子问题都会被求解多次，因此，我们也采用自底向上的动态规划方式求解。

首先定义一个二维矩阵value，value[i][j]存放子序列A_i…A_j在最优加全部括号时的标量乘积次数，我们只使用j>=i的部分，且value[i][i]=0。

动态规划的实现步骤如下：

步骤一：令step=0；

步骤二：对于所有i=0，…，n，计算并保存value[i][i+step；

步骤三：若step=n-1，则结束，否则step=step+1，返回步骤二。

四、例题

假设现在有如下矩阵序列：

C语言实现如下：

 

#include <stdio.h>

#include <stdlib.h>

#define ArrS 6   

//数组个数

 

int m_value(int i,int j,int value[][ArrS+1],int Num1,int dimentions[],int position[][ArrS+1]);

void show(int position[][ArrS+1],int i,int j);

 

int main()

{

       int position[ArrS+1][ArrS+1]={0}; //position[i][j]=k，表示子序列被分为i,...,k和k+1,...,j两组

       int value[ArrS+1][ArrS+1]={0};//value[i][j]表示子序列i，...，j相乘所需最小次数

       int dimentions[ArrS+1]={30,35,15,5,10,20,25}; //数组i的维数是dimentions[i-1]行dimentions[i]列

      

       int i,j,L;

 

       for(j=0;j<ArrS;j++)

           for(i=1;i+j<=ArrS;i++)

               value[i][i+j]=m_value(i,i+j,value,ArrS+1,dimentions, position);

 

      

       printf("Show the position[i][j]:\n");       

    for(i=1;i<=ArrS;i++)

    {

           for   (j=1;j<=ArrS;j++)

               printf("�, ",position[i][j]);

           printf("\n");

       }

                

 

       printf("\n\nThe path is:\n");

       show(position,1,6);

 

    system("PAUSE"); 

    return 0;

}

 

int m_value(int i,int j,int value[][ArrS+1],int Num1,int dimentions[],int position[][ArrS+1])

{

       if(j==i)

       {

              position[i][j]=i;

              return 0;

       }

             

       int k,min;

       min=dimentions[i-1]*dimentions[i]*dimentions[j]+value[i+1][j];

       position[i][j]=i;

       for(k=i+1;k<j;k++)

           if(min>dimentions[i-1]*dimentions[k]*dimentions[j]+value[i][k]+value[k+1][j])

           {

               min=dimentions[i-1]*dimentions[k]*dimentions[j]+value[i][k]+value[k+1][j];

               position[i][j]=k;

              }

      

       return min;

}

      

void show(int position[][ArrS+1],int i,int j)

//用递归的方法去显示完整路径，调用的方式是 show(1，n）

{

       if (j<=i)

           return;

       int a;

       a=position[i][j];

       printf("position[%d][%d]=%d  \n",i,j,position[i][j]);

       show(position,i,a);

       show(position,a+1,j);

}