动态规划-矩阵连乘问题

矩阵连乘问题描述

• 给定$n$个矩阵$\left\{A_1,A_2,\dots ,A_n\right\}$，其中$A_i$与$A_{i+1}$是可乘的，$i=1,2,3,...,n$
• 考查这$n$个矩阵的连乘积$A_1{A}_2\dots A_n$
• 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定
• 若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用$2$个矩阵相乘的标准算法计算出矩阵连乘积

算法描述

假设我们要计算6个矩阵的连乘积问题，如下：

从连乘矩阵个数为2开始计算每次的最小乘次数$m[i][j]$（为便于理解，矩阵下标从1开始）:

• 连乘矩阵个数为2时：m[1][2]、m[2][3]、m[3][4]、m[4][5]、m[5][6]
• 连乘矩阵个数为3时：m[1][3]、m[2][4]、m[3][5]、m[4][6]
• 连乘矩阵个数为4时：m[1][4]、m[2][5]、m[3][6]
• 连乘矩阵个数为5时：m[1][5]、m[2][6]
• 连乘矩阵个数为6时：m[1][6] //要求最小乘次数
  

动态规划代码实现：

• $p_i$:第$i$个矩阵的行数、$p_k$:$i:k$矩阵连乘后得到的列数，$p_j$:$k+1:j$矩阵连乘后得到的列数
• $m[i][j]$:最小乘次数数组，$s[i][j]$:最优断开位置数组
  例如，在计算m[1][4]时，依据递归式有：
  $m[1][4]=\min \{\begin{array}{l}m[1][1]+m[2][4]+p_0{p}_1{p}_4\\ m[1][2]+m[3][4]+p_0{p}_2{p}_4\\ m[1][3]+m[4][4]+p_0{p}_3{p}_4\end{array}$

void matrixChain(int *p, int n, int m[][N], int s[][N])
{
   
	for (int i = 1; i <= n; i++)
		m[i][i] = 0;
	for (int r = 2; r <= n; r++) //连乘矩阵的规模
	{
   
		for (int i = 1; i <= n - r + 1; i++)
		{
   
			int j = i + r - 1; //j表示连乘矩阵中的最后一个
			// k == i时
			m[i][j] = m[i][i] + m[i + 1][j] + p[i - 1] * p[i] * p[j];
			s[i][j] = i;
			for (int k = i + 1; k < j; k++)
			{
   
				int tmp = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
				if (tmp < m[i][j])
				{
   
					m[i][j] = tmp;
					s[i][j] = k;
				}
			}
		}
	}
}

递归构造最优解：

void traceBack(int i, int j, int s[][N])
{
   
	if (i == j)
		std::cout << "A" << i;
	else
	{
   
		std::cout << "(";
		traceBack(i, s[i][j], s);
		traceBack(s[i][j] + 1, j, s);
		std::cout << ")";
	}
}

测试结果：

对于矩阵连乘问题，常用的还有备忘录方法，与动态规划方法不同的是，备忘录方法是自顶向下的（动态规划方法是自底向上）。两种方法有相似之处，了解一个另一个也很好理解。

参考书：计算机算法设计与分析 第四版 王晓东著