矩阵链乘法算法

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

为了进一步说明，考虑要相乘的矩阵 A、B、C 和 D；因此，乘法是使用标准矩阵乘法完成的。由于矩阵乘法是结合律的，因此在使用标准方法时会发现矩阵的多种组合。例如，有五种方法可以将上面给出的四个矩阵相乘 -

• (A(B(CD)))

• (A((BC)D))

• ((AB)(CD))

• ((A(BC))D)

• (((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；但是，(A((BC)D)) 的成本为 10 × 25 × 37 = 9,250。

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

矩阵链乘法算法

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

算法

• 计算括号化的数量。找到使用以下公式可以将输入矩阵相乘的方式的数量 -

$$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.$$

(或)

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

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

• 使用公式，$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值表来找到矩阵序列的最低成本括号化。

• 找到最低成本后，将相应的括号化作为输出打印。

伪代码

查找所有可能的括号化的最低成本的伪代码 -

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 “)”

示例

动态规划公式的应用与理论略有不同；为了更好地理解它，让我们看看下面的几个例子。

设置要相乘的矩阵 A、B、C、D 序列，其维度分别为 5 × 10、10 × 15、15 × 20、20 × 25。使用矩阵链乘法找到乘以给定矩阵的最低成本括号化。

解决方案

给定矩阵及其相应的维度为 -

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 种括号组合中，矩阵链乘法算法必须找到成本最低的括号。

步骤 1

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

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

步骤 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$

步骤 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}$

• $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$

步骤 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}$

• $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$

步骤 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}$

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

• $C[1,4]=4700$

现在成本表中的所有值都已计算出来，最后一步是对矩阵序列进行括号化。为此，需要构造k表，其中包含与每个括号相对应的“k”的最小值。

括号化

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

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

                  (ABC)(D)

在 [1, 3] 处获得的最低成本值是在 k = 2 时实现的，因此下一个括号化在 2 处完成。

                  ((AB)C)(D)

当 k = 1 时，在 [1, 2] 处取得最低成本值，因此下一个括号化操作在 1 处进行。但括号化操作至少需要两个矩阵相乘，所以我们不再进一步划分。

                  ((AB)(C))(D)

由于该序列无法进一步进行括号化，因此矩阵链乘法的最终解为 ((AB)C)(D)。

实施

以下是使用动态规划计算多个矩阵相乘的最小次数的矩阵链乘法算法的最终实现：

#include <stdio.h>
#include <string.h>
#define INT_MAX 999999
int mc[50][50];
int min(int a, int b){
   if(a < b)
      return a;
   else
      return b;
}
int DynamicProgramming(int c[], int i, int j){
   if (i == j) {
      return 0;
   }
   if (mc[i][j] != -1) {
      return
         mc[i][j];
   }
   mc[i][j] = INT_MAX;
   for (int k = i; k < j; k++) {
      mc[i][j] = min(mc[i][j], DynamicProgramming(c, i, k) + DynamicProgramming(c, k + 1, j) + c[i - 1] * c[k] * c[j]);
   }
   return mc[i][j];
}
int Matrix(int c[], int n){
   int i = 1, j = n - 1;
   return DynamicProgramming(c, i, j);
}
int main(){
   int arr[] = { 23, 26, 27, 20 };
   int n = sizeof(arr) / sizeof(arr[0]);
   memset(mc, -1, sizeof mc);
   printf("Minimum number of multiplications is: %d", Matrix(arr, n));
}

Minimum number of multiplications is: 26000

#include <bits/stdc++.h>
using namespace std;
int mc[50][50];
int DynamicProgramming(int* c, int i, int j){
   if (i == j) {
      return 0;
   }
   if (mc[i][j] != -1) {
      return
         mc[i][j];
   }
   mc[i][j] = INT_MAX;
   for (int k = i; k < j; k++) {
      mc[i][j] = min(mc[i][j], DynamicProgramming(c, i, k) + DynamicProgramming(c, k + 1, j) + c[i - 1] * c[k] * c[j]);
   }
   return mc[i][j];
}
int Matrix(int* c, int n){
   int i = 1, j = n - 1;
   return DynamicProgramming(c, i, j);
}
int main(){
   int arr[] = { 23, 26, 27, 20 };
   int n = sizeof(arr) / sizeof(arr[0]);
   memset(mc, -1, sizeof mc);
   cout << "Minimum number of multiplications is: " << Matrix(arr, n);
}

Minimum number of multiplications is: 26000

import java.io.*;
import java.util.*;
public class Main {
   static int[][] mc = new int[50][50];
   public static int DynamicProgramming(int c[], int i, int j) {
      if (i == j) {
         return 0;
      }
      if (mc[i][j] != -1) {
         return mc[i][j];
      }
      mc[i][j] = Integer.MAX_VALUE;
      for (int k = i; k < j; k++) {
         mc[i][j] = Math.min(mc[i][j], DynamicProgramming(c, i, k) + DynamicProgramming(c, k + 1, j) + c[i - 1] * c[k] * c[j]);
      }
      return mc[i][j];
   }
   public static int Matrix(int c[], int n) {
      int i = 1, j = n - 1;
      return DynamicProgramming(c, i, j);
   }
   public static void main(String args[]) {
      int arr[] = { 23, 26, 27, 20 };
      int n = arr.length;
      for (int[] row : mc)
         Arrays.fill(row, -1);
      System.out.println("Minimum number of multiplications is: " + Matrix(arr, n));
   }
}

Minimum number of multiplications is: 26000

mc = [[-1 for n in range(50)] for m in range(50)]
def DynamicProgramming(c, i, j):
   if (i == j):
      return 0
   if (mc[i][j] != -1):
      return mc[i][j]
   mc[i][j] = 999999
   for k in range (i, j):
      mc[i][j] = min(mc[i][j], DynamicProgramming(c, i, k) + DynamicProgramming(c, k + 1, j) + c[i - 1] * c[k] * c[j]);
   return mc[i][j]

def Matrix(c, n):
   i = 1
   j = n - 1
   return DynamicProgramming(c, i, j);

arr = [ 23, 26, 27, 20 ]
n = len(arr)
print("Minimum number of multiplications is: ")
print(Matrix(arr, n))

Minimum number of multiplications is: 
26000