矩阵连乘积问题 动态规划算法
矩阵连乘积问题 动态规划算法
动态规划
动态规划问题的特征
动态规划算法的有效性依赖于问题本身所具有的两个重要性质：
1.最优子结构
当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质
2.子问题重叠
在使用递归算法自顶向下求解问题时，产生的子问题并不总是新问题，有些子问题被反复计算过，动态规划算法(自底向上)正是利用了子问题重叠性质，对每个子问题只解一次。
动态规划法的步骤
- 找出最优解的性质，并刻画其结构特征；
- 递归地定义最优值（写出动态规划方程）；
- 以自底向上的方式计算出最优值；
- 根据计算最优值时得到的信息，构造一个最优解（自顶向下，递归）。
矩阵连乘积问题
已知：给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，
计算：这n个矩阵的连乘积A1A2…An所需要的乘法运算的次数的最小值。
分析
矩阵相乘的条件：第一个矩阵的列数=第二个矩阵的行数
因为矩阵乘法符合结合律，所以在计算ABC时，有两种方案，即(AB)C和A(BC)。对于第一方案(AB)C，计算：
其乘法运算次数为：2×3 ×2=12
其乘法运算次数为：2×2×4=16。
乘法运算次数的总计算量为：12+16=28
############################################################
对第二方案 A(BC)，计算
其乘法运算次数为：3×2×4=24
其乘法运算次数为：2×3×4=24。
乘法运算次数的总计算量为：24+24=48
由此可以知道，不同方案的乘法运算量可能相差很悬殊。
动态规划法 求解
分析最优解结构
将矩阵连乘积AiAi+1…Aj 简记为A[i:j], 这里i≤j;
考察计算A[1:n]的最优计算次序。
设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1≤k<n
则其相应完全加括号方式为(A1A2…Ak)(Ak+1Ak+2…An) 计算量（乘法计算的次数）=： A[1:k]的计算量+
A[k+1:n]的计算量+
A[1:k]和A[k+1:n]相乘的计算量
特征：计算A[1:n]的最优次序所包含的计算矩阵子链
A[1:k]和A[k+1:n]的次序也是最优的。
最优子结构的证明： （反证法）
如果A[1:k]不是最优，即存在1…k的另一种计算方法，
使得矩阵1…k连乘的次数小于A[1:k]
则，
意味着存在一个更优的计算次序，比A[1：n]更小
即 A[1：n]不是最优计算次序。
这与已知矛盾。
建立递归关系
矩阵相乘的条件：第一个矩阵的列数=第二个矩阵的行数
设计算A[i: j]（1≤i≤j≤n）所需要的最少乘法次数为m[i][j]，则原问题的最优值为m[1][n] 。
当i=j时，A[i: j]=Ai，因此，m[i][i]=0 ， i=1,2,…,n
当i<j 时，
（Ai的维数是Pi-1×Pi）
可以递归地定义m[i][j]为
k的位置只有 j-i 种可能
计算最优值
- 根据矩阵连乘的计算特点，按照矩阵链长度递增的方法完成矩阵连乘所需的乘法计算次数的计算(m[][])
- 先计算长度是1的矩阵链（即一个矩阵连乘）所需要的乘法运算次数（n）
- 再计算长度是2的矩阵链的乘法运算所需的乘法运算次数m[1][2],m[2][3],m[3][4]……(n-1)
- 再计算长度是3的矩阵链的乘法运算所需的乘法运算次数
m[1][3],m[2][4],m[3][5]………….
-最优值的计算次序
算法计算矩阵连乘积的动态规划算法
#define NUM 51
int p[NUM];//记录矩阵的行列数的值，p[0]记录第一个矩阵行数，之后的数组分量依次记录其他矩阵的列数。数组分量的个数等于矩阵的个数+1
int m[NUM][NUM];//状态，记录子问题的最优值
int s[NUM][NUM];//记录子问题的最优解
void MatrixChain (int n){
for (int i=1; i<=n; i++) m[i][i] = 0;//长度是1的矩阵链连乘的计算次数
for (int r=2; r<=n; r++)//矩阵链的长度，按照矩阵链长度递增的方法完成计算
for (int i=1; i<=n-r+1; i++) { //连乘的起点
int j=i+r-1; //矩阵链中的最后一个矩阵的编号
m[i][j] = m[i+1][j]+p[i-1]*p[i]*p[j]; //m[i][j]的假设值
s[i][j] = i; //断开位置的初值，记录即最优解的初值
//计算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;}
}
}
}
构造最优解
最优解的计算过程
1-6(i,j) ((A1A2A3A4)(A5A6))
1-4(i,j) (A1(A2A3A4)) (A2(A3A4))
5-6(i,j)
……
如果 i==j,
输出Ai
否则 ，
输出(
计算 (i,s[i][j])
计算(s[i][j]+1,j)
输出 )
void TraceBack(int i, int j) {
if(i==j) cout<<"A "<< i;
else
{
cout<<"(";
TraceBack(i,s[i][j]);
TraceBack(s[i][j]+1,j);
cout<<")";
}
}