矩阵连乘问题.doc

矩阵连乘问题问题:给定的n个矩阵A1,A2,A3,A4,An，其中Ai与Ai+1是可乘的，i=1,2,3，n-1。考察这n个矩阵连乘积A1A2A3A4An。分析:由于矩阵乘法满足结合律，故计算矩阵的乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式确定。若一个矩阵的连乘次序完全确定，也就是说该连乘积已经完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可以递归的定义为：（1） 单个矩阵是完全加括号的（2） 矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的连乘积B和C的乘积并加括号，级A=（BC）。伪代码:1 计算最优值，依据其递归式以自底向上的方式进行计算。void matrixChain() for(int i=1;i=n;i+)mii=0; for(int r=2;r=n;r+)/对角线循环 for(int i=1;i=n-r+1;i+)/行循环 int j = i+r-1;/列的控制 /找mij的最小值，先初始化一下，令k=i mij=mi+1j+pi-1*pi*pj; sij=i; /k从i+1到j-1循环找mij的最小值 for(int k = i+1;kj;k+) int t=mik+mk+1j+pi-1*pk*pj; if(tmij) mij=t; /s用来记录在子序列i-j段中，在k位置处 /断开能得到最优解 sij=k; 2.按算法matrixChain计算，以加括号方式输出计算Ai：j的最优计算次序。void traceback(int i,int j) static int a=0; int x=0; int y=0; if(i=j)return ; traceback(i,sij); traceback(sij+1,j); for(int p=0;pa;p+) for(int q=0;qijpq)x+; if(jijpq)y+; insert(i+x,j+y,n);ija0=i;ija1=j;a+;n=n+2;/数组每次增加2/即增加了左右括号 3，在原数组ABC间插入括号void insert(int i,int j,int m)/插入括号 int x=m; for(;x=i;x-) linex+1=linex; linex+1=(; x=m+1; j+; for(;xj;x-) linex+1=linex; linex+1=); 程序：#include using namespace std; const int MAX = 100; /p用来记录矩阵的行列，main函数中有说明 /mij用来记录第i个矩阵至第j个矩阵的最优解 /s用来记录从哪里断开的才可得到该最优解 int pMAX+1,mMAXMAX,sMAXMAX; char lineMAX; int n;/矩阵个数 int ijMAX2;/存放每次调用时，i,j的值 void insert(int i,int j,int m)/插入括号 int x=m; for(;x=i;x-) linex+1=linex; linex+1=(; x=m+1; j+; for(;xj;x-) linex+1=linex; linex+1=); void matrixChain() for(int i=1;i=n;i+)mii=0; for(int r=2;r=n;r+)/对角线循环 for(int i=1;i=n-r+1;i+)/行循环 int j = i+r-1;/列的控制 /找mij的最小值，先初始化一下，令k=i mij=mi+1j+pi-1*pi*pj; sij=i; /k从i+1到j-1循环找mij的最小值 for(int k = i+1;kj;k+) int t=mik+mk+1j+pi-1*pk*pj; if(tmij) mij=t; /s用来记录在子序列i-j段中，在k位置处 /断开能得到最优解 sij=k; /根据s记录的各个子段的最优解，将其输出 void traceback(int i,int j) static int a=0; int x=0; int y=0; if(i=j)return ; traceback(i,sij); traceback(sij+1,j); for(int p=0;pa;p+) for(int q=0;qijpq)x+; if(jijpq)y+; insert(i+x,j+y,n);ija0=i;ija1=j;a+;n=n+2;/数组每次增加2/即增加了左右括号 int main() coutn; int k=n; for(int i=1;i=n;i+)linei=A+i-1; cout第一个矩阵行数和以后矩阵列数：; for(i=0;ipi; matrixChain(); traceback(