Vince Jiang

CSCI3160 / 辅导 · 本站更新

CSCI3160 T07 矩阵链乘法

课程：CSCI3160 Design and Analysis of Algorithms 本讲：T07 矩阵链乘法 · 原件 T07-矩阵链乘法-未核-隐藏.pdf（本地课件） p.1–11 定位：矩阵顺序不变，只优化加括号的位置。 承接：L08 DP依赖、T06 方案恢复

p.1–3：结合顺序改变中间矩阵尺寸【新】

p.1 标题，p.2 每个Ai尺寸ai×bi，相邻满足bi=a(i+1)，只允许改变括号，不能调换矩阵顺序。p.3 A1、A2是m×m，A3是m×1：先A1A2花m³，再乘A3花m²；先A2A3花m²，再A1乘结果再花m²。因此前者Θ(m³)、后者Θ(m²)。

这里用标准乘法的标量乘法次数abc作为精确比较模型；原文只写O(abc)，单凭一个上界记号不能比较两个实现的精确常数。

p.4–6：枚举最后一次乘法

p.4 “a fully parenthesized product”

完全括号化递归地是单矩阵，或两个完全括号化式子的乘积。例如 p.4 的 (A1A2)(A3A4) 和 ((A1A2)A3)A4 都完全括号化；A1(A2A3A4) 还没有指定后三个的相乘顺序，因而不完整。p.5 若最后在k处分开，左右结果尺寸a1×bk、a(k+1)×bn，最后乘法花a1bkbn。p.6 推广到区间(i,j)，先定义M(i,j)为最小标量乘法次数，目标M(1,n)。左右子方案必须分别最优，否则替换更优子方案可降低总体而不改变结果尺寸。

p.7–9：填满原件例子的表

p.7 递推为

M(i,j)={0,i=j,min⁡i≤k<j{M(i,k)+M(k+1,j)+aibkbj},i<j. M(i,j)=\begin{cases}0,&i=j,\\\min_{i\le k<j}\{M(i,k)+M(k+1,j)+a_i b_k b_j\},&i<j.\end{cases}

按链长递增，O(n²)状态每格O(n)分割，总O(n³)时间、O(n²)空间。单矩阵无标量乘法所以基值0；讲义把读取开销记O(1)，两种成本口径不要混写。

图（p.8–9）：A1、A2为m×m，A3为m×1，A4为1×m的上三角DP表。元素：对角单矩阵、最右上格完整链。看什么：表中的O(m²)不告诉你具体最优分割，还需比较候选值。

原页 p.9 的完整上三角量级表为：

i\j 1 2 3 4
1 O(1) O(m³) O(m²) O(m²)
2 — O(1) O(m²) O(m²)
3 — — O(1) O(m²)
4 — — — O(1)

下三角原图写0，仅是无效区间占位，不是需使用的子问题。标准标量乘法模型下，对 m≥1，M12=m³，M23=M34=m²，M13=M24=2m²，M14=3m²；m=1 时可能多个分割并列。这个精确表达同时说明原图各个 O 量级为什么成立。

将讲义参数取m=2演示（数值2为自取）：尺寸2×2、2×2、2×1、1×2。两矩阵成本M12=8、M23=4、M34=4；三矩阵M13=min(0+4+4,8+0+4)=8，M24=min(0+4+8,4+0+4)=8；四矩阵候选为16、20、12，故M14=12。最优值比全左结合的16更小。

补充：三个顶层候选不是三个随意括号。 原演示 m=2 时，完整区间(1,4)的最后分割账本为：

k 左子链成本 右子链成本 最后两结果尺寸 最后成本 总成本
1 0 8 2×2 与 2×2 8 16
2 8 4 2×2 与 2×2 8 20
3 8 0 2×1 与 1×2 4 12

每行的左右成本已经是该子区间的最优值，所以枚举最后一次分割就隐含覆盖了所有更深层括号。无论子区间内部怎么结合，它的输出尺寸由首矩阵行数和末矩阵列数决定；这正是可独立优化子问题的原因。

自测：为什么单矩阵基值是 0，而不是它的元素个数？

当前成本只计为了完成乘积执行的标量乘法；单矩阵已有，不做乘法。若应用还要复制或读入矩阵，可以另计数据处理开销，但不能把复制成本混进某些基值又在其他地方忽略，使候选比较口径不一致。

p.10–11：恢复完整括号

p.10 bestSub(i,j)存使递推最小的分割k，单矩阵存空。可另枚举O(n³)求，也可填M时同时记录。p.11 原例最优顶层k3，子链(1,3)取k1，输出(A1(A2A3))A4。取m2时三次实际乘法成本4+4+4=12，与表一致。

恢复函数在i=j时输出Ai，否则先输出左括号、递归(i,k)、递归(k+1,j)、右括号。递归树n个叶、n−1个内部结点，O(n)次输出。求括号的O(n³)是关于矩阵个数的规划时间，并不包括实际进行那些可能巨大维度矩阵乘法的成本。

本讲核心考点

  • （C 级 通识）以最后一次分割推导区间DP。
  • （C 级 通识）区分规划时间与执行矩阵乘法的算术成本。
  • （C 级 通识）存最优分割并恢复完整括号。

附录

本讲所需过程已在正文展开。

来源与证据

  • 本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。

  • 原件：T07-矩阵链乘法-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。

  • 版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。

  • 发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。

  • 既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无

  • 缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。