备忘录方法和动态规划算法在矩阵连乘问题中的应用

摘要：文章从算法思路、算法步骤、代码实现、时间复杂度和空间复杂度几个方面，介绍了备忘录方法和动态规划算法在矩阵连乘问题中的应用。指出了两种算法的实现方式、计算顺序、空间需求和适用场景的不同点，得出动态规划算法和备忘录方法都是解决优化问题的有效工具。

关键词：矩阵连乘；备忘录；动态规划算法；优化问题

中图分类号：TP301.6 文献标识码：A

文章编号：1009-3044（2025）02-0050-03 开放科学（资源服务） 标识码（OSID） ：

1 矩阵连乘问题

矩阵连乘问题是指给定n 个矩阵A1，A2，...，An ，通过加括号来确定一种最优的计算顺序，使得计算这些矩阵乘积所需的乘法次数最少[1]。矩阵乘法不满足交换律，所以不同的计算顺序会得到不同的结果。但矩阵乘法满足结合律，对于三个矩阵 A、B、C，（A×B）×C = A×（B×C）。不同的计算顺序在计算量上可能会有很大差异。例如，有三个矩阵A1 （p0×p1） 、A2 （p1×p2） 和 A3（p2× p3） ，不同的计算顺序会导致不同的乘法次数。（A1 A2） A3的计算次数=p0×p1×p2+p0×p2×p3、A1（A2A3） 的计算次数= p1×p2×p3+p0×p1×p3。若A1（2×3）、A2（3×4）、A3（4×2），则（A1 A2） A3的计算次数=2×3×4+2×4×2=40，A1（A2A3） =3×4×2+2×3×2=36，所以A1（A2A3） 计算顺序的计算次数最少。

矩阵连乘广泛应用于图形变换、神经网络和数据降维等领域。在处理大规模矩阵连乘时，最小化计算次数能够明显减少乘法运算量。例如，在计算机图形学中对3D 模型进行先旋转再平移操作时，可以通过矩阵连乘来表示。假设有一个3D 模型，其顶点坐标用齐次坐标（x，y，z）表示，模型空间中的一个点P用齐次坐标表示为（x，y，z，1）。若对其进行绕z 轴旋转α角度，则其旋转矩阵Rz为：

然后考虑将其平移，沿x轴方向平移距离为tx，沿y 轴方向平移距离为ty，沿z轴方向平移距离为tz，则平移矩阵T 为：

则P 点经过先旋转再平移得到的点P’=Rz×T×P[2]，如果能找到三个矩阵的最小计算次数的连乘顺序，就可以大大缩短此3D模型渲染的时间。

2 动态规划算法在矩阵连乘问题中的应用

2.1 算法定义

动态规划（Dynamic Programming） 是一种用于解决具有重叠子问题和最优子结构性质问题的算法策略。它通过保存子问题的解来避免重复计算，从而提高算法的效率[3]。

最优子结构：一个问题的最优解可以由其子问题的最优解构建而成。例如，在计算斐波那契数列时，F[n]=F[n-1]+F[n-2]，这体现了最优子结构特性。

重叠子问题：解决问题时会多次遇到相同的子问题。以斐波那契数列为例，计算 F （n） 时会多次计算 F （n - 1）、F （n - 2） 等子问题，子问题的重复计算会导致效率低下，而动态规划可以有效地解决这个问题。

动态规划算法在资源分配、编辑距离问题、最长递增子序列问题、矩阵链乘法问题、股票买卖问题等方面都有广泛的应用。本文以矩阵链乘法为例，介绍动态规划算法的具体应用。

2.2 算法思路

1） 定义状态。用二维数组 m[i][j] 表示计算矩阵Ai 到Aj 的最少乘法次数。

2） 确定状态转移方程。将矩阵序列划分为两部分，即 Ai 到 Ak 和 Ak+1 到 Aj ， 则有： m[i][ j] =mini⩽k lt; j {m[i][k] + m[k + 1][ j] + pi - 1 pk }，其中pi - 1是矩阵Ai 的行数， pk 是矩阵 Ak+1 的行数，pj 是矩阵 Aj 的列数[3]。

3） 确定边界条件。当 i=j 时，m[i][i]=0，即只有一个矩阵，因为一个矩阵自身不需要进行乘法运算。

4） 确定计算顺序。按照矩阵链的长度从短到长进行计算。先计算长度为 2 的子问题，然后是长度为3 的子问题，以此类推，直到计算出整个矩阵链的最优解。

2.3 算法步骤

1） 使用一维数组p来存储矩阵序列的维度信息，其中p0是第一个矩阵的行数， p1是第一个矩阵的列数，同时也是第二个矩阵的行数，以此类推。

2） 创建二维数组 m，用于存储子问题的最优解。初始化m[i][i]=0，对于所有的i。

3） 计算长度为 2 的矩阵相乘，即m[i][i+1]，对于i=1，2，...，n-1 。

4） 逐步增加矩阵链的长度3=

2.4 代码实现

def matrix_chain_order（p）：

n = len（p） - 1

m = [[0] * （n + 1） for _ in range（n + 1）]

for l in range（2， n + 1）：

for i in range（1， n - l + 2）：

j = i + l - 1

m[i][j] = float（'inf'）

for k in range（i， j）：

q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]

if q lt; m[i][j]：

m[i][j] = q

return m[1][n]

2.5 时间复杂度和空间复杂度

时间复杂度：O（n3） ，其中n是矩阵的个数。因为需要计算n2个状态，每个状态的计算需要O（n） 的时间。

空间复杂度：O（n2） ，用于存储二维数组m。

动态规划算法通过分析问题的最优子结构和子问题重叠性质，有效地解决了矩阵连乘问题，避免了重复计算，提高了计算效率。

3 备忘录在矩阵连乘问题中的应用

3.1 备忘录的作用

备忘录（Memoization） 是一种优化技术，它是动态规划算法的一个变形。

备忘录方法用一个表格来保存已解决的子问题答案，当再次遇到该子问题时，只须查看该子问题的答案，无须再进行重复计算。与动态规划算法不同的是，备忘录方法采用的自顶向下的递归方式，而动态规划算法采用的自底向上的非递归方式[4]。通过使用备忘录来记录子问题的解，可以有效地减少计算量。在矩阵连乘问题中，由于不同的子问题可能会被多次求解，使用备忘录可以大大提高算法的效率。

3.2 实现方法

1） 定义备忘录表。创建一个二维数组m[i][j] ，用于存储子问题Ai 到Aj 的最优解，即最少的乘法次数。

2） 初始化备忘录表。当 i=j 时，m[i][i]=0 时，因为一个矩阵自己相乘的次数为 0。

3） 递归定义最优值。m[i][ j]=mini⩽k

4） 填充备忘录表。从较小的子问题开始，逐步计算并填充备忘录表，直到求解出整个问题的最优解。

3.3 算法步骤

1） 输入矩阵序列的维度信息，存储在数组p中，其中p0是第一个矩阵的行数， p1是第一个矩阵的列数，同时也是第二个矩阵的行数，以此类推。

2） 创建备忘录表，即一个二维数组 ，用于存储子问题的最优解。初始时，将所有元素设置为无穷大，表示尚未求解，并初始化对角线元素为 0。

3） 按照矩阵链的长度从 2 开始逐步增加，计算并填充备忘录表。

4） 对于长度为l 的矩阵链，遍历所有可能的划分点k ，计算m[i][j]的值。

在计算m[i][j]时，首先检查m[i][j]是否已经被计算过。如果已经计算过，则直接返回结果；否则，进行计算并将结果存储在m[i][j]中。最终m[l][n]即为矩阵连乘的最少乘法次数。

3.4 代码实现

def matrix_chain_order（p）：

n = len（p） - 1

m = [[float（'inf'）] * n for _ in range（n）]

return lookup_chain（m， p， 0， n - 1）

def lookup_chain（m， p， i， j）：

if m[i][j] lt; float（'inf'）：

return m[i][j]

if i == j：

m[i][j] = 0

else：

for k in range（i， j）：

q = lookup_chain（m， p， i， k） + lookup_chain（m， p， k+ 1， j） + p[i] * p[k + 1] * p[j + 1]

if q lt; m[i][j]：

m[i][j] = q

return m[i][j]

3.5 时间复杂度和空间复杂度

时间复杂度：O（n3） ，其中n是矩阵的个数。

空间复杂度：O（n2） ，用于存储备忘录表。

备忘录方法通过记录子问题的解，避免了重复计算，有效地解决了矩阵连乘问题。

4 算法比较

动态规划算法通常采用自底向上的方式，通过填充二维数组m来逐步求解问题[5]。首先计算两个矩阵相乘的乘法次数，然后利用这些小问题的解来，逐步计算三个、四个等更多矩阵相乘的最优乘法次数，最终得到整个矩阵链的最优乘法次数，即原问题的解。

备忘录方法通过递归调用并结合备忘录，即存储已计算子问题结果的二维数组m来求解问题。在递归过程中，对于矩阵连乘问题，在计算Ai 到Aj 的乘法次数时，先检查备忘录中是否已经存储了该子问题的结果。如果没有，就递归地计算不同划分点下的乘法次数，并选择最小的结果存入备忘录[6]。与动态规划法相比，备忘录法的状态转移方程和计算逻辑基本相同，只是计算顺序有所不同。动态规划法是自底向上计算，而备忘录法是自顶向下计算。备忘录方法结合了递归的简洁性和动态规划避免重复计算的优点，在一些情况下，代码结构可能更直观，具体的比较如表1 所示。

5 图形变换中的矩阵连乘应用

在图形学中，图形的变换（如平移、旋转、缩放等） 可以通过矩阵乘法来实现。例如，二维平面上的一个点（x，y）经过一个2×2的变换矩阵后的新坐标（x'，y'）可以通过[x' y']"= M [x y ]来计算。复杂的图形变换往往是多个基本变换矩阵的连乘。

假设有三个图形变换矩阵A1（2×3）、A2（3×4）、A3（4×2）。具体的计算示意图如图1所示。

首先，根据边界条件，m[1][1]=m[2][2]=m[3][3]=0。

计算子矩阵的链长度为2的情况：

m[1][2]=p0p1p2=2×3×4=24

m[2][3]=p1p2p3=3×4×2=24

计算子矩阵的链长度为3的情况：

m[1] [3] =min{m[1] [1] +m[2] [3] +p0p1p3， m[1] [2] +m[3][3]+p0p2p3}

=min{0+24+2×3×2，24+0+2×4×2}

=min{36，40}=36

具体的计算次数如表2 所示，计算顺序如表3 所示。

所以，由表2可知A1（2×3）、A2（3×4）、A3（4×2）连乘的最小计算量为36，由表3可知最优的矩阵连乘顺序是A1（A2A3）。在图形变换中，按照这个顺序进行矩阵连乘可以减少计算量，提高图形变换的效率。

矩阵连乘还可用于组合图像变换，如连续旋转和平移。前文中提到将3D模型中的一点P（x，y，z，1）先绕z 轴旋转α度，得到旋转矩阵Rz；再沿x轴方向平移tx，沿y轴方向平移ty，沿z轴方向平移tz，得到平移矩阵T，变换后结果P’=Rz×T×P。

可以选择的计算顺序有Rz×（T×P）和 （Rz×T）×P，根据具体的旋转角度和平移距离，能算出最小的计算次数。

利用矩阵连乘还可以优化图像变换计算的效率，即减少重复计算。例如，对于三个矩阵A1 （p0×p1） 、A2 （p1×p2） 和 A3（p2×p3） ，根据矩阵乘法结合律（A1×A2）×A3=A1×（A2×A3），但是两种计算顺序的乘法运算次数不同。在实际的图像变换中，涉及的矩阵可能更多，合理安排矩阵连乘的顺序可以显著减少计算量。

6 总结

在矩阵连乘问题中，动态规划算法和备忘录都可以有效地解决最优计算顺序的问题。备忘录方法的空间需求通常相对较小，对于矩阵连乘问题，备忘录只需要一个二维数组存储不同区间的子问题的最优乘法次数。动态规划算法需要用二维数组来存储所有子问题的解，空间复杂度取决于问题的规模[7]。对于矩阵连乘问题，其空间需求可能会比备忘录算法略大，因为它需要存储所有可能的子问题的解。如果问题的规模不是很大，或者递归求解比较直观，备忘录方法可以快速实现并得到较好的效果。当矩阵的数量较多时，动态规划算法能够高效地求解最优乘法次数，并且可以通过分析表格中的结果得到最优的乘法顺序。

矩阵连乘问题也可以使用基于分治策略的并行算法，将矩阵链A1 × A2 × ...×An 划分为大致相等的两个子链。例如，对于n=8的矩阵链，划分为A1 × A2 × A3 × A4 和A5 × A6 × A7 × A8 两个子链。使用两个处理器同时计算两个子链的乘积，一个处理器计算子链A1 × A2 × A3 × A4 的乘积，得到结果矩阵B1；另一个处理器计算子链A5 × A6 × A7 × A8 的乘积，得到结果矩阵B2。再使用一个处理器计算B1×B2得到最终结果[8]。由于并行算法的加速比和效率，既和使用的处理器个数有关，还和数据划分的开销有关，所以此算法解决矩阵连乘问题也有待改进。

参考文献：

[1] 苏旺辉，刘海涛，谢继国.求解矩阵连乘最小乘法次数的一个自底向上算法[J].甘肃高师学报，2008，13（2）：16-17.

[2] 李野，童小念.矩阵乘并行算法的仿真与性能分析[J].现代计算机（专业版），2008（9）：20-22.

[3] 王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2007.

[4] 王秋芬，赵刚彬.算法设计与分析：基于C++编程语言的描述[M].北京：清华大学出版社，2023.

[5] 刘文强，周波，桑海涛，等.算法分析与设计课程中矩阵连乘问题的教学探讨[J].教育教学论坛，2016（18）：206-208.

[6] 赵雪岩，徐继明，陈景森.最值吸收算法解决矩阵连乘次序问题[J].西安工程大学学报，2013，27（6）：827-830.

[7] 周浩慧.两种矩阵连乘动态规划优化算法对比分析[J].长春理工大学学报（自然科学版），2010，33（8）：61-62.

[8] 武铮.面向申威异构众核处理器的高效矩阵乘并行算法研究[D].合肥：中国科学技术大学，2023.

【通联编辑：梁书】

基金项目：基于知识图谱的线上一流课程《高级语言程序设计》