首页 > 代码库 > 0815------算法笔记----------矩阵连乘问题
0815------算法笔记----------矩阵连乘问题
1.矩阵连乘问题的定义
1.1 给定 n 个矩阵的连乘积 A1A2...An，因为矩阵乘法满足结合律，所以计算矩阵的连乘积可以有不同的计算次序（这个次序的组合数满足卡特兰数），采用不同的计算次序计算的数乘次数也不相同。例如，A1A2A3，这三个矩阵的维数分别是10*100,100*5，和5*50，若先计算A1A2，总的计算次数为10*100*5+10*5*50 = 7500，然而先计算A2A3，总的计算次数为 100*5*50 + 10*100*50 = 75000，可见计算数乘次数相差10倍。这里我们用加括号的方式来表示矩阵的计算次序。每一种完全加括号方式对应一种矩阵的计算次序；
1.2 什么是完全加括号的矩阵连乘积？完全加括号的矩阵连乘积可以递归的定义为(见《计算机算法分析与设计》)：
a）单个矩阵是完全加括号的；
b）矩阵连乘积 A 是完全加括号的，则 A 可以表示为 2 个完全加括号的矩阵连乘积 B 和 C 的乘积并加括号，即 A =(BC)。
2.矩阵连乘问题的求解
2.1 设矩阵连乘积A1A2...An，Ai的维数分别为 p[i-1]*p[i]，m[i][j]为AiAi+1...Aj的最少数乘次数，它满足下述递归关系:
a)m[i][j] = 0 , i == j;
b)m[i][j] = min{m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]}, i<= k < j;
2.2 根据上述递归式可以写出本问题的递归方法，这里为了求出最终的计算次序，需要用一个二维数组 s 保存每次断开的位置。
#include <iostream>#include <string>#include <vector>#include <string.h>#define MAX 100using namespace std;int MatrixChain(int i, int j, int *p, int (*m)[MAX], int (*s)[MAX]);void TraceBack(int i, int j, int (*s)[MAX]);int main(int argc, const char *argv[]){ int p[MAX], m[MAX][MAX], s[MAX][MAX]; int n; cin >> n; //矩阵的个数 int i ; for(i = 0; i <= n; i++){ //相乘矩阵链的行列数 cin >> p[i]; } memset(m, -1, sizeof m); MatrixChain(1, n, p, m, s); TraceBack(1, n, s); cout << endl; return 0;}int MatrixChain(int i, int j, int *p, int (*m)[MAX], int (*s)[MAX]){ if(m[i][j] != -1) return m[i][j]; if(i == j) return 0; else{ int k, min = 1000000; for(k = i; k < j; k++){ m[i][k] = MatrixChain(i, k, p, m, s); m[k+1][j] = MatrixChain(k+1, j, p, m, s); int tmp = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]; if(tmp < min){ min = tmp; s[i][j] = k; } } return min; }}void TraceBack(int i, int j, int (*s)[MAX]){ if(i == j){ cout << "A" << i; return; } cout << "("; TraceBack(i, s[i][j], s); cout << "*"; TraceBack(s[i][j] + 1, j, s); cout << ")";}2.3 矩阵连乘的非递归方法其实就是一个填充表格的过程，以6个矩阵的乘积为例，矩阵的维度分别为p[] = {30, 35, 15, 5, 10, 20, 25},如下图所示，这里先将 m[i][i] 设置为 0， 之后再以正对角线方向根据上述递归式计算m[1][2],m[2][3]...m[5][6]等等，例如m[2][3] = m[2][2] + m[3][3] + p[1] * p[2] *p[3] = 0 + 0 + 30 * 35 * 15 = 15750,这里只能以2分割, 再例如计算 m[2][5] ，此时要分别计算出 m[2][2] + m[3][5] + p[1] * p[2] * p[5], m[2][3] + m[4][5] + p[1] * p[3] * p[5], 以及 m[2][4] + m[5][5] + p[1] * p[4] * p[5]，然后求其最小值即为 m[2][5]。填充后的表格和源程序如下：
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 15750 | 7875 | 9375 | 11875 | 15125 |
| 2 | 0 | 2625 | 4375 | 7125 | 10500 | |
| 3 | 0 | 750 | 2500 | 5375 | ||
| 4 | 0 | 1000 | 3500 | |||
| 5 | 0 | 5000 | ||||
| 6 | 0 |
#include <iostream>#include <string>#include <vector>#define MAX 100using namespace std;void MatrixChain(int *p, int n, int (*m)[MAX], int (*s)[MAX]);void TraceBack(int i, int j, int (*s)[MAX]);int main(int argc, const char *argv[]){ int p[MAX], m[MAX][MAX], s[MAX][MAX]; int n; cin >> n; //矩阵的个数 int i ; for(i = 0; i <= n; i++){ //相乘矩阵链的行列数 cin >> p[i]; } MatrixChain(p, n, m, s); TraceBack(1, n, s); cout << endl; return 0;}void MatrixChain(int *p, int n, int (*m)[MAX], int (*s)[MAX]){ int i; for(i = 1; i <= n; i++) m[i][i] = 0; int r; //外层循环的次数 for(r = 2; r <= n; r++){ for(i = 1; i<= n - r + 1; i++){ //求解m[i][j] int j = i + r -1; int min = m[i][i] + m[i+1][j] + p[i-1] * p[i] * p[j]; s[i][j] = i; int k; for(k = i + 1; k < j; k++){ int tmp = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if(tmp < min){ min = tmp; s[i][j] = k; } } m[i][j] = min; } }}void TraceBack(int i, int j, int (*s)[MAX]){ if(i == j){ cout << "A" << i; return; } cout << "("; TraceBack(i, s[i][j], s); cout << "*"; TraceBack(s[i][j] + 1, j, s); cout << ")";}
3.小结
3.1 和最长公共子序列问题相同，当我们使用动态规划来求解某一个问题时，这个问题一般都具有两个明显特征，一是最优子结构性质，即问题的最优解包含了子问题的最优解，二是子问题重叠，即在递归求解时，有些子问题被重复计算。
3.2 针对上述子问题重叠的性质，我们使用了备忘录方法，即在递归的过程中将每个子问题的结果保存在数组中，如果下次需要直接从数组中取出，从而避免了重复计算。