线性动态规划：矩阵连乘问题（Matrix Chain Multiplication）
字数 3569 2025-12-10 09:05:13

线性动态规划：矩阵连乘问题（Matrix Chain Multiplication）

1. 问题描述

给定一系列矩阵 \(A_1, A_2, \dots, A_n\)，其中矩阵 \(A_i\) 的维度为 \(p_{i-1} \times p_i\)（即行数为 \(p_{i-1}\)，列数为 \(p_i\)）。我们需要计算这些矩阵的连乘积 \(A_1 A_2 \dots A_n\)。由于矩阵乘法满足结合律，我们可以通过添加括号来改变计算顺序，不同的计算顺序会导致标量乘法次数的巨大差异。目标是找到一种完全加括号的方式，使得计算该矩阵连乘所需的总标量乘法次数最少。

例如：

  • 矩阵维度：\(A_1: 10 \times 20\)，\(A_2: 20 \times 30\)，\(A_3: 30 \times 40\)，\(A_4: 40 \times 30\)。
  • 如果按 \(((A_1 A_2) A_3) A_4\) 计算，乘法次数为 \(10 \times 20 \times 30 + 10 \times 30 \times 40 + 10 \times 40 \times 30 = 6000 + 12000 + 12000 = 30000\)。
  • 如果按 \((A_1 (A_2 (A_3 A_4)))\) 计算，乘法次数为 \(30 \times 40 \times 30 + 20 \times 30 \times 30 + 10 \times 20 \times 30 = 36000 + 18000 + 6000 = 60000\)。
    可见，不同顺序代价差异很大。

2. 关键概念

  • 标量乘法次数：两个矩阵 \(X\)（维度 \(a \times b\)）和 \(Y\)（维度 \(b \times c\)）相乘，需要 \(a \times b \times c\) 次标量乘法。
  • 完全加括号：每个矩阵乘法对都有明确的括号指定计算顺序。
  • 目标：最小化总标量乘法次数。

3. 动态规划思路

设 \(m[i][j]\) 表示计算从第 \(i\) 个矩阵到第 \(j\) 个矩阵（即 \(A_i A_{i+1} \dots A_j\)）的最小标量乘法次数。
状态转移方程推导：

  • 考虑最后一步乘法发生在某个位置 \(k\)（\(i \le k < j\)），即先计算 \(A_i \dots A_k\) 和 \(A_{k+1} \dots A_j\)，再将两个结果相乘。
  • 设 \(A_i\) 的维度为 \(p_{i-1} \times p_i\)。
  • 计算 \(A_i \dots A_k\) 的最小代价为 \(m[i][k]\)，结果矩阵维度为 \(p_{i-1} \times p_k\)。
  • 计算 \(A_{k+1} \dots A_j\) 的最小代价为 \(m[k+1][j]\)，结果矩阵维度为 \(p_k \times p_j\)。
  • 最后将这两个结果相乘，额外乘法次数为 \(p_{i-1} \times p_k \times p_j\)。
  • 因此：

\[ m[i][j] = \min_{i \le k < j} \left( m[i][k] + m[k+1][j] + p_{i-1} \times p_k \times p_j \right) \]

  • 边界条件：当 \(i = j\) 时，只有一个矩阵，不需要乘法，所以 \(m[i][i] = 0\)。

4. 计算顺序

  • 由于 \(m[i][j]\) 依赖于更短的子链（即区间长度更小的问题），我们应按照区间长度从小到大计算。
  • 设链长度 \(L\) 从 2 到 \(n\)（因为长度 1 代价为 0）。
  • 对每个长度 \(L\)，遍历所有起始点 \(i\)（从 1 到 \(n-L+1\)），则 \(j = i + L - 1\)。
  • 在计算 \(m[i][j]\) 时，遍历所有可能的分割点 \(k\) 从 \(i\) 到 \(j-1\)，取最小值。

5. 示例演算

矩阵维度数组 \(p = [10, 20, 30, 40, 30]\)（对应矩阵 \(A_1\) 到 \(A_4\) 的维度，\(n = 4\)）。

初始化：\(m[i][i] = 0\) 对所有 \(i\)。

长度 L = 2：

  • \(i=1, j=2\)：\(m[1][2] = m[1][1] + m[2][2] + p_0 \times p_1 \times p_2 = 0 + 0 + 10 \times 20 \times 30 = 6000\)。
  • \(i=2, j=3\)：\(m[2][3] = 0 + 0 + 20 \times 30 \times 40 = 24000\)。
  • \(i=3, j=4\)：\(m[3][4] = 0 + 0 + 30 \times 40 \times 30 = 36000\)。

长度 L = 3：

  • \(i=1, j=3\)：
    • \(k=1\)：\(m[1][1] + m[2][3] + 10 \times 20 \times 40 = 0 + 24000 + 8000 = 32000\)。
    • \(k=2\)：\(m[1][2] + m[3][3] + 10 \times 30 \times 40 = 6000 + 0 + 12000 = 18000\)。
    • 最小值 18000，所以 \(m[1][3] = 18000\)。
  • \(i=2, j=4\)：
    • \(k=2\)：\(m[2][2] + m[3][4] + 20 \times 30 \times 30 = 0 + 36000 + 18000 = 54000\)。
    • \(k=3\)：\(m[2][3] + m[4][4] + 20 \times 40 \times 30 = 24000 + 0 + 24000 = 48000\)。
    • 最小值 48000，所以 \(m[2][4] = 48000\)。

长度 L = 4：

  • \(i=1, j=4\)：
    • \(k=1\)：\(m[1][1] + m[2][4] + 10 \times 20 \times 30 = 0 + 48000 + 6000 = 54000\)。
    • \(k=2\)：\(m[1][2] + m[3][4] + 10 \times 30 \times 30 = 6000 + 36000 + 9000 = 51000\)。
    • \(k=3\)：\(m[1][3] + m[4][4] + 10 \times 40 \times 30 = 18000 + 0 + 12000 = 30000\)。
    • 最小值 30000，所以 \(m[1][4] = 30000\)。

最终结果：最小乘法次数为 \(m[1][n] = 30000\)。

6. 构造最优括号方案

可以额外使用数组 \(s[i][j]\) 记录得到 \(m[i][j]\) 时的分割点 \(k\)。之后通过递归回溯，输出完全加括号的表达式。

对于上例，\(s[1][4] = 3\) 表示在 3 处分割，即 \((A_1 A_2 A_3)(A_4)\)。然后递归处理 \(s[1][3] = 2\) 得 \(((A_1 A_2) A_3) A_4\)。

7. 时间与空间复杂度

  • 时间复杂度：三重循环，\(O(n^3)\)。
  • 空间复杂度：\(O(n^2)\) 存储 \(m\) 和 \(s\)。

8. 核心总结

  • 该问题是区间动态规划的经典应用，关键在于定义子问题为“计算从第 \(i\) 到第 \(j\) 个矩阵连乘的最小代价”。
  • 状态转移考虑最后一个乘法发生的位置，将问题划分为两个子链，再加上合并代价。
  • 通过自底向上递推求解，最终得到全局最优解，并可回溯得到括号方案。
线性动态规划：矩阵连乘问题（Matrix Chain Multiplication） 1. 问题描述 给定一系列矩阵 \( A_ 1, A_ 2, \dots, A_ n \)，其中矩阵 \( A_ i \) 的维度为 \( p_ {i-1} \times p_ i \)（即行数为 \( p_ {i-1} \)，列数为 \( p_ i \)）。我们需要计算这些矩阵的连乘积 \( A_ 1 A_ 2 \dots A_ n \)。由于矩阵乘法满足结合律，我们可以通过添加括号来改变计算顺序，不同的计算顺序会导致标量乘法次数的巨大差异。目标是 找到一种完全加括号的方式，使得计算该矩阵连乘所需的总标量乘法次数最少 。 例如： 矩阵维度：\( A_ 1: 10 \times 20 \)，\( A_ 2: 20 \times 30 \)，\( A_ 3: 30 \times 40 \)，\( A_ 4: 40 \times 30 \)。 如果按 \( ((A_ 1 A_ 2) A_ 3) A_ 4 \) 计算，乘法次数为 \( 10 \times 20 \times 30 + 10 \times 30 \times 40 + 10 \times 40 \times 30 = 6000 + 12000 + 12000 = 30000 \)。 如果按 \( (A_ 1 (A_ 2 (A_ 3 A_ 4))) \) 计算，乘法次数为 \( 30 \times 40 \times 30 + 20 \times 30 \times 30 + 10 \times 20 \times 30 = 36000 + 18000 + 6000 = 60000 \)。 可见，不同顺序代价差异很大。 2. 关键概念 标量乘法次数：两个矩阵 \( X \)（维度 \( a \times b \)）和 \( Y \)（维度 \( b \times c \)）相乘，需要 \( a \times b \times c \) 次标量乘法。 完全加括号：每个矩阵乘法对都有明确的括号指定计算顺序。 目标：最小化总标量乘法次数。 3. 动态规划思路 设 \( m[ i][ j] \) 表示计算从第 \( i \) 个矩阵到第 \( j \) 个矩阵（即 \( A_ i A_ {i+1} \dots A_ j \)）的最小标量乘法次数。 状态转移方程推导 ： 考虑最后一步乘法发生在某个位置 \( k \)（\( i \le k < j \)），即先计算 \( A_ i \dots A_ k \) 和 \( A_ {k+1} \dots A_ j \)，再将两个结果相乘。 设 \( A_ i \) 的维度为 \( p_ {i-1} \times p_ i \)。 计算 \( A_ i \dots A_ k \) 的最小代价为 \( m[ i][ k] \)，结果矩阵维度为 \( p_ {i-1} \times p_ k \)。 计算 \( A_ {k+1} \dots A_ j \) 的最小代价为 \( m[ k+1][ j] \)，结果矩阵维度为 \( p_ k \times p_ j \)。 最后将这两个结果相乘，额外乘法次数为 \( p_ {i-1} \times p_ k \times p_ j \)。 因此： \[ m[ i][ j] = \min_ {i \le k < j} \left( m[ i][ k] + m[ k+1][ j] + p_ {i-1} \times p_ k \times p_ j \right) \] 边界条件：当 \( i = j \) 时，只有一个矩阵，不需要乘法，所以 \( m[ i][ i ] = 0 \)。 4. 计算顺序 由于 \( m[ i][ j] \) 依赖于更短的子链（即区间长度更小的问题），我们应按照 区间长度从小到大 计算。 设链长度 \( L \) 从 2 到 \( n \)（因为长度 1 代价为 0）。 对每个长度 \( L \)，遍历所有起始点 \( i \)（从 1 到 \( n-L+1 \)），则 \( j = i + L - 1 \)。 在计算 \( m[ i][ j ] \) 时，遍历所有可能的分割点 \( k \) 从 \( i \) 到 \( j-1 \)，取最小值。 5. 示例演算 矩阵维度数组 \( p = [ 10, 20, 30, 40, 30] \)（对应矩阵 \( A_ 1 \) 到 \( A_ 4 \) 的维度，\( n = 4 \)）。 初始化 ：\( m[ i][ i ] = 0 \) 对所有 \( i \)。 长度 L = 2 ： \( i=1, j=2 \)：\( m[ 1][ 2] = m[ 1][ 1] + m[ 2][ 2] + p_ 0 \times p_ 1 \times p_ 2 = 0 + 0 + 10 \times 20 \times 30 = 6000 \)。 \( i=2, j=3 \)：\( m[ 2][ 3 ] = 0 + 0 + 20 \times 30 \times 40 = 24000 \)。 \( i=3, j=4 \)：\( m[ 3][ 4 ] = 0 + 0 + 30 \times 40 \times 30 = 36000 \)。 长度 L = 3 ： \( i=1, j=3 \)： \( k=1 \)：\( m[ 1][ 1] + m[ 2][ 3 ] + 10 \times 20 \times 40 = 0 + 24000 + 8000 = 32000 \)。 \( k=2 \)：\( m[ 1][ 2] + m[ 3][ 3 ] + 10 \times 30 \times 40 = 6000 + 0 + 12000 = 18000 \)。 最小值 18000，所以 \( m[ 1][ 3 ] = 18000 \)。 \( i=2, j=4 \)： \( k=2 \)：\( m[ 2][ 2] + m[ 3][ 4 ] + 20 \times 30 \times 30 = 0 + 36000 + 18000 = 54000 \)。 \( k=3 \)：\( m[ 2][ 3] + m[ 4][ 4 ] + 20 \times 40 \times 30 = 24000 + 0 + 24000 = 48000 \)。 最小值 48000，所以 \( m[ 2][ 4 ] = 48000 \)。 长度 L = 4 ： \( i=1, j=4 \)： \( k=1 \)：\( m[ 1][ 1] + m[ 2][ 4 ] + 10 \times 20 \times 30 = 0 + 48000 + 6000 = 54000 \)。 \( k=2 \)：\( m[ 1][ 2] + m[ 3][ 4 ] + 10 \times 30 \times 30 = 6000 + 36000 + 9000 = 51000 \)。 \( k=3 \)：\( m[ 1][ 3] + m[ 4][ 4 ] + 10 \times 40 \times 30 = 18000 + 0 + 12000 = 30000 \)。 最小值 30000，所以 \( m[ 1][ 4 ] = 30000 \)。 最终结果：最小乘法次数为 \( m[ 1][ n ] = 30000 \)。 6. 构造最优括号方案 可以额外使用数组 \( s[ i][ j] \) 记录得到 \( m[ i][ j ] \) 时的分割点 \( k \)。之后通过递归回溯，输出完全加括号的表达式。 对于上例，\( s[ 1][ 4] = 3 \) 表示在 3 处分割，即 \( (A_ 1 A_ 2 A_ 3)(A_ 4) \)。然后递归处理 \( s[ 1][ 3] = 2 \) 得 \( ((A_ 1 A_ 2) A_ 3) A_ 4 \)。 7. 时间与空间复杂度 时间复杂度：三重循环，\( O(n^3) \)。 空间复杂度：\( O(n^2) \) 存储 \( m \) 和 \( s \)。 8. 核心总结 该问题是 区间动态规划 的经典应用，关键在于定义子问题为“计算从第 \( i \) 到第 \( j \) 个矩阵连乘的最小代价”。 状态转移考虑最后一个乘法发生的位置，将问题划分为两个子链，再加上合并代价。 通过 自底向上 递推求解，最终得到全局最优解，并可回溯得到括号方案。