动态规划之矩阵连乘问题
1. 问题描述
给定\(n\)个矩阵\({A_1, A_2,\ldots,A_n}\)，其中\(A_i\)与\(A_{i+1}\)是可乘的\((i = 1, 2,\ldots, n - 1)\)，矩阵\(A_i\)的维数为\(p_{i-1}*p_i, i=1, 2,\ldots,n\)。考察这\(n\)个矩阵的连乘积\(A_1A_2\ldots A_n\)。要求通过添加括号使得矩阵连乘时，数乘次数最少。例如连乘积\(A_1A_2A_3A_4\)可以有以下5中完全加括号方式：\((A_1(A_2(A_3A_4)))\)，\((A_1((A_2A_3)A_4))\)，\(((A_1A_2)(A_3A_4))\)，\(((A_1(A_2A_3))A_4))\)，\((((A_1A_2)A_3)A_4)\)
2.问题分析
2.1 分析最优解的结构
将矩阵连乘\({A_i, A_{i+1},\ldots,A_j}\)简记为\(A[i:j]\)。为考察计算\(A[1:n]\)的计算次序，设这个计算次序在矩阵\(A_k(1\le k<n)\)和\(A_{k+1}\)之间将矩阵链断开，则其相应的完全加括号方式为\(((A_1,\ldots, A_k)(A_{k+1}, A_n))\)。以此次序，先计算\(A[1:k]\)和\(A[k+1:n]\)，再计算结果相乘，得到总得计算顺序为：\(A[1:k]\)的计算量加上\(A[k+1:n]\)的计算量，再加上\(A[1:k]\)和\(A[k+1:n]\)相乘的计算量。
2.2建立递推关系
对于矩阵连乘积的最优计算次序问题，设计算\(A[i:j](1\le i\le j\le n)\)，所需的最少数乘次数为\(m[i][j]\)，则原问题的最优值为\(m[1][n]\)。
当\(i = j\)时，\(A[i:j]=A_i\)为单一矩阵，无须计算，因此\(m[i][i] = 0 (i = 1, 2,\ldots, n)\)。
当\(i < j\)时，利用最优子结构心知来计算\(m[i][j]\)。若\(A[i:j]\)的最优次序在 \(A_k(i\le k<j)\)和\(A_{k+1}\)之间断开，则\(m[i][j] = m[i][k] + m[k+1][j] + p_{i-1}p_kp_j\)。
从而，\(m[i][j]\)可以递归定义为：
2.3计算最优值
动态规划算法MatrixChain中，输入参数\(p_0,p_1,\ldots,p_n\)存储于数组\(p\)中。除了输入最优值数组\(m\)，算法还输出记录最优断开位置的数组\(S\)。
void MatrixChain(int *p, int n, int **m, int **s) {
// 求解规模为1的子问题，即一个矩阵相乘的数乘次数
for (int i = 1;i <= n;i++)
m[i][i] = 0;
// 规模控制，控制规模从2到n个矩阵相乘的数乘次数
for (int r = 2;r <= n;r++) {
// 规模为r的子问题个数。i是对应的子问题的首矩阵的编号，j是以i开始的规模为r的子问题的结果矩阵编号
for (int i = 1;i <= n - r + 1;i++) {
int j = i + r - 1;
// 求解在i出断开时，矩阵数乘次数。s[i][j]记录断开位置
m[i][j] = m[i + 1][j] + p[i - 1] * p [i] * p[j];
s[i][j] = i;
// 控制不同断开方式下，最优值求解
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 (m[i][j] > t) {
m[i][j] = t;
s[i][j] = k;
}
}
}
}
}
例题分析:
要计算矩阵连乘积\(A_1A_2A_3A_4A_5A_6\)，其中各矩阵的维数分别如下表：
2.4 构造最优解
算法MatrixChain记录了构造最优解所需的全部信息。\(S[i][j]\)中的数表明，计算矩阵链\(A[i:j]\)的最佳方式是在矩阵\(A_k\)和\(A_{k+1}\)之间断开，即最优加括号方式为\((A[i:k])(A[k+1:j])\)。而\(A[1:s[1][n]]\)的最优加括号方式为\((A[1:s[1][n]])(A[s[1][n]+1:n])\)。算了，直接看代码吧......
void Traceback(int i, int j, int **s) {
if (i == j)
return ;
Traceback(i, s[i][j], s);
Traceback(s[i][j] + 1, j, s);
cout << "Multiply A" << i << ", " << s[i][j];
cout << " and A" << (s[i][j] + 1) << ", " << j << endl;
}