矩阵连乘问题

《矩阵连乘问题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、矩阵连乘问题问题:给定的n个矩阵{A1,A2,A3,A4……,An}，其中Ai与Ai+1是可乘的，i=1,2,3……，n-1。考察这n个矩阵连乘积A1A2A3A4……An。分析:由于矩阵乘法满足结合律，故计算矩阵的乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式确定。若一个矩阵的连乘次序完全确定，也就是说该连乘积已经完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘

2、积可以递归的定义为：（1）单个矩阵是完全加括号的（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的连乘积B和C的乘积并加括号，级A=（BC）。伪代码:1计算最优值，依据其递归式以自底向上的方式进行计算。voidmatrixChain(){for(inti=1;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++)//对角线循环for(inti=1;i<=n-r+1;i++){//行循环intj=i+r-1;//列的控制//找m[i][j]的最小值，先初始化一下，令k=im

3、[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;//k从i+1到j-1循环找m[i][j]的最小值for(intk=i+1;k

4、eback(inti,intj){staticinta=0;intx=0;inty=0;if(i==j)return;traceback(i,s[i][j]);traceback(s[i][j]+1,j);for(intp=0;pij[p][q])x++;if(j>ij[p][q])y++;}insert(i+x,j+y,n);ij[a][0]=i;ij[a][1]=j;a++;n=n+2;//数组每次增加2//即增加了左右括号}3，在原数组

5、ABC……间插入括号voidinsert(inti,intj,intm)//插入括号{intx=m;for(;x>=i;x--)line[x+1]=line[x];line[x+1]='(';x=m+1;j++;for(;x>j;x--)line[x+1]=line[x];line[x+1]=')';}程序：#includeusingnamespacestd;constintMAX=100;//p用来记录矩阵的行列，main函数中有说明//m[i][j]用来记录第i个矩阵至第j个矩阵的最

6、优解//s[][]用来记录从哪里断开的才可得到该最优解intp[MAX+1],m[MAX][MAX],s[MAX][MAX];charline[MAX];intn;//矩阵个数intij[MAX][2];//存放每次调用时，i,j的值voidinsert(inti,intj,intm)//插入括号{intx=m;for(;x>=i;x--)line[x+1]=line[x];line[x+1]='(';x=m+1;j++;for(;x>j;x--)line[x+1]=line[x];line[x+1]=')

7、';}voidmatrixChain(){for(inti=1;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++)//对角线循环for(inti=1;i<=n-r+1;i++){//行循环intj=i+r-1;//列的控制//找m[i][j]的最小值，先初始化一下，令k=im[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;//k从i+1到j-1循环找m[i][j]的最小值for(intk=i+1;k

8、m[k+1][j]+p[i-1]*p[k]*p[j];if(t