第56课：矩阵链乘法 - 最优计算次序

学习目标

1. 理解矩阵链乘法问题：明白不同计算顺序（括号化）对计算成本（标量乘法次数）的巨大影响。
2. 掌握动态规划建模：学会将矩阵链乘法问题分解为子问题，并构建递推关系式。
3. 实现动态规划算法：编写代码，利用动态规划计算最小乘法次数。
4. 分析算法复杂度：理解矩阵链乘法算法的时间与空间复杂度。
5. 重构最优解：能够利用动态规划表，反向构造出最优的括号化方案。

核心概念

为什么顺序很重要？

计算矩阵乘法 A x B x C，假设 A 是 10×100，B 是 100×5，C 是 5×50。

• 顺序一：(A x B) x C
  • A x B: 10×100 * 100×5 -> 10×5，计算量 = 10 * 100 * 5 = 5000
  • 结果 x C: 10×5 * 5×50 -> 10×50，计算量 = 10 * 5 * 50 = 2500
  • 总计算量: 7500
• 顺序二：A x (B x C)
  • B x C: 100×5 * 5×50 -> 100×50，计算量 = 100 * 5 * 50 = 25000
  • A x 结果: 10×100 * 100×50 -> 10×50，计算量 = 10 * 100 * 50 = 50000
  • 总计算量: 75000

仅仅改变计算顺序，成本相差 10倍！矩阵链乘法问题就是寻找那个成本最低的括号化方案。

动态规划思路

我们定义 m[i][j] 为计算矩阵 A_i * A_{i+1} * ... * A_j 所需的最小乘法次数。那么：

1. 基本情况：当 i = j 时，m[i][j] = 0。自己和自己相乘，无需计算。
2. 递推关系：当 i < j 时，我们需要在 k (i <= k < j) 处“断开”这个链： m[i][j] = min_{i<=k<j} { m[i][k] + m[k+1][j] + p_{i-1} * p_k * p_j } 其中 p 数组存储了矩阵的维度。矩阵 A_i 的维度为 p_{i-1} x p_i。 这个公式的含义是：A_i...A_j 的最优成本，等于将其分为 (A_i...A_k) 和 (A_{k+1}...A_j) 两部分分别计算的最小成本，再加上合并这两部分结果（两个矩阵相乘）的成本。

代码示例

def matrix_chain_order(p):
    """
    计算矩阵链乘法的最小乘法次数。
    :param p: 矩阵维度列表。例如，矩阵链 A1(10x100), A2(100x5), A3(5x50) 对应 p = [10, 100, 5, 50]。
    :return: (m, s)。m[i][j]存储最小乘法次数，s[i][j]存储最优断开位置k。
    """
    n = len(p) - 1  # 矩阵的数量
    # 初始化表格，所有元素先设为0
    m = [[0 for _ in range(n)] for _ in range(n)]  # 记录成本
    s = [[0 for _ in range(n)] for _ in range(n)]  # 记录断点

    # l 是子链的长度 (l=2 表示两个矩阵相乘)
    for l in range(2, n + 1):
        # i 是子链的起始矩阵索引
        for i in range(0, n - l + 1):
            j = i + l - 1  # 子链的结束矩阵索引
            m[i][j] = float('inf')  # 初始化为一个大数
            # 尝试在所有可能的k处断开
            for k in range(i, j):
                # 计算将链分成 A_i..A_k 和 A_{k+1}..A_j 两部分再合并的成本
                cost = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
                if cost < m[i][j]:
                    m[i][j] = cost
                    s[i][j] = k  # 记录此时的最优断点

    return m, s


def print_optimal_parenthesis(s, i, j):
    """
    根据记录断点的s表，递归打印最优括号化方案。
    """
    if i == j:
        print(f"A{i + 1}", end='')  # 矩阵从1开始编号，索引从0开始
    else:
        print("(", end='')
        print_optimal_parenthesis(s, i, s[i][j])  # 递归左半部分
        print_optimal_parenthesis(s, s[i][j] + 1, j)  # 递归右半部分
        print(")", end='')


# 示例
if __name__ == "__main__":
    # 矩阵链维度 p = [10, 100, 5, 50, 7] 表示4个矩阵:
    # A1: 10x100, A2: 100x5, A3: 5x50, A4: 50x7
    p = [10, 100, 5, 50, 7]
    n = len(p) - 1  # 矩阵数量

    m, s = matrix_chain_order(p)

    print("最小乘法次数表 m[i][j] (索引从0开始):")
    for i in range(n):
        print([m[i][j] for j in range(n)])

    print(f"\n计算整个矩阵链 (A1-A{n}) 的最小乘法次数为: {m[0][n - 1]}")

    print("\n最优括号化方案为: ", end='')
    print_optimal_parenthesis(s, 0, n - 1)
    print()

输出结果:

最小乘法次数表 m[i][j] (索引从0开始):
[0, 5000, 7500, 11700]
[0, 0, 25000, 29500]
[0, 0, 0, 1750]
[0, 0, 0, 0]

计算整个矩阵链 (A1-A4) 的最小乘法次数为: 11700

最优括号化方案为: ((A1(A2A3))A4)

实践练习

练习1：手动计算

给定矩阵链维度 p = [30, 35, 15, 5, 10, 20, 25]（6个矩阵）。请手动填写下面 m 和 s 表的前三行（即 m[0][1], m[1][2], m[2][3], s[0][1], s[1][2], s[2][3]）。

• 预期输出: 你需要给出计算过程和结果。例如，m[0][1] = p[0]*p[1]*p[2] = 30*35*15 = 15750。

练习2：代码实现

将上面的 matrix_chain_order 函数修改为只返回 m[0][n-1]（即整个矩阵链的最小乘法次数），不返回 s 表。并写一个测试用例，使用 p = [40, 20, 30, 10, 30] 验证你的函数。

• 预期输出: 程序应输出该矩阵链的最小乘法次数 26000。

练习3：输出方案

修改 print_optimal_parenthesis 函数，使其返回一个字符串而不是直接打印，并且矩阵编号从1开始更符合阅读习惯。测试 p = [10, 100, 5, 50]。

• 预期输出: 函数应返回字符串 "((A1A2)A3)" 或类似的形式。

常见错误

1. 维度数组 p 的索引混乱：

   • 错误：将 m[i][j] 对应的维度错误地认为是 p[i] * p[j]。
   • 正确：矩阵 A_k 的维度是 p[k-1] x p[k]。A_i 到 A_j 相乘得到的矩阵维度是 p[i-1] x p[j]。成本项 p[i-1] * p[k] * p[j] 需要仔细对照。

2. 循环边界错误：

   • 错误：在外层循环 for l 或内层循环 for i 时，索引越界。
   • 正确：l 从 2 到 n，i 从 0 到 n-l。j = i+l-1，k 从 i 到 j-1。

3. 初始化遗漏：

   • 错误：忘记将 m[i][i] 初始化为 0，导致计算结果偏大。
   • 正确：在双重循环开始前，m 表已经通过列表推导式全部初始化为 0。

4. 递推顺序错误：

   • 错误：试图一次性计算 m[0][n-1]，而不先计算更短的子链。
   • 正确：必须按子链长度 l 从小到大进行递推，确保计算 m[i][j] 时，所有更短的子链成本 m[i][k] 和 m[k+1][j] 都已知。

小结

• 问题本质：矩阵链乘法是寻找标量乘法次数最少的矩阵连乘顺序，体现了“计算次序”的重要性。
• 动态规划关键：
  • 最优子结构：最优解包含其子问题的最优解。
  • 状态定义：m[i][j] 代表子问题 A_i...A_j 的最小成本。
  • 递推关系：m[i][j] = min{ m[i][k] + m[k+1][j] + p_{i-1}p_k p_j }，其中 i <= k < j。
  • 填表顺序：按子链长度 l 从小到大的顺序填充 m 表。
• 算法复杂度：
  • 时间：O(n³)。三重循环。
  • 空间：O(n²)。需要存储 m 表和 s 表。
• 应用延伸：该算法思想可应用于所有具有相似“合并”或“分割”成本的优化问题，如最优二叉搜索树、多边形最优三角剖分等。