加载中…动态规划中的链矩阵相乘的介绍与理解（含c语言源代码）
(2014-09-20 17:46:06)
标签：
算法导论c语言it图片娱乐 |
分类： 数据结构和算法导论 |
动态规划中矩阵链乘法问题描述：
此问题最难的地方在于找到最优子结构。对乘积A1A2...An的任意加括号方法都会将序列在某个地方分成两部分，也就是最后一次乘法计算的地方，我们将这个位置记为k，也就是说首先计算A1...Ak和Ak+1...An，然后再将这两部分的结果相乘。
最优子结构如下：假设A1A2...An的一个最优加括号把乘积在Ak和Ak+1间分开，则前缀子链A1...Ak的加括号方式必定为A1...Ak的一个最优加括号，后缀子链同理。
一开始并不知道k的确切位置，需要遍历所有位置以保证找到合适的k来分割乘积。
2）构造递归求解方案
设m[i,j]为矩阵链Ai...Aj的最优解的代价，则
m[i,j] = │
举个例子：
计算m[2,5]的最优运算的过程；
从而m【2,5】最小运算的次数为7125；注意上面的m[3,5]，m[2,4]都是去最小运算次数，根据递归运算可得；
从第二步的递归式可以发现解的过程中会有很多重叠子问题，可以用一个nXn维的辅助表s[n][n]来保存子问题的解，表中每个元素包含2个信息，分别是最优乘积代价及其分割位置k 。
辅助表s[n][n]可以由2种方法构造，一种是自底向上填表构建，该方法要求按照递增的方式逐步填写子问题的解，也就是先计算长度为2的所有矩阵链的解，然后计算长度3的矩阵链，直到长度n；另一种是自顶向下填表的备忘录法，该方法将表的每个元素初始化为某特殊值(本问题中可以将最优乘积代价设置为一极大值)，以表示待计算，在递归的过程中逐个填入遇到的子问题的解。
备忘录法会比自底向上法慢一个常数因子，因为前者有递归调用的代价，维护表格的开销也稍大。
源代码如下（c语言）：
#include
int p[7]={30,35,15,5,10,20,25};
int m[7][7];
int s[7][7];
void MATRIX_CHAIN_ORDER()
{
int n=7-1;
int i,l,j,k,q;
for(i=1;i<= n;i++)
m[i][i]=0;
//上面两句语句是对矩阵m[i][j]的对角线初始化；
//不要以为后面有了对矩阵更加好的初始化，从而不必需要这语句；这个语句是如果矩阵是一个，则相乘数目为0；
for(l=2;l<= n;l++)
{
for(i=1;i<= n-l+1;i++)
{
j=i+l-1;
m[i][j]=1000000;
for(k=i;k<= j-1;k++)
{
q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(q
{
m[i][j]=q;
s[i][j]=k;
//对矩阵最小运算的坐标记住方便，括号的标记保存；
}
}
}
}
}
void PRINT_OPTIMAL_PARENS(int i,int j)
{
if(i==j)
printf("A%d",i);
else
{
printf("(");
PRINT_OPTIMAL_PARENS(i,s[i][j]);
//s[i][j]是记录了k值，最优括号在Ak与A（k+1）之间；
PRINT_OPTIMAL_PARENS(s[i][j]+1,j);
printf(")");
}
}
int main()
{
int i,j;
printf("输入的矩阵维数如下：\n");
for(i=0;i<6;i++)
printf("A%d=%d*%d ",i+1,p[i],p[i+1]);
printf("\n");
printf("得到的矩阵为：\n");
MATRIX_CHAIN_ORDER();
for(i=1;i<=6;i++)
{
for(j=1;j<=6;j++)
{
if(j>=i)
printf("m",m[i][j]);
else
printf("
");
//这样做的目的是只打印上三角的数据，原因，其他数据都为零，没有意义；
}
printf("\n");
}
printf("最优括号位置的打印：\n");
for(i=1;i<=6;i++)
{
for(j=1;j<=6;j++)
{
if(j>=i)
printf("m",s[i][j]);
else
int p[7]={30,35,15,5,10,20,25};
int m[7][7];
int s[7][7];
void MATRIX_CHAIN_ORDER()
{
}
void PRINT_OPTIMAL_PARENS(int i,int j)
{
}
int main()
{