わたしの部屋

1. 问题描述#

给定矩阵序列 $A_1, A_2, \ldots, A_n$，矩阵相乘顺序不能改变，但可以改变加括号的方式。

目标：找到一种加括号方式，使矩阵连乘的总计算次数最少。

需要注意的是，矩阵连乘问题不是要求真正算出矩阵乘积，而是要求找到最优计算顺序。

2. 括号的位置会影响计算次数#

矩阵相乘有一个很容易被忽略的点：先算谁，会改变中间结果的规模。

对于两个矩阵 $A(p \times q)$ 和 $B(q \times r)$，它们相乘需要的计算次数是：

而乘完之后，得到的新矩阵规模是：

中间的 $q$ 只负责“对齐”两个矩阵，真正留下来的只有外侧的 $p$ 和 $r$：

这就带来一个问题：如果有多个矩阵连乘，某一步产生的中间矩阵太大，后面的计算量也会被一起放大。

来看一个例子，维度数组为：

对应 5 个矩阵：

矩阵顺序不能换，仍然只能按 $A_1A_2A_3A_4A_5$ 来乘。但括号可以换，而这正好决定了先算哪一部分。

例如：

可以看到，两种写法的数学结果一样，但计算量不同。

所以，矩阵连乘问题真正关心的不是乘积本身，而是：

先算哪一部分，才能让总计算量最小。

3. 算法策略#

矩阵连乘问题使用：

原因是它满足动态规划的两个特点：

• 最优子结构：整体最优解可以由子问题的最优解组成。
• 重叠子问题：不同括号方式中会反复用到相同的子问题。

例如要求 $A_1A_2A_3$ 的最优计算方式，可以拆成：

或：

每一种断开方式都会产生左右两个子问题。动态规划的思路就是先求小区间的最优值，再逐步推出大区间的最优值。

4. 状态定义#

设矩阵 $A_i$ 的规模为：

其中，$p$ 是维度数组。

例如：

则：

所以，矩阵 $A_i$ 的行数是 $p_{i-1}$，列数是 $p_i$。

这里容易混淆的一点是：

• $A_1, A_2, A_3$ 是矩阵编号，通常从 $1$ 开始。
• $p_0, p_1, p_2, p_3$ 是维度数组下标，通常从 $0$ 开始。

所以才会有：

动态规划中主要使用两张表：$m$ 表和 $s$ 表。

例如：

表示计算 $A_1A_2A_3A_4A_5$ 的最少乘法次数。

如果：

表示最优断点在 $A_4$ 后面：

初始条件为：

因为单个矩阵不需要相乘。

5. 状态转移方程#

要求 $m[i][j]$，也就是要求 $A_i \cdots A_j$ 的最少乘法次数。

可以在某个位置 $k$ 处断开：

其中：

总代价由三部分组成：

所以状态转移方程为：

其中：

• $m[i][k]$ 表示左半部分 $A_i \cdots A_k$ 的最少乘法次数。
• $m[k+1][j]$ 表示右半部分 $A_{k+1} \cdots A_j$ 的最少乘法次数。
• $p_{i-1} \cdot p_k \cdot p_j$ 表示左右两部分最后合并时的乘法次数。
• $k$ 表示当前尝试的断点。

为什么最后合并代价是：

因为一串矩阵相乘后，结果矩阵的规模等于：

所以：

最后合并时，相当于计算：

因此乘法次数为：

用一句话理解这个公式：

枚举所有断点 $k$，把矩阵链分成左右两部分，先算左右两边的最优代价，再加上最后合并的代价，最后取最小值。

6. 算法步骤#

1. 初始化 $m[i][i] = 0$。
2. 按矩阵链长度 $l = 2, 3, \ldots, n$ 从短到长填表。
3. 对每个区间 $[i,\ j]$，枚举断点 $k$。
4. 使用状态转移方程计算当前代价。
5. 如果当前代价更小，就更新 $m[i][j]$，并把断点 $k$ 记录到 $s[i][j]$。
6. 最后，$m[1][n]$ 就是最少乘法次数。
7. 根据 $s$ 表可以还原最优加括号方式。

7. 样例计算#

设维度数组为：

对应矩阵为：

8. 最优值表与决策表#

9. 如何根据 $s$ 表画括号？#

$s[i][j] = k$ 的意思是：

从 $A_i$ 到 $A_j$ 这一段，最优断点在 $A_k$ 后面。

也就是：

画括号时要注意：

• 竖线 $\mid$ 表示“从哪里断开”。
• 括号表示“这一段要先作为一个整体计算”。

所以如果：

表示：

写成括号就是：

不是把竖线写进最终答案，而是把断开的左右两部分合成一个整体。

1
A1 A2 A3 A4 A5
2
        |
3
        k=4
4
        ↓
5
A1 A2 A3 A4 | A5
6

7
A1 A2 A3 A4
8
|
9
k=1
10
↓
11
A1 | A2 A3 A4
12

13
A2 A3 A4
14
|
15
k=2
16
↓
17
A2 | A3 A4
18

19
A3 A4
20
|
21
k=3
22
↓
23
A3 | A4

10. Java 实现#

1
public class MatrixChainMultiplication {
2

3
    static int[][] m; // m[i][j] 表示 Ai 到 Aj 的最少乘法次数
4
    static int[][] s; // s[i][j] 表示最优断点位置
5

6
    public static void matrixChainOrder(int[] p) {
7
        int n = p.length - 1; // 矩阵个数
8

9
        m = new int[n + 1][n + 1];
10
        s = new int[n + 1][n + 1];
11

12
        // 单个矩阵不需要相乘
13
        for (int i = 1; i <= n; i++) {
14
            m[i][i] = 0;
15
        }
16

17
        // len 表示当前矩阵链长度
18
        for (int len = 2; len <= n; len++) {
19
            for (int i = 1; i <= n - len + 1; i++) {
20
                int j = i + len - 1;
21

22
                m[i][j] = Integer.MAX_VALUE;
23

24
                // 枚举断点 k
25
                for (int k = i; k < j; k++) {
26
                    int cost = m[i][k]
27
                            + m[k + 1][j]
28
                            + p[i - 1] * p[k] * p[j];
29

30
                    if (cost < m[i][j]) {
31
                        m[i][j] = cost;
32
                        s[i][j] = k;
33
                    }
34
                }
35
            }
36
        }
37
    }
38

39
    public static void printOptimalParens(int i, int j) {
40
        if (i == j) {
41
            System.out.print("A" + i);
42
        } else {
43
            System.out.print("(");
44
            printOptimalParens(i, s[i][j]);
45
            printOptimalParens(s[i][j] + 1, j);
46
            System.out.print(")");
47
        }
48
    }
49

50
    public static void main(String[] args) {
51
        // p = [2, 3, 6, 4, 2, 7]
52
        // A1: 2×3
53
        // A2: 3×6
54
        // A3: 6×4
55
        // A4: 4×2
56
        // A5: 2×7
57
        int[] p = {2, 3, 6, 4, 2, 7};
58

59
        int n = p.length - 1;
60

61
        matrixChainOrder(p);
62

63
        System.out.println("最少乘法次数：" + m[1][n]);
64

65
        System.out.print("最优加括号方式：");
66
        printOptimalParens(1, n);
67
    }
68
}

运行结果：

1
最少乘法次数：124
2
最优加括号方式：((A1(A2(A3A4)))A5)

11. 总结#

矩阵连乘问题的关键不是计算矩阵乘积，而是寻找最优计算顺序。

核心内容可以概括为：

• 使用动态规划解决。
• $m[i][j]$ 表示 $A_i$ 到 $A_j$ 的最少乘法次数。
• $s[i][j]$ 表示取得最优值时的断开位置。
• $k$ 表示当前尝试的断点。
• $A_i = p_{i-1} \times p_i$。
• 一串矩阵相乘后的规模等于第一个矩阵的行数乘最后一个矩阵的列数。
• 状态转移方程为：

通俗理解就是：

把矩阵链从不同位置切开，分别计算左右两边的最优代价，再加上最后合并的代价，最后选择代价最小的切法。