矩阵链乘法算法

更新于 2025/10/16 16:21:06

矩阵链乘法算法
实现

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

进一步简化，假设矩阵 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} ight.$$

(或)

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

一旦括号完成后，必须设计最优子结构作为动态规划方法的第一步，以确保最终结果最优。在矩阵链乘法中，最优子结构是通过将矩阵序列 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} ight.$ 通过构建成本表和相应的 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，需要进行乘法运算。使用矩阵链乘法找到成本最低的括号来乘以给定的矩阵。

解答

给定矩阵，其对应的维数为负

A_5×10×B_10×15×C_15×20×D_20×25

求这4个矩阵的括号数，即n = 4。

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

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

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

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

$$P\left ( 4 ight )=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 ight )=P(1)P(2)+P(2)P(1)$$

$$=1+1=2$$

因此，

$$P\left ( 4 ight )=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} ight.$$

$C\left [ 1,1 ight ]=0$

$C\left [ 2,2 ight ]=0$

$C\left [ 3,3 ight ]=0$

$C\left [ 4,4 ight ]=0$

步骤 3

由于 i 始终

$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 次 10 次 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 次 15 次 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 imes 20 imes 25 ight )$
$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 时间 15 时间 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 值，我们在矩阵序列上添加括号。

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

实现

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

C C++ Java Python

#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

数据结构和算法

数据结构

链接列表

堆栈 &队列

搜索算法

排序算法

图形数据结构

树数据结构

递归

分而治之

贪婪算法

动态规划

近似算法

随机算法

DSA 有用资源

矩阵链乘法算法

矩阵链乘法算法

算法

伪代码

示例

解答

括号化

实现

输出

输出

输出

输出

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！