基本思想： 1．按照2个矩阵乘积的标准算法，若一个p×q的矩阵A和一个s×t的矩阵B相乘（当然s和q要相等），要进行三重循环，总共需要pqr次数乘，显然这是一个比较的的数。 2．通过简单分析，我们易知给连乘矩阵xx加括号方式对应一种矩阵连乘的计算次序，而这种计算次序会改变计算矩阵连乘的计算量，再试想如果是n个矩阵进行连乘那将会要太多次数乘，所以有必要做一个算法找出怎样合理的给连乘矩阵xx加括号以找出最少计算量的计算方法。 3．穷举搜索法是最容易想到的方法，但是它本身是一个计算量非常大的算法，对于n个矩阵的连乘问题，不同的计算次序是随n的增大呈指数增长的。 4．尝试用动态规划算法解决上面问题：首先由于A【1：n】（表示1到n个矩阵连乘）如果是{zy}解，那么它包含的A【1：k】和A【k＋1：n】也是{zy}解，即矩阵连乘求{zy}解符合动态规划中的{zy}子结构性质；再次由于A【i：j】的最少数乘次数m【i】【j】可以表示为m【i】【j】＝m【i】【k】＋m【k＋1】【j】＋pj－1pkpj（其中k是断开点），所以它也可以设计成一个具有递归关系的算法。 5．具体实现：按照m【1】【n】的递归性以自底向上的方式进行计算，在计算中用m【】【】数组记录已经计算过的自问题的答案，m【i】【j】表示A【i：j】的最少数乘次数，并且用数组s【】【】来表示对应的m【】【】数组值的{zy}断开点。 程序由两个函数组成：1）、void MatrixChain(int p[],int n)用来产生数组m和s，是关键部分；2）、int Traceback(int i,int j)是用来找出s数组中记录的{zy}断开点的函数。程序中我把m和s数组都给了输出，方便观察、研究。 程序如下： #include #include using namespace std; #define SIZE 6 //控制参与连乘矩阵的个数 int m[SIZE][SIZE],s[SIZE][SIZE]; void MatrixChain(int p[],int n) //用来产生数组m和s，是关键部分 { for(int a=0;a<n;a++) m[a][a]=0; for(int r=2;r<=n;r++) for(int i=0;i<n-r+1;i++) { int j=i+r-1; m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1]; s[i][j]=i+1; for(int k=i+1;k<j;k++) { int t=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1]; if(t<m[i][j]) { m[i][j]=t; s[i][j]=k+1; } } } } int Traceback(int i,int j) //找出s数组中记录的{zy}断开点 { if(i==j) return -1; Traceback(i,s[i][j]-1); Traceback(s[i][j],j); cout<<"包含矩阵 A"<<s[i][j]; cout<<"的部分与包含矩阵 A"<<(s[i][j]+1)<<"的部分结合，放在一个括号中"<<endl; return 0; } void main() { int p[SIZE+1]={30,35,15,5,10,20,25}; //p记录矩阵的行列数 MatrixChain(p,SIZE); cout<<"输出m矩阵为："<<endl; for(int i=0;i<SIZE;i++) { for(int j=0;j<SIZE;j++) { cout<<setw(6)<<m[i][j]<<" "; } cout<<endl; } cout<<endl<<endl; cout<<"输出s矩阵为："<<endl; for(int a=0;a<SIZE;a++) { for(int b=0;b<SIZE;b++) { cout<<setw(6)<<s[a][b]<<" "; } cout<<endl; } cout<<endl<<endl; Traceback(0,5); }