【算法概论】动态规划：矩阵连乘问题

矩阵连乘问题（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 <iostream>
#include <vector>
#include <string>

using namespace std;

//int min(int, int);
/*
回溯最优解
	s[i][i] 存储 从 i 到 j 的 最优切分位置 
*/
string result(vector<vector<int>> &s, int k1, int k2);

int main()
{
	int num;
	cout << "请输入矩阵的个数：" << endl;
	cin >> num;

	vector<vector<int>> matrix(num, vector<int>(2, 0));			//num行两列的二维向量，用于存储各个矩阵的行列数
	cout << "请输入各个矩阵的行列数：" << endl;
	for (int i = 0; i < num; ++i)
	{
		for (int j = 0; j < 2; ++j)
		{
			cin >> matrix[i][j];
		}
	}

	vector<vector<int>> m(num, vector<int>(num, INT_MAX));	//m[i][j]记录问题的最优解, 各个元素初始化为INT_MAX!!!
	vector<vector<int>> s(num, vector<int>(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<vector<int>> &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;
//}

【算法概论】动态规划：矩阵连乘问题

矩阵连乘问题（Matrix Multiplication Order Problem / Chain Matrix Multiplication）

相关推荐