动态规划解决矩阵连乘问题
给定n个矩阵{A1,A2,…,An},其中,Ai与Ai+1是可乘的,(i=1,2 ,…,n-1)。用加括号的方法表示矩阵连乘的次序,不同的计算次序计算量(乘法次数)是不同的,找出一种加括号的方法,使得矩阵连乘的次数最小。......
动态规划解决矩阵连乘问题
文章目录
动态规划
1.要素
动态规划两大要素:最优子结构、重叠子问题
最优子结构:当问题的最优解包含了其子问题的最优解时,该问题具有最优子结构性质
重叠子问题:在用递归算法自底向下解此问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算,具有子问题重叠性质。这类问题称重叠子问题
2.基本思想
将待求解问题分解成若干个子问题,先求解子问题,然后结合这些子问题的解得到原问题的解。求解的问题经分解得到的子问题往往不是相互独立的
3.适用于解最优化问题步骤
1)找出最优解的性质,并刻画其结果特征(分析最优解结构)
2)递归地定义最优解(建立递归关系)
3)以自底向上的方法计算得到的信息,构造最优解(计算最优解)
4)根据计算最优值得到的信息,构造最优解(构造最优解)
1)2)3)为基本步骤
提示:以下是本篇文章正文内容,下面案例可供参考
一、矩阵连乘问题
给定n个矩阵{A1,A2,…,An},其中,Ai与Ai+1是可乘的,(i=1,2 ,…,n-1)。用加括号的方法表示矩阵连乘的次序,不同的计算次序计算量(乘法次数)是不同的,找出一种加括号的方法,使得矩阵连乘的次数最小。
规则
若一个矩阵连乘积的次序完全确定,也就是说该连乘积已完全加括号,则可反复调用2个矩阵相乘的标准算法计算出矩阵连乘积
完全加括号的矩阵连乘积可递归地定义为:
1)单个矩阵是完全加括号的
2)矩阵连乘积A是完全加括号的,则A可表示为2个完全加括号的矩阵连乘积B和C的乘积在加括号,即A=(BC)
矩阵可乘的条件
矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数
计算的次序对计算量的影响
例如:
A1是A(5*10)的方阵;
A2是A(10*100)的方阵;
A3是A(100*2)的方阵;
那么有两种加括号的方法:
1.(A1A2)A3;
2. A1(A2A3);
第一种方法的计算量:5*10*100+5*100*2=6000;
第二种方法的计算量:10*100*2+5*10*2=2100;
可以看出不同计算方法计算量差别很大。
二、动态规划
1.分析:
1.矩阵连乘的条件:第一个矩阵的列等于第二个矩阵的行,此时两个矩阵是可乘的;
2. 多个矩阵连乘的结果矩阵,其行列等于第一个矩阵的行和最后一个矩阵的列;
3.两个矩阵相乘的计算量
矩阵Amn和Bnk的乘法运算次数为:mnk
2.矩阵连乘AiAi+1Ai+2……Aj的最优解问题
假设在第k位置上找到最优解,则问题变成了两个子问题:(AiAi+1……Ak),(Ak+1……Aj)
用m[i][j]表示矩阵连乘的最优值,那么两个子问题对应的最优值变成m[i][k],m[k+1][j];
设矩阵Am的行数为Pm,列数为qm,矩阵是可连乘的,即相邻矩阵qm=Pm+1,所以(AiAi+1……Ak)可表示为Pi * qk,
(Ak+1……Aj)可表示为Pk+1 * qj,qk = Pk+1.则两个矩阵连乘的乘法次数为Pi * Pk+1 * qj。
3.矩阵连乘最优值递归式:
代码如下(示例):
#include<iostream>
#include<cstring>
using namespace std;
const int size=100;
int p[size];
int m[size][size],s[size][size];
int n;
void matrixchain()
{
int i,r,j,k;
memset(m,0,sizeof(m));
memset(s,0,sizeof(s));//初始化数组
for(r=2;r<=n;r++)//矩阵连乘的规模为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];//对m[][]开始赋值
s[i][j]=i;//s[][]存储各子问题的决策点
for(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;
}
}
}
}
}
void print(int i,int j)
{
if(i == j)
{
cout<<"A["<<i<<"]";
return;
}
cout<<"(";
print(i,s[i][j]);
print(s[i][j]+1,j);//递归1到s[1][j]
cout<<")";
}
int main()
{
cout<<"请输入矩阵的个数n : "<<endl;
cin>>n;
int i,j;
cout<<"请依次输入每个矩阵的行数和最后一个矩阵的列数:"<<endl;
for(i=0;i<=n;i++)
cin>>p[i];
matrixchain();
print(1,n);
cout<<endl;
cout<<"最小计算量的值为:"<<m[1][n]<<endl;
return 0;
}
总结
`东塔规划的时间复杂度为O(n3),远远优于穷举搜索法
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)