矩阵乘法问题
问题描述
给定n个矩阵：A1,A2,...,An，其中Ai与Ai+1是可乘的，i=1，2...，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
矩阵乘法的顺序安排
对于图像处理来说，矩阵运行是中必不可少的重要数学方法，另外在神经网络、模式识别等领域也有着广泛的用途。在这里就先来简单复习一下矩阵的相关知识：
矩阵乘法
在矩阵乘法中，第一个矩阵的行数和第二个矩阵的列数必须是相同的。先来看一个简单的例子：
之所以这样要求，是因为矩阵的乘法定义中，就要求了，第一个矩阵每一行和第二个矩阵每一列相对应位置的数字做乘的操作：
如果A矩阵是p×q的矩阵，B是q×r的矩阵，那么乘积C是p×r的矩阵。它们一共计算了p×q×r次。
以下是一段计算两个矩阵乘积的标准算法：
void matrixMultiply(int[][] matrixA, int[][] matrixB,int[][] matrixC,int ra, int ca, int rb, int cb) {
if (ca != cb) {
System.err.println("矩阵不可乘！");
return;
} // end if
for (int i = 0; i < ra; i++) {
for (int j = 0; j < cb; j++) {
int sum = matrixA[i][0] * matrixB[0][j];
for (int k = 0; k < ca; k++) {
sum += matrixA[i][k] * matrixB[k][j];
} // end for
matrixC[i][j] = sum;
}
}
}顺序安排
假设给定3个矩阵，A、B、C，它们的规模分别是10×100、100×5和5×50。
- 如果按照((AB)C)的顺序计算： 为计算AB（规模10×5），需要做10×100×5=5000次标量乘法，再与C相乘又需要做10×5×50=2500次标量乘法， 共需要7500次标量乘法。
- 如果按照(A(BC))的顺序计算： 为计算BC（规模100×50），需要做100×5×50=25000次标量乘法，再与A相乘又需要做10×100×50=50000次标量乘法，共需要75000次标量乘法。
因此，按第一种顺序计算矩阵连乘要比第二种顺序快10倍。所以，进行一些计算来确定最有顺序还是值得的。
动态规划法
设mLeft,Right是进行矩阵乘法ALeftALeft+1···ARight-1ARight所需要的乘法次数。为一致起见，mLeft,Left=0。设最后的乘法是（ALeft···Ai）（Ai+1ARight），其中 Left ≤ i ≤ Right。
此时所用的乘法次数为：mLeft,i + mi+1,Right + cLeft-1cicRight。这三项分别代表计算（ALeft···Ai）、（Ai+1ARight）以及它们的乘积所需要的乘法。除了最后的答案，还要显示实际的乘法顺序，所以我们还要记录i的值，由此得到以下算法：
public static void optMatrix(int[] c, long[][] m, int[][] lastChange) {
int n = c.length - 1;
for (int left = 0; left < n; left++) {
m[left][left] = 0;
}
for (int k = 1; k <= n; k++) {
for (int left = 1; left <= n - k; left++) { // k is right - left，即子问题规模
// For each postion
int right = left + k;
m[left][right] = INFINITY; // 置为无穷大
for (int i = left; i < right; i++) { // i为断开位置
long thisCost = m[left][i] + m[i + 1][right] +
c[left - 1] * c[i] * c[right];
if (thisCost < m[left][right]) { // Update min
m[left][right] = thisCost;
lastChange[left][right] = i;
}
}
} // end inner for
} // end outer for
}这个程序包含三重嵌套循环，容易看出它以O(N3)时间运行。这里其实有更快地算法，但由于执行具体矩阵乘法的时间仍然很可能会比计算最有顺序的乘法的时间多得多，所以这个算法还是挺实用的。