【动态规划】矩阵链乘法——算法设计与分析-Toy模板网

这篇具有很好参考价值的文章主要介绍了【动态规划】矩阵链乘法——算法设计与分析。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、问题定义

1.1 矩阵乘法

对于矩阵 $U_{p\times q}$ 和 $V_{q\times r}$ ， $Z_{p\times r}=UV$ ，共需计算 $pq r$ 次标量乘法，时间复杂度为 $\Theta (pqr)$

矩阵乘法满足结合律，即 $(U V) W = U (VW)$ ，选择不同的结合顺序，会对计算的次数产生巨大的影响。

1.2 矩阵链乘法问题

$n$ 个矩阵相乘称为矩阵链乘法，问题在于如何确定相乘顺序，以提高计算效率？

形式化定义如下：

输入：

$n$ 个矩阵组成的矩阵链 $U_{1..n}=<U_1,U_2,...,U_n>$

矩阵链 $U_{1..n}$ 对应的维度数分别为 $p_0,p_1,...,p_n$ ， $U_i$ 的维度为 $p_{i-1}\times p_i$

输出：

找到一种添加括号的方式，以确定矩阵链乘法的计算顺序，使得最小化矩阵链标量乘法的次数

二、求解策略

显然，最优矩阵链乘法加括号的组合中，任意一部分均为最优，具有最优子结构性质，尝试动态规划求解。

2.1 分析问题结构

形式化表示问题：

$D [i, j]$ ：计算矩阵链 $U_{i..j}$ 所需标量乘法的最小次数

原问题：

$D [i, n]$ ：计算矩阵链 $U_{1..n}$ 所需标量乘法的最小次数

2.2 建立递推关系

以长度为4的矩阵链为例辅助思考， $U=U_1U_2U_3U_4$

对其进行加1个括号的操作，有以下几种方式：
$U=(U_1)(U_2U_3U_4)\Rightarrow D[1,4]=D[1,1]+D[2,4]+p_0p_1p_4\\ U=(U_1U_2)(U_3U_4)\Rightarrow D[1,4]=D[1,2]+D[3,4]+p_0p_2p_4\\ U=(U_1U_2U_3)(U_4)\Rightarrow D[1,4]=D[1,3]+D[4,4]+p_0p_3p_4$
而 $D [1, 4]$ 结果只需要在这3种方式中取得最大值即可。

我们不妨来看一下，求得 $D [1, 4]$ 需要哪些数据：

	1	2	3	4
1	？	？	？	目标
2				？
3				？
4				？

再次观察，对角线上的元素表示矩阵自身，不需要进行运算，所以值均为0。而左下三角的矩阵并没有实际含义，因为 $j\ge i$ ，故当前表格更新为下表所示：

	1	2	3	4
1	0	？	？	目标
2	NULL	0		？
3	NULL	NULL	0	？
4	NULL	NULL	NULL	0

相信大家已经看出递推关系。

对于矩阵链 $U_{i..j}$ ，求解 $D [i, j]$ 时，为了不遗漏最优分割位置，需要枚举所有可能位置 $i, i + 1, .., j - 1$ ，一共 $j - i$ 种。

假设在 $k$ 处进行分割，分为 $U_{i..k}$ 和 $U_{k+1..j}$ 两部分，前者的维度为 $p_{i-1} \times p_k$ ，后者的维度为 $p_k\times p_j$ ，将两部分进行乘积时，需要额外增加 $p_{i-1}\times p_k \times p_j$ 的计算次数。

因此， $D[i,j]=\min_{i\leq k <j} \left \{ D[i,k]+D[k+1,j]+p_{i-1}p_kp_j \right \}$

2.3 自底向上计算

采用图中的方向进行计算：

矩阵链乘法算法,算法设计与分析,算法,矩阵,动态规划

许多教材中习惯将其逆时针旋转45度，以方便观察，在于个人习惯。

矩阵链乘法算法,算法设计与分析,算法,矩阵,动态规划

2.4 追踪最优方案

构造追踪数组 $R ec [1.. n, 1.. n]$ ， $R ec [i, j]$ 表示矩阵链 $U_{i..j}$ 的最优分割位置（一次分割）。

在计算 $D [i, j]$ 的过程中，选出最小的 $k$ ，记录 $R ec [i, j] = k$

追踪时，从 $R ec [1, n]$ 出发，假设 $R ec [1, n] = k$ ，则说明在 $U_k$ 处进行了分割，分为矩阵链 $D [1, k]$ 和 $D [k + 1, n]$ ，再分别查看 $R ec [1, k]$ 和 $R ec [k + 1, n]$ ，便找到两部分的分割地方。如此寻找直至对角线部分。