矩阵连乘问题.doc

矩阵连乘问题
问题:
给定的n个矩阵{A1,A2,A3,A4……,An}，其中Ai与Ai+1是可乘的，i=1,2,3……，n-1。考察这n个矩阵连乘积A1A2A3A4……An。

分析:
由于矩阵乘法满足结合律，故计算矩阵的乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式确定。若一个矩阵的连乘次序完全确定，也就是说该连乘积已经完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可以递归的定义为：
（1） 单个矩阵是完全加括号的
（2） 矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的连乘积B和C的乘积并加括号，级A=（BC）。

伪代码:
1 计算最优值，依据其递归式以自底向上的方式进行计算。
void matrixChain(){
for(int i=1;i<=n;i++)m[i][i]=0;

for(int r=2;r<=n;r++)//对角线循环
for(int i=1;i<=n-r+1;i++){//行循环
int j = i+r-1;//列的控制
//找m[i][j]的最小值，先初始化一下，令k=i
m[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(int k = i+1;k<j;k++){
int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(t<m[i][j]){
m[i][j]=t;
//s[][]用来记录在子序列i-j段中，在k位置处
//断开能得到最优解
s[i][j]=k;
}
}
}
}
2.按算法matrixChain计算，以加括号方式输出计算A[i：j]的最优计算次序。
void traceback(int i,int j){
static int a=0;

int x=0;
int y=0;
if(i==j)return ;

traceback(i,s[i][j]);
traceback(s[i][j]+1,j);

for(int p=0;p<a;p++)
for(int q=0;q<=1;q++)
{
if(i>ij[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，在原数组ABC……间插入括号
void insert(int i,int j,int m)//插入括号
{
int x=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]=')';

}

程序：
#include<iostream>
using namespace std;
const int MAX = 100;
//p用来记录矩阵的行列，main函数中有说明
//m[i][j]用来记录第i个矩阵至第j个矩阵的最优解
//s[][]用来记录从哪里断开的才可得到该最优解
int p[MAX+1],m[MAX][MAX],s[MAX][MAX];
char line[MAX];
int n;//矩阵个数
int ij[MAX][2];//存放每次调用时，i,j的值

void insert(int i,int j,int m)//插入括号
{
int x=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]=')';

}

void matrixChain(){
for(int i=1;i<=n;i++)m[i][i]=0;

for(int r=2;r<=n;r++)//对角线循环
for(int i=1;i<=n-r+1;i++){//行循环
int j = i+r-1;//列的控制
//找m[i][j]的最小值，先初始化一下，令k=i
m[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(int k = i+1;k<j;k++){
int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(t<m[i][j]){
m[i][j]=t;
//s[][]用来记录在子序列i-j段中，在k位置处
//断开能得到最优解
s[i][j]=k;
}
}
}
}

//根据s[][]记录的各个子段的最优解，将其输出
void traceback(int i,int j){
static int a=0;

int x=0;
int y=0;
if(i==j)return ;

traceback(i,s[i][j]);
traceback(s[i][j]+1,j);

for(int p=0;p<a;p++)
for(int q=0;q<=1;q++)
{
if(i>ij[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//即增加了左右括号
}

int main(){
cout<<"矩阵个数：";
cin>>n;
int k=n;
for(int i=1;i<=n;i++)line[i]='A'+i-1;
cout<<"第一个矩阵行数和以后矩阵列数：";
for(i=0;i<=n;i++)cin>>p[i];
matrixChain();
traceback(1,n);
//最终解值为m[1][n]
cout<<"最优算法"<<endl;
for( i=1;i<=n;i++)
cout<<line[i];
cout<<endl;
cout<<"最少次数：";
cout<<m[1][k]<<endl;
return 0;
}

运行情况：