矩陣鏈乘法演算法

Table of content
上一頁
下一頁

矩陣鏈乘法是一種用於確定矩陣相乘的最低成本方法的演算法。實際的乘法是使用標準的矩陣相乘方法完成的，即遵循基本規則，即一個矩陣的行數必須等於另一個矩陣的列數。因此，必須進行多次標量乘法才能獲得乘積。

為了進一步說明，考慮要相乘的矩陣 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

上表稱為成本表，其中儲存了從括號的不同組合計算的所有成本值。

cost_table

還建立了另一個表來儲存在每個組合的最低成本下獲得的k值。

k_values

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

dynamic_programming

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

dynamic_approach_formula

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

filled_diagonally

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

final_element

現在成本表中的所有值都已計算出來，最後一步是對矩陣序列進行括號化。為此，需要構造k表，其中包含與每個括號相對應的“k”的最小值。

k_table

括號化

根據成本表中的最低成本值及其對應的 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)。

實施

以下是使用動態規劃計算多個矩陣相乘的最小次數的矩陣鏈乘法演算法的最終實現：

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
列印頁面
上一頁
下一頁
廣告