矩阵链乘法算法

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

进一步简述，考虑矩阵 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。

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

矩阵链乘法算法

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

Algorithm

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

$$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] and 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 值表，找出矩阵序列的最低成本括号化方式。

• 一旦找到最低成本，就打印对应的括号化方式作为输出。

Pseudocode

找出所有可能括号化方式的最低成本的伪代码 −

MATRIX-CHAIN-MULTIPLICATION(p)
   n = p.length  1
   let m[1n, 1n] and s[1n  1, 2n] 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 Ai
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 种括号组合中，矩阵链乘法算法必须找出最低成本的括号方式。

步骤 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 值。

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)。

实现

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

#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