【C++】 动态规划—矩阵链乘
【本文原创于Paul的博客园技术博客。】
【本文欢迎转载,转载请以链接形式注明出处。】
【本博客所有文章都经博主精心整理,请尊重我的劳动成果。】
【C++】 动态规划—矩阵链乘
1、问题描述
给定n个矩阵构成的一个链给定{A1,A2,…,An},其中i=1,2,...,n.矩阵Ai的维数为pi-1*pi,如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。
2、最优子结构
3、状态转移方程
4、代码实现
1 #include<iostream> 2 using namespace std; 3 //p为矩阵链,p[0],p[1]代表第一个矩阵,p[1],p[2]代表第二个矩阵,length为p的长度 4 //所以如果有六个矩阵,length=7,m为存储最优结果的二维矩阵,t为存储选择最优结果路线的 5 //二维矩阵 6 void MatrixChainOrder(int *p,int (*m)[10],int (*t)[10],int length) 7 { 8 int n=length-1; 9 int i,j,k,q,num=0; 10 //A[i][i]只有一个矩阵,所以相乘次数为0,即m[i][i]=0; 11 for(i=1;i<length;i++) 12 { 13 m[i][i]=0; 14 } 15 //i代表矩阵链的长度,i=2表示有两个矩阵相乘时如何划分 16 for(i=2;i<=n;i++) 17 { 18 //j表示从第j个矩阵开始的i个矩阵如何划分是最优 19 for(j=1;j<=n-i+1;j++) 20 { 21 //k为从第j个数i个矩阵就是k,从j到k表示他们之间的i个矩阵如何划分 22 k=j+i-1; 23 //m[j][k]存储了从j到k使用最佳划分所得到的最优结果 24 m[j][k]=0x7fffffff; 25 //q为介于j到k-1之间的数,目的是利用q对j到k之间的矩阵进行试探性的划分, 26 //从而找到最优划分,这是一种遍历性的试探。 27 for(q=j;q<=k-1;q++) 28 { 29 num=m[j][q]+m[q+1][k]+p[j-1]*p[q]*p[k]; 30 if(num<m[j][k]) 31 { 32 m[j][k]=num; 33 t[j][k]=q; 34 } 35 } 36 } 37 } 38 } 39 void PrintAnswer(int(*t)[10],int i,int j) 40 { 41 if(i==j) 42 { 43 cout<<"A"<<i; 44 } 45 else 46 { 47 cout<<"("; 48 PrintAnswer(t,i,t[i][j]); 49 PrintAnswer(t,t[i][j]+1,j); 50 cout<<")"; 51 } 52 53 } 54 int main() 55 { 56 int p[7]={30,35,15,5,10,20,25}; 57 int m[10][10],t[10][10]; 58 MatrixChainOrder(p,m,t,7); 59 MatrixChainOrder(p,m,t,7); 60 PrintAnswer(t,1,6); 61 cout<<endl; 62 return 0; 63 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。