Data Structures Algorithms 简明教程
Matrix Chain Multiplication Algorithm
矩阵链乘是一种算法，用于确定以最低成本乘以矩阵。实际相乘是使用矩阵相乘的标准方式完成的，即遵循一个基本规则，即一个矩阵中的行数必须等于另一个矩阵中的列数。因此，必须执行多次标量相乘以获得乘积。
Matrix Chain Multiplication is an algorithm that is applied to determine the lowest cost way for multiplying matrices. The actual multiplication is done using the standard way of multiplying the matrices, i.e., it follows the basic rule that the number of rows in one matrix must be equal to the number of columns in another matrix. Hence, multiple scalar multiplications must be done to achieve the product.
粗略介绍一下吧，考虑要相乘的矩阵 A、B、C 和 D；因而，使用标准矩阵乘法进行乘法运算。使用标准方法时，会发现矩阵存在多个组合，因为矩阵乘法是可结合的。例如，有五种方式可以乘以上面给出的四个矩阵 −
To brief it further, consider matrices A, B, C, and D, to be multiplied; hence, the multiplication is done using the standard matrix multiplication. There are multiple combinations of the matrices found while using the standard approach since matrix multiplication is associative. For instance, there are five ways to multiply the four matrices given above −
-
(A(B(CD)))
-
(ABC)D
-
AB)(CD
-
A(BCD)
-
(((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。
Now, if the size of matrices A, B, C, and D are l × m, m × n, n × p, p × q respectively, then the number of scalar multiplications performed will be lmnpq. But the cost of the matrices change based on the rows and columns present in it. Suppose, the values of l, m, n, p, q are 5, 10, 15, 20, 25 respectively, the cost of (A(B(CD))) is 5 × 100 × 25 = 12,500; however, the cost of (ABC)D is 10 × 25 × 37 = 9,250.
因此，采用矩阵链乘的动态规划方法来找到具有最低成本的组合。
So, dynamic programming approach of the matrix chain multiplication is adopted in order to find the combination with the lowest cost.
Matrix Chain Multiplication Algorithm
矩阵链乘算法仅用于找到乘以一系列矩阵的最低成本方式。因此，算法的输入是矩阵的序列，而获得的输出是最小的成本括号化。
Matrix chain multiplication algorithm is only applied to find the minimum cost way to multiply a sequence of matrices. Therefore, the input taken by the algorithm is the sequence of matrices while the output achieved is the lowest cost parenthesization.
Algorithm
-
Count the number of parenthesizations. Find the number of ways in which the input matrices can be multiplied using the formulae −
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)
(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.
-
Once the parenthesization is done, the optimal substructure must be devised as the first step of dynamic programming approach so the final product achieved is optimal. In matrix chain multiplication, the optimal substructure is found by dividing the sequence of matrices A[i….j] into two parts A[i,k] and A[k+1,j]. It must be ensured that the parts are divided in such a way that optimal solution is achieved.
-
Using the formula, $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.$ find the lowest cost parenthesization of the sequence of matrices by constructing cost tables and corresponding k values table.
-
Once the lowest cost is found, print the corresponding parenthesization as the output.
Pseudocode
查找所有可能的括号化之最小成本的伪代码 −
Pseudocode to find the lowest cost of all the possible parenthesizations −
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打印最佳输出括号化的伪代码 −
Pseudocode to print the optimal output parenthesization −
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
动态规划公式的应用与理论略有不同；为了更好地理解这一点，让我们看看以下一些示例。
The application of dynamic programming formula is slightly different from the theory; to understand it better let us look at few examples below.
一组尺寸为 5 × 10、10 × 15、15 × 20、20 × 25 的矩阵 A、B、C、D 设置为相乘。使用矩阵链乘法，找出乘以给定矩阵的最优成本括号化。
A sequence of matrices A, B, C, D with dimensions 5 × 10, 10 × 15, 15 × 20, 20 × 25 are set to be multiplied. Find the lowest cost parenthesization to multiply the given matrices using matrix chain multiplication.
Solution
给定的矩阵及其对应尺寸为 −
Given matrices and their corresponding dimensions are −
A5×10×B10×15×C15×20×D20×25找出 4 个矩阵的括号化数量，即 n = 4。
Find the count of parenthesization of the 4 matrices, i.e. 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.$
Using the formula, $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，应用公式的第二种情况 −
Since n = 4 ≥ 2, apply the second case of the formula −
P\left ( n \right )=\sum_{k=1}^{n-1}P(k)P(n-k)
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 )=\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\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)
If P(1) = 1 and P(2) is also equal to 1, P(4) will be calculated based on the P(3) value. Therefore, P(3) needs to determined first.
P\left ( 3 \right )=P(1)P(2)+P(2)P(1)
P\left ( 3 \right )=P(1)P(2)+P(2)P(1)
=1+1=2
因此，
Therefore,
P\left ( 4 \right )=P(1)P(3)+P(2)P(2)+P(3)P(1)
P\left ( 4 \right )=P(1)P(3)+P(2)P(2)+P(3)P(1)
=2+1+2=5
在这些 5 种括号组合中，矩阵链乘法算法必须找到成本最低的括号。
Among these 5 combinations of parenthesis, the matrix chain multiplicatiion algorithm must find the lowest cost parenthesis.
Step 1
Step 1
上表被称为 cost table ，其中存储了从不同括号组合计算出的所有成本值。
The table above is known as a cost table, where all the cost values calculated from the different combinations of parenthesis are stored.
还创建了另一个表来存储在每个组合的最小成本来获得的 k 值。
Another table is also created to store the k values obtained at the minimum cost of each combination.
Step 2
Step 2
应用动态规划方法公式查找各种括号化的成本，
Applying the dynamic programming approach formula find the costs of various parenthesizations,
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[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 [ 1,1 \right ]=0$
C\left [ 2,2 \right ]=0
$C\left [ 2,2 \right ]=0$
C\left [ 3,3 \right ]=0
$C\left [ 3,3 \right ]=0$
C\left [ 4,4 \right ]=0
$C\left [ 4,4 \right ]=0$
Step 3
Step 3
仅在成本表的上三角值中应用动态方法公式，因为 i < j 始终成立。
Applying the dynamic approach formula only in the upper triangular values of the cost table, since i < j always.
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}
$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}$
-
$C[1,2]=0+0+\left ( 5\times 10\times 15 \right )$
-
$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}$
-
$C[2,3]=0+0+\left ( 10\times 15\times 20 \right )$
-
$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}$
-
$C[3,4]=0+0+\left ( 15\times 20\times 25 \right )$
-
$C[3,4]=7500$
Step 4
Step 4
在这一步中找到 [1, 3] 和 [2, 4] 的值。费用表总是分步对角线填充的。
Find the values of [1, 3] and [2, 4] in this step. The cost table is always filled diagonally step-wise.
$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}$
-
$C[2,4]=\displaystyle min\left\{ ( 0 + 7500 + (10 \times 15 \times 20)), (3000 + 5000)\right\}$
-
$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}$
-
$C[1,3]=min\left\{ ( 0 + 3000 + 1000), (1500+0+750)\right\}$
-
$C[1,3]=2250$
Step 5
Step 5
现在计算费用表中的最终元素来比较括号化的最低成本。
Now compute the final element of the cost table to compare the lowest cost parenthesization.
$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}$
-
$C[1,4]=min\left\{0+8000+1250,750+7500+1875,2200+0+2500\right\}$
-
$C[1,4]=4700$
现在，费用表中的所有值都已计算出来，最终步骤是为矩阵序列加上括号。为此，需要用每个括号对应的“k”的最小值构造 k 表。
Now that all the values in cost table are computed, the final step is to parethesize the sequence of matrices. For that, k table needs to be constructed with the minimum value of ‘k’ corresponding to every parenthesis.
Parenthesization
基于成本表中的最低成本值及其对应的 k 值，让我们在矩阵序列上添加括号。
Based on the lowest cost values from the cost table and their corresponding k values, let us add parenthesis on the sequence of matrices.
在 [1, 4] 的最低成本值在 k = 3 时实现，因此，必须在 3 处进行第一个加括号操作。
The lowest cost value at [1, 4] is achieved when k = 3, therefore, the first parenthesization must be done at 3.
(ABC)(D)在 [1, 3] 的最低成本值在 k = 2 时实现，因此在 2 处进行下一个加括号操作。
The lowest cost value at [1, 3] is achieved when k = 2, therefore the next parenthesization is done at 2.
((AB)C)(D)在 [1, 2] 的最低成本值在 k = 1 时实现，因此在 1 处进行下一个加括号操作。但是加括号操作至少需要两个矩阵相乘，因此我们不再进一步细分。
The lowest cost value at [1, 2] is achieved when k = 1, therefore the next parenthesization is done at 1. But the parenthesization needs at least two matrices to be multiplied so we do not divide further.
((AB)(C))(D)由于序列无法进一步加括号，因此矩阵链相乘的最终解决方案是 ((AB)C)(D)。
Since, the sequence cannot be parenthesized further, the final solution of matrix chain multiplication is ((AB)C)(D).