最优矩阵链乘顺序问题（最小化乘法总次数）

字数 3120 2025-12-06 01:37:52

最优矩阵链乘顺序问题（最小化乘法总次数）

题目描述
给定一个矩阵链 \(A_1, A_2, \dots, A_n\)，其中矩阵 \(A_i\) 的维度为 \(p_{i-1} \times p_i\)。我们需要计算这些矩阵的乘积 \(A_1 A_2 \dots A_n\)。由于矩阵乘法满足结合律，我们可以通过添加括号来改变乘法的顺序，但不同的括号化方式会导致总的标量乘法次数不同。目标是找到一种最优的括号化方案，使得计算矩阵链乘所需要的标量乘法总次数最少。

例如，矩阵链的维度数组为 \(p = [10, 20, 30, 40]\)，表示三个矩阵：

\(A_1: 10 \times 20\)
\(A_2: 20 \times 30\)
\(A_3: 30 \times 40\)
有两种括号化方式：

\((A_1 A_2)A_3\): 乘法次数 = \(10 \times 20 \times 30 + 10 \times 30 \times 40 = 6000 + 12000 = 18000\)
\(A_1(A_2 A_3)\): 乘法次数 = \(20 \times 30 \times 40 + 10 \times 20 \times 40 = 24000 + 8000 = 32000\)
最优方案是第一种，最小乘法次数为 18000。

解题步骤

1. 定义状态
设 \(dp[i][j]\) 表示计算矩阵链 \(A_i A_{i+1} \dots A_j\) 所需的最小标量乘法次数。

当 \(i = j\) 时，只有一个矩阵，不需要乘法，所以 \(dp[i][i] = 0\)。
当 \(i < j\) 时，我们需要找到最优的分割点 \(k\)（\(i \le k < j\)），使得 \((A_i \dots A_k)\) 和 \((A_{k+1} \dots A_j)\) 分别计算后再相乘的总乘法次数最小。

2. 状态转移方程
对于区间 \([i, j]\)，如果我们选择在 \(k\) 处分割，即先计算 \(A_i \dots A_k\)（结果为维度 \(p_{i-1} \times p_k\) 的矩阵）和 \(A_{k+1} \dots A_j\)（结果为维度 \(p_k \times p_j\) 的矩阵），再将这两个结果相乘，则乘法次数为：

\[dp[i][k] + dp[k+1][j] + p_{i-1} \times p_k \times p_j \]

其中：

\(dp[i][k]\) 是计算左半部分的最小乘法次数。
\(dp[k+1][j]\) 是计算右半部分的最小乘法次数。
\(p_{i-1} \times p_k \times p_j\) 是合并左右两部分结果所需的乘法次数（因为左矩阵维度为 \(p_{i-1} \times p_k\)，右矩阵维度为 \(p_k \times p_j\)，乘法次数为两维度的乘积）。

我们需要遍历所有可能的 \(k\) 来找到最小值：

\[dp[i][j] = \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] + p_{i-1} \times p_k \times p_j \} \]

3. 计算顺序
区间 DP 通常按区间长度从小到大计算。

长度 \(len = 1\) 时，\(dp[i][i] = 0\)。
长度 \(len = 2\) 时，计算所有长度为 2 的区间（即两个矩阵相乘）。
逐步增加长度，直到 \(len = n\) 覆盖整个矩阵链。

4. 例子演示
以 \(p = [10, 20, 30, 40, 30]\) 为例（4 个矩阵）：
矩阵维度：

\(A_1: 10 \times 20\)
\(A_2: 20 \times 30\)
\(A_3: 30 \times 40\)
\(A_4: 40 \times 30\)

初始化：
\(dp[1][1] = 0, dp[2][2] = 0, dp[3][3] = 0, dp[4][4] = 0\)。

长度 2（两个矩阵相乘）：

\(dp[1][2] = 10 \times 20 \times 30 = 6000\)
\(dp[2][3] = 20 \times 30 \times 40 = 24000\)
\(dp[3][4] = 30 \times 40 \times 30 = 36000\)

长度 3（三个矩阵，有两种分割方式）：

\(dp[1][3]\): 分割点 \(k=1\) 或 \(k=2\)
- \(k=1: dp[1][1] + dp[2][3] + 10 \times 20 \times 40 = 0 + 24000 + 8000 = 32000\)
- \(k=2: dp[1][2] + dp[3][3] + 10 \times 30 \times 40 = 6000 + 0 + 12000 = 18000\)
  取最小值 18000。
\(dp[2][4]\): 分割点 \(k=2\) 或 \(k=3\)
- \(k=2: dp[2][2] + dp[3][4] + 20 \times 30 \times 30 = 0 + 36000 + 18000 = 54000\)
- \(k=3: dp[2][3] + dp[4][4] + 20 \times 40 \times 30 = 24000 + 0 + 24000 = 48000\)
  取最小值 48000。

长度 4（整个链）：

\(dp[1][4]\): 分割点 \(k=1,2,3\)
- \(k=1: dp[1][1] + dp[2][4] + 10 \times 20 \times 30 = 0 + 48000 + 6000 = 54000\)
- \(k=2: dp[1][2] + dp[3][4] + 10 \times 30 \times 30 = 6000 + 36000 + 9000 = 51000\)
- \(k=3: dp[1][3] + dp[4][4] + 10 \times 40 \times 30 = 18000 + 0 + 12000 = 30000\)
  取最小值 30000。

最优乘法总次数为 30000。

5. 复杂度分析

时间复杂度：\(O(n^3)\)，三重循环（长度、起点、分割点）。
空间复杂度：\(O(n^2)\)，用于存储 \(dp\) 表。

6. 扩展：记录括号方案
如果需要输出最优括号化方案，可以用另一个数组 \(s[i][j]\) 记录得到 \(dp[i][j]\) 时的分割点 \(k\)，然后通过递归或栈构造括号表达式。

这个问题的核心是区间 DP 的经典应用，通过枚举分割点将大问题分解为两个子问题，最终得到全局最优解。

最优矩阵链乘顺序问题（最小化乘法总次数）题目描述给定一个矩阵链 \( A_ 1, A_ 2, \dots, A_ n \)，其中矩阵 \( A_ i \) 的维度为 \( p_ {i-1} \times p_ i \)。我们需要计算这些矩阵的乘积 \( A_ 1 A_ 2 \dots A_ n \)。由于矩阵乘法满足结合律，我们可以通过添加括号来改变乘法的顺序，但不同的括号化方式会导致总的标量乘法次数不同。目标是找到一种最优的括号化方案，使得计算矩阵链乘所需要的标量乘法总次数最少。例如，矩阵链的维度数组为 \( p = [ 10, 20, 30, 40 ] \)，表示三个矩阵： \( A_ 1: 10 \times 20 \) \( A_ 2: 20 \times 30 \) \( A_ 3: 30 \times 40 \) 有两种括号化方式： \( (A_ 1 A_ 2)A_ 3 \): 乘法次数 = \( 10 \times 20 \times 30 + 10 \times 30 \times 40 = 6000 + 12000 = 18000 \) \( A_ 1(A_ 2 A_ 3) \): 乘法次数 = \( 20 \times 30 \times 40 + 10 \times 20 \times 40 = 24000 + 8000 = 32000 \) 最优方案是第一种，最小乘法次数为 18000。解题步骤 1. 定义状态设 \( dp[ i][ j] \) 表示计算矩阵链 \( A_ i A_ {i+1} \dots A_ j \) 所需的最小标量乘法次数。当 \( i = j \) 时，只有一个矩阵，不需要乘法，所以 \( dp[ i][ i ] = 0 \)。当 \( i < j \) 时，我们需要找到最优的分割点 \( k \)（\( i \le k < j \)），使得 \( (A_ i \dots A_ k) \) 和 \( (A_ {k+1} \dots A_ j) \) 分别计算后再相乘的总乘法次数最小。 2. 状态转移方程对于区间 \([ i, j]\)，如果我们选择在 \( k \) 处分割，即先计算 \( A_ i \dots A_ k \)（结果为维度 \( p_ {i-1} \times p_ k \) 的矩阵）和 \( A_ {k+1} \dots A_ j \)（结果为维度 \( p_ k \times p_ j \) 的矩阵），再将这两个结果相乘，则乘法次数为： \[ dp[ i][ k] + dp[ k+1][ j] + p_ {i-1} \times p_ k \times p_ j \] 其中： \( dp[ i][ k ] \) 是计算左半部分的最小乘法次数。 \( dp[ k+1][ j ] \) 是计算右半部分的最小乘法次数。 \( p_ {i-1} \times p_ k \times p_ j \) 是合并左右两部分结果所需的乘法次数（因为左矩阵维度为 \( p_ {i-1} \times p_ k \)，右矩阵维度为 \( p_ k \times p_ j \)，乘法次数为两维度的乘积）。我们需要遍历所有可能的 \( k \) 来找到最小值： \[ dp[ i][ j] = \min_ {i \le k < j} \{ dp[ i][ k] + dp[ k+1][ j] + p_ {i-1} \times p_ k \times p_ j \} \] 3. 计算顺序区间 DP 通常按区间长度从小到大计算。长度 \( len = 1 \) 时，\( dp[ i][ i ] = 0 \)。长度 \( len = 2 \) 时，计算所有长度为 2 的区间（即两个矩阵相乘）。逐步增加长度，直到 \( len = n \) 覆盖整个矩阵链。 4. 例子演示以 \( p = [ 10, 20, 30, 40, 30 ] \) 为例（4 个矩阵）：矩阵维度： \( A_ 1: 10 \times 20 \) \( A_ 2: 20 \times 30 \) \( A_ 3: 30 \times 40 \) \( A_ 4: 40 \times 30 \) 初始化： \( dp[ 1][ 1] = 0, dp[ 2][ 2] = 0, dp[ 3][ 3] = 0, dp[ 4][ 4 ] = 0 \)。长度 2 （两个矩阵相乘）： \( dp[ 1][ 2 ] = 10 \times 20 \times 30 = 6000 \) \( dp[ 2][ 3 ] = 20 \times 30 \times 40 = 24000 \) \( dp[ 3][ 4 ] = 30 \times 40 \times 30 = 36000 \) 长度 3 （三个矩阵，有两种分割方式）： \( dp[ 1][ 3 ] \): 分割点 \( k=1 \) 或 \( k=2 \) \( k=1: dp[ 1][ 1] + dp[ 2][ 3 ] + 10 \times 20 \times 40 = 0 + 24000 + 8000 = 32000 \) \( k=2: dp[ 1][ 2] + dp[ 3][ 3 ] + 10 \times 30 \times 40 = 6000 + 0 + 12000 = 18000 \) 取最小值 18000。 \( dp[ 2][ 4 ] \): 分割点 \( k=2 \) 或 \( k=3 \) \( k=2: dp[ 2][ 2] + dp[ 3][ 4 ] + 20 \times 30 \times 30 = 0 + 36000 + 18000 = 54000 \) \( k=3: dp[ 2][ 3] + dp[ 4][ 4 ] + 20 \times 40 \times 30 = 24000 + 0 + 24000 = 48000 \) 取最小值 48000。长度 4 （整个链）： \( dp[ 1][ 4 ] \): 分割点 \( k=1,2,3 \) \( k=1: dp[ 1][ 1] + dp[ 2][ 4 ] + 10 \times 20 \times 30 = 0 + 48000 + 6000 = 54000 \) \( k=2: dp[ 1][ 2] + dp[ 3][ 4 ] + 10 \times 30 \times 30 = 6000 + 36000 + 9000 = 51000 \) \( k=3: dp[ 1][ 3] + dp[ 4][ 4 ] + 10 \times 40 \times 30 = 18000 + 0 + 12000 = 30000 \) 取最小值 30000。最优乘法总次数为 30000。 5. 复杂度分析时间复杂度：\( O(n^3) \)，三重循环（长度、起点、分割点）。空间复杂度：\( O(n^2) \)，用于存储 \( dp \) 表。 6. 扩展：记录括号方案如果需要输出最优括号化方案，可以用另一个数组 \( s[ i][ j] \) 记录得到 \( dp[ i][ j ] \) 时的分割点 \( k \)，然后通过递归或栈构造括号表达式。这个问题的核心是区间 DP 的经典应用，通过枚举分割点将大问题分解为两个子问题，最终得到全局最优解。