|
给定有n个要相乘的矩阵构成的序列（链）<A1,A2,A3,……，An>,要计算乘积A1A2……An.一组矩阵是加全部括号的。矩阵链加括号对运算的性能有很大影响。
仅当两个矩阵A和B相容（即A的列数等于B的行数），才可以进行相乘运算。如果A是一个p×q矩阵，B是q×r矩阵，结果C是p×r的矩阵。计算C的时间由乘法运算次数决定的，次数为p×q×r.
矩阵链乘法问题可表述为：给定n个矩阵构成的一个链<A1,A2,A3……，An>,其中i=1,2,3,4……，n,矩阵Ai的维数为Pi-1 ×Pi,对乘积A1A2A3……An,以一种最小标量乘法次数的方式进行加全部括号。
对AiAi+1……Aj的任何家全部括号形式都将乘积在Ak和Ak+1之间分开，即计算矩阵Ai…k和Ak+1……Aj,然后将他们相乘得到最终的乘积Ai……j.加全括号的代价是Ai…k和Ak+1…j的代价之和，再加上两者相乘的代价。
加全部括号最小代价的递归定义：
m[i,j]=min{m[i,k] + m[k+1,j] + Pi-1 * Pk *Pj} ;i<j; m[i,j]=0; i==j;
计算最优代价时，使用辅助表m[n][n]来保存m[i][j],使用s[n][n]来记录计算m[i][j]时取得的最优代价处的k值，即每一个表项s[i][j]都记录了对乘积AiAi+1……Aj在Ak和Ak+1之间进行分裂取得的最优加全部括号时的k值。
全部代码如下：
[cpp]
//计算矩阵链乘积所需的最有标量乘法次数
void MATRIX_CHAIN_ORDER（int PArray[], int m[][PArrayLength], int s[][PArrayLength], int Length）
{
int n=Length-1;//表示有n个矩阵相乘
int temp=0;//临时变量
for （int i=1; i<Length; i++）
{
m[i][i]=0;//先将代价初始化为0;长度为1的链最小代价为0
}
for （int l=2; l<=n; l++）//从第二个链开始分别计算长度为2、3、n的链的最小代价
{
for （int i=1; i<=n-l+1; i++）
{
int j=i+l-1;
m[i][j]=0x7fffffff;
for（int k=i; k<j; k++）//逐个检验K值，找到最小代价的k值
{
temp=m[i][k]+m[k+1][j]+PArray[i-1]*PArray[k]*PArray[j];
if （temp<m[i][j]）
{
m[i][j]=temp;
s[i][j]=k;
}
}
}
}
}
//构造一个最优解
void PRINT_OPTIMAL_PARENS（int s[][PArrayLength], int i, int j）
{
if （i==j）
{
cout《“A”《i;
}
else
{
cout《“（”;
PRINT_OPTIMAL_PARENS（s, i, s[i][j]）；
PRINT_OPTIMAL_PARENS（s, s[i][j]+1, j）；
cout《“）”;
}
}
|