设计与分析-矩阵链乘法

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

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

• （A B C D）））

• （A B C D））

• （（A B C D））

• （（A B C D）

• （（（A B 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(nk)& if\ : n\geq 2\\ \end{矩阵}\right.$$

（或者）

$$P(n)=\left\{\begin{matrix} \frac{2(n-1)C_{n-1}}{n} & if\: n\geq 2 \\ 1 & if\: n= 1\\ \end{矩阵}\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{矩阵}\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 “)”

例子

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

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

解决方案

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

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(nk) & if\: n\geq 2 \\ \end{矩阵}\right.$

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

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

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

$$P\左 ( 4 \右 )=P(1)P(3)+P(2)P(2)+P(3)P(1)$$

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

$$P\左 ( 3 \右 )=P(1)P(2)+P(2)P(1)$$

$$=1+1=2$$

所以，

$$P\左 ( 4 \右 )=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{矩阵}\right。 $$

$C\左[1,1\右]=0$

$C\左[2,2\右]=0$

$C\左[3,3\右]=0$

$C\左[4,4\右]=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{B 矩阵}$

• $C[1,2]=0+0+\左 ( 5\乘以 10\乘以 15 \右 )$

• $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{B 矩阵}$

• $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{B 矩阵}$

• $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]=分钟\左\{ ( 0 + 3000 + 1000), (1500+0+750)\右\}$

• $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{B矩阵}$

• $C[1,4]=分钟\左\{0+8000+1250,750+7500+1875,2200+0+2500\右\}$

• $C[1,4]=4700$

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

括号

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

当 k = 3 时，[1, 4] 处的成本值最低，因此，第一个括号必须在 3 处完成。

                  (ABC)(D)

当 k = 2 时，[1, 3] 处的成本值最低，因此下一个括号在 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