3-1矩阵连乘问题(动态规划和备忘录方法)-创新互联
3-1 矩阵连乘问题
一、题目
本文题目:3-1矩阵连乘问题(动态规划和备忘录方法)-创新互联
地址分享:http://scjbc.cn/article/dhgegs.html
给定n个矩阵:A1,A2,…,An,其中Ai与Ai+1是可乘的,i=1,2…,n-1。考察这n个矩阵的连乘积A1A2…An。
确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。
这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用 2 个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为:
( 1 )单个矩阵是完全加括号的;
( 2 )矩阵连乘积 A 是完全加括号的,则 A 可表示为 2 个完全加括号的矩阵连乘积 B 和 C 的乘积并加括号,即 A= ( BC )。
//3-1矩阵连乘问题
// 6 30 35 15 5 10 20 25
#includeusing namespace std;
int n;//n个矩阵,n+1个数
int p[100];//Ai的维数为p[i-1]*p[i]
int m[100][100];//
int s[100][100];//记录断开的位置
void MatrixChain(){//动态规划 --自底向上
int r,i,j,k;
for(i=1;i<=n;i++) m[i][i]=0;
for(r=2;r<=n;r++){for(i=1;i<=n-r+1;i++){ j=i+r-1;
m[i][j]=m[i+1][j] + p[i-1]*p[i]*p[j];
s[i][j]=i;
for(k=i;k<=j;k++){ int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(t m[i][j] = t;
s[i][j] = k;
}
}
}
}
}
void Traceback(int i,int j){//构造最优解
if(i==j){cout<<"A"<for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){ cout<//初始化为0
for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){ a[i][j]=0;
}
}
}
int Look(int i,int j){//备忘录方法---自顶向下
if(m[i][j]>0) return m[i][j];
if(i==j) return 0;
int u =Look(i,i)+Look(i+1,j)+p[i-1]*p[i]*p[j];
s[i][j]=i;
for(int k=i+1;kint t = Look(i,k)+Look(k+1,j)+p[i-1]*p[k]*p[j];
if(t u=t;
s[i][j]=k;
}
}
m[i][j]=u;
return u;
}
int main(){cin>>n;
for(int i=0;i<=n;i++)
cin>>p[i];
MatrixChain();
cout<<"m[i][j]\n";
Print(m);
cout<<"s[i][j]\n";
Print(s);
cout<<"traceback\n";
Traceback(1,n);
Clear(s);
Clear(m);
cout<<"\n备忘录方法\nlook[1][n]="<
四、运行截图
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
本文题目:3-1矩阵连乘问题(动态规划和备忘录方法)-创新互联
地址分享:http://scjbc.cn/article/dhgegs.html