本文共 2756 字，大约阅读时间需要 9 分钟。
矩阵连乘问题（Matrix Multiplication Order Problem / Chain Matrix Multiplication）
【文中所有标蓝字体为下标】
问题描述：
有 n 个矩阵进行连乘，已知各个矩阵的行列数，问：如何在算式的中间插入合适的括弧，使得乘法的进行次数最少？
问题解释：
一个 m * n 的矩阵与一个 n * p 的矩阵相乘，越需要进行 m * n * p 次乘法。矩阵的乘法虽不满足交换律，但满足结合律?。我们可以通过对矩阵进行合适的结合，使得进行的乘法次数最少。
❗算法分析❗：
用动态规划解决问题分为四个步骤?：
① 定义子问题，并检查是否满足最优子结构；
② 确定求解子问题的次序；
③ 定义决策方程和状态转移方程；
④ 回溯最优解?
首先来定义子问题：在本题中，要求矩阵连乘运算进行的乘法次数最少。假设矩阵 A1 * A2 * A3 * … * An-2 * An-1 * An 的 最优解为 ( A1 * A2 * A3 * A4 * … * Ak ) * (Ak+1 * Ak+2 * … * An-1 * An) ，那么从 A1 到 Ak 呢？从 Ak+1 到 An 呢？它们一定是进行这个问题的最优解(๑•̀ㅂ•́)و✧！这样下来，我们容易想到，子问题 应该定义为： C(i, j) = 计算 Ai * Ai+1 * … * Aj-1 * Aj 的最小代价。而最小子问题 为 i = j时，此时做乘法的矩阵。
所以，状态转移方程为 ：C(i, j) = min(C(i, k) + C(k+1, j) + mi-1 * mk * mj) ?
子问题的次序：bottom-up，自顶向上。
接下来分析另外一个问题，请看下图：
注意上下图中，m[1, n] 指向的位置，别收到旁边一竖列 n → 1 的影响，差点晕了?
注意！?上面的这个矩形图中标灰色的区域，意味着我们可以不用计算?。
上述的矩形图有什么意义呢？m[1, n] gives the optimal solution to the problem → m[1, n]给出了问题的最优解 —— 进行乘法运算的次数。灰色区域的 i 值 大于 j 值，是没有意义的！
回溯最优解：
我们可以用一个二维数组s，s[i][j]记录了切分位置k，同理，下半部分也不要。
下面给出代码✍:
#include#include #include using namespace std;//int min(int, int);/*回溯最优解 s[i][i] 存储 从 i 到 j 的 最优切分位置 */string result(vector > &s, int k1, int k2);int main(){ int num; cout << "请输入矩阵的个数：" << endl; cin >> num; vector > matrix(num, vector (2, 0)); //num行两列的二维向量，用于存储各个矩阵的行列数 cout << "请输入各个矩阵的行列数：" << endl; for (int i = 0; i < num; ++i) { for (int j = 0; j < 2; ++j) { cin >> matrix[i][j]; } } vector > m(num, vector (num, INT_MAX)); //m[i][j]记录问题的最优解, 各个元素初始化为INT_MAX!!! vector > s(num, vector (num, -1)); //s[i][j]回溯问题的最优解 → 记录切分位置k //当 i = j 时, m[i][j] = 0 for (int i = 0; i < num; ++i) { m[i][i] = 0; } //自底向上，对角线方向进行 for (int i = 1; i < num; ++i) //控制沿对角线遍历的次数 √ { for (int j = 0; j < num - i; ++j) //控制每条对角线上元素的个数 √ { int temp = i + j; for (int k = j; k < temp; ++k) { //m[j][temp] = min(m[j][k] + m[k + 1][temp] + (matrix[j][0] * matrix[k][1] * matrix[temp][1]), m[j][temp]); if (m[j][k] + m[k + 1][temp] + (matrix[j][0] * matrix[k][1] * matrix[temp][1]) < m[j][temp]) { m[j][temp] = m[j][k] + m[k + 1][temp] + (matrix[j][0] * matrix[k][1] * matrix[temp][1]); s[j][temp] = k; } } } } //输出最优解 cout << "最小乘法次数：" << endl; cout << m[0][num-1] << endl; //回溯最优解 cout << "分割方法：" << endl; /*for (int i = 0; i < num; ++i) { for (int j = 0; j < num; ++j) { cout << i << ' ' << j << ' ' << s[i][j] << endl; } } cout << endl; cout << endl;*/ cout << result(s, 0, num - 1) << endl; cout << endl; return 0;}//回溯最优解string result(vector > &s, int k1, int k2){ if (k1 == k2) { return string(1, 'A' + k1); } int split = s[k1][k2]; return " ( " + result(s, k1, split) + " * " + result(s, split + 1, k2) + " ) ";}//int min(int x, int y)//{// return x < y ? x : y;//}
转载地址：http://mttai.baihongyu.com/