Data Structures Algorithms 简明教程

Matrix Chain Multiplication Algorithm

矩阵链乘是一种算法，用于确定以最低成本乘以矩阵。实际相乘是使用矩阵相乘的标准方式完成的，即遵循一个基本规则，即一个矩阵中的行数必须等于另一个矩阵中的列数。因此，必须执行多次标量相乘以获得乘积。

粗略介绍一下吧，考虑要相乘的矩阵 A、B、C 和 D；因而，使用标准矩阵乘法进行乘法运算。使用标准方法时，会发现矩阵存在多个组合，因为矩阵乘法是可结合的。例如，有五种方式可以乘以上面给出的四个矩阵 −

  1. (A(B(CD)))

  2. (ABC)D

  3. AB)(CD

  4. A(BCD)

  5. (((AB)C)D)

现在，如果矩阵 A、B、C 和 D 的大小分别是 l × m, m × n, n × p, p × q ，那么执行标量乘法的次数将是 lmnpq 。但是，矩阵的成本会根据其中现有的行和列而改变。假设 l、m、n、p、q 的值分别是 5、10、15、20、25，那么 (A(B(CD))) 的成本为 5 × 100 × 25 = 12,500；而 (ABC)D 的成本为 10 × 25 × 37 = 9,250。

因此，采用矩阵链乘的动态规划方法来找到具有最低成本的组合。

Matrix Chain Multiplication Algorithm

矩阵链乘算法仅用于找到乘以一系列矩阵的最低成本方式。因此，算法的输入是矩阵的序列，而获得的输出是最小的成本括号化。

Algorithm

  1. 计算括号化的数量。找出使用以下公式可以将输入矩阵乘以多少种方式 −

P(n)=\left\{\begin{matrix} 1 & if\: n=1\\ \sum_{k=1}^{n-1} P(k)P(n-k)& if\: n\geq 2\\ \end{matrix}\right.

(or)

P(n)=\left\{\begin{matrix} \frac{2(n-1)C_{n-1}}{n} & if\: n\geq 2 \\ 1 & if\: n= 1\\ \end{matrix}\right.

  1. 在完成括号化之后，必须将最优子结构设计为动态规划方法的第一步，以便获得的最终结果是最优的。在矩阵链乘中，通过将矩阵序列 A[i….j] 分成两部分 A[i,k] and A[k+1,j] 来找到最优子结构。必须确保以这种方式划分部分，以便获得最优解。

  2. 使用公式，$C[i,j]=\left\{\begin{matrix} 0 & if \: i=j\\ \displaystyle \min_{ i\leq k< j}\begin{cases} C [i,k]+C[k+1,j]+d_{i-1}d_{k}d_{j} \end{cases} &if \: i< j \\ \end{matrix}\right.$ 通过构建成本表和对应的 k 值表，找出矩阵序列的最优成本括号化。

  3. 找到最小成本后，打印出相应的括号化作为输出。

Pseudocode

查找所有可能的括号化之最小成本的伪代码 −

MATRIX-CHAIN-MULTIPLICATION(p)
   n = p.length ─ 1
   let m[1…n, 1…n] and s[1…n ─ 1, 2…n] be new matrices
   for i = 1 to n
      m[i, i] = 0
   for l = 2 to n // l is the chain length
      for i = 1 to n - l + 1
         j = i + l - 1
         m[i, j] = ∞
         for k = i to j - 1
            q = m[i, k] + m[k + 1, j] + pi-1pkpj
            if q < m[i, j]
               m[i, j] = q
               s[i, j] = k
return m and s

打印最佳输出括号化的伪代码 −

PRINT-OPTIMAL-OUTPUT(s, i, j )
if i == j
print “A”i
else print “(”
PRINT-OPTIMAL-OUTPUT(s, i, s[i, j])
PRINT-OPTIMAL-OUTPUT(s, s[i, j] + 1, j)
print “)”

Example

动态规划公式的应用与理论略有不同；为了更好地理解这一点，让我们看看以下一些示例。

一组尺寸为 5 × 10、10 × 15、15 × 20、20 × 25 的矩阵 A、B、C、D 设置为相乘。使用矩阵链乘法，找出乘以给定矩阵的最优成本括号化。

Solution

给定的矩阵及其对应尺寸为 −

A5×10×B10×15×C15×20×D20×25

找出 4 个矩阵的括号化数量，即 n = 4。

使用公式，$P\left ( n \right )=\left\{\begin{matrix} 1 & if\: n=1\\ \sum_{k=1}^{n-1}P(k)P(n-k) & if\: n\geq 2 \\ \end{matrix}\right.$

由于 n = 4 ≥ 2，应用公式的第二种情况 −

P\left ( n \right )=\sum_{k=1}^{n-1}P(k)P(n-k)

P\left ( 4 \right )=\sum_{k=1}^{3}P(k)P(4-k)

P\left ( 4 \right )=P(1)P(3)+P(2)P(2)+P(3)P(1)

如果 P(1) = 1 且 P(2) 也等于 1，P(4) 将基于 P(3) 值计算。因此，需要首先确定 P(3)

P\left ( 3 \right )=P(1)P(2)+P(2)P(1)

=1+1=2

因此，

P\left ( 4 \right )=P(1)P(3)+P(2)P(2)+P(3)P(1)

=2+1+2=5

在这些 5 种括号组合中，矩阵链乘法算法必须找到成本最低的括号。

Step 1

上表被称为 cost table ，其中存储了从不同括号组合计算出的所有成本值。

cost table

还创建了另一个表来存储在每个组合的最小成本来获得的 k 值。

k values

Step 2

应用动态规划方法公式查找各种括号化的成本，

C[i,j]=\left\{\begin{matrix} 0 & if \: i=j\\ \displaystyle \min_{ i\leq k< j}\begin{cases} C [i,k]+C\left [ k+1,j \right ]+d_{i-1}d_{k}d_{j} \end{cases} &if \: i< j \\ \end{matrix}\right.

C\left [ 1,1 \right ]=0

C\left [ 2,2 \right ]=0

C\left [ 3,3 \right ]=0

C\left [ 4,4 \right ]=0

dynamic programming

Step 3

仅在成本表的上三角值中应用动态方法公式，因为 i < j 始终成立。

C[1,2]=\displaystyle \min_{ 1\leq k< 2}\begin{Bmatrix} C[1,1]+C[2,2]+d_{0}d_{1}d_{2} \end{Bmatrix}

  1. C[1,2]=0+0+\left ( 5\times 10\times 15 \right )

  2. $C[1,2]=750$

$C[2,3]=\displaystyle \min_{ 2\leq k< 3}\begin{Bmatrix} C[2,2]+C[3,3]+d_{1}d_{2}d_{3} \end{Bmatrix}$

  1. $C[2,3]=0+0+\left ( 10\times 15\times 20 \right )$

  2. $C[2,3]=3000$

$C[3,4]=\displaystyle \min_{ 3\leq k< 4}\begin{Bmatrix} C[3,3]+C[4,4]+d_{2}d_{3}d_{4} \end{Bmatrix}$

  1. $C[3,4]=0+0+\left ( 15\times 20\times 25 \right )$

  2. $C[3,4]=7500$

dynamic approach formula

Step 4

在这一步中找到 [1, 3] 和 [2, 4] 的值。费用表总是分步对角线填充的。

$C[2,4]=\displaystyle \min_{ 2\leq k< 4}\begin{Bmatrix} C[2,2]+C[3,4]+d_{1}d_{2}d_{4},C[2,3] +C[4,4]+d_{1}d_{3}d_{4}\end{Bmatrix}$

  1. $C[2,4]=\displaystyle min\left\{ ( 0 + 7500 + (10 \times 15 \times 20)), (3000 + 5000)\right\}$

  2. $C[2,4]=8000$

$C[1,3]=\displaystyle \min_{ 1\leq k< 3}\begin{Bmatrix} C[1,1]+C[2,3]+d_{0}d_{1}d_{3},C[1,2] +C[3,3]+d_{0}d_{2}d_{3}\end{Bmatrix}$

  1. $C[1,3]=min\left\{ ( 0 + 3000 + 1000), (1500+0+750)\right\}$

  2. $C[1,3]=2250$

filled diagonally

Step 5

现在计算费用表中的最终元素来比较括号化的最低成本。

$C[1,4]=\displaystyle \min_{ 1\leq k< 4}\begin{Bmatrix} C[1,1]+C[2,4]+d_{0}d_{1}d_{4},C[1,2] +C[3,4]+d_{1}d_{2}d_{4},C[1,3]+C[4,4] +d_{1}d_{3}d_{4}\end{Bmatrix}$

  1. $C[1,4]=min\left\{0+8000+1250,750+7500+1875,2200+0+2500\right\}$

  2. $C[1,4]=4700$

final element

现在，费用表中的所有值都已计算出来，最终步骤是为矩阵序列加上括号。为此，需要用每个括号对应的“k”的最小值构造 k 表。

k table

Parenthesization

基于成本表中的最低成本值及其对应的 k 值，让我们在矩阵序列上添加括号。

在 [1, 4] 的最低成本值在 k = 3 时实现，因此，必须在 3 处进行第一个加括号操作。

                  (ABC)(D)

在 [1, 3] 的最低成本值在 k = 2 时实现，因此在 2 处进行下一个加括号操作。

                  ((AB)C)(D)

在 [1, 2] 的最低成本值在 k = 1 时实现，因此在 1 处进行下一个加括号操作。但是加括号操作至少需要两个矩阵相乘，因此我们不再进一步细分。

                  ((AB)(C))(D)

由于序列无法进一步加括号，因此矩阵链相乘的最终解决方案是 ((AB)C)(D)。

Implementation

以下是矩阵链相乘算法的最终实现，用于使用动态规划计算可以乘以多个矩阵的最少方式数 −