Matrix-chain

定义 Definition

matrix-chain（常见于算法语境）指“矩阵链（乘法）问题”：给定一串需要相乘的矩阵（矩阵维度已知），由于矩阵乘法满足结合律但不同加括号方式计算代价不同，目标是找到使标量乘法次数最少的最佳括号化方案（经典动态规划问题）。
（也可泛指“一串矩阵的连续相乘/矩阵序列”，但最常见指上述优化问题。）

发音 Pronunciation (IPA)

/ˈmeɪtrɪks tʃeɪn/

例句 Examples

We solved the matrix-chain problem with dynamic programming.
我们用动态规划解决了矩阵链问题。

Although matrix multiplication is associative, the matrix-chain order can drastically change the total number of scalar multiplications.
尽管矩阵乘法满足结合律，但矩阵链的乘法顺序会显著改变标量乘法的总次数。

词源 Etymology

matrix 源自拉丁语 matrix（本义与“母体、孕育者”相关，后在数学中用于表示“矩阵”这一结构）；chain 源自古法语 chaine（链条），表示“串联的一系列”。在计算机科学中，matrix-chain 作为复合词，强调“矩阵按链式顺序相乘”，并特指“矩阵链乘法的括号化优化”这一经典问题。

相关词 Related Words

• Dynamic Programming
• Optimization
• Parenthesization
• Matrix Multiplication
• Associativity
• Cost Function
• Computational Complexity

文学与名著用例 Literary Works

• Introduction to Algorithms（《算法导论》, Cormen/Leiserson/Rivest/Stein）：以“Matrix-Chain Multiplication”作为动态规划章节的经典案例。
• Algorithm Design（《算法设计》, Jon Kleinberg & Éva Tardos）：在动态规划与最优子结构的讲解中涉及矩阵链括号化思想。
• The Algorithm Design Manual（《算法设计手册》, Steven S. Skiena）：在讲解动态规划与优化套路时常提及该类经典问题。