Phép nhân chuỗi ma trận

Nếu cho một chuỗi ma trận, chúng ta phải tìm số lượng nhỏ nhất của dãy ma trận chính xác để nhân.

Chúng ta biết rằng phép nhân ma trận là liên kết, vì vậy bốn ma trận ABCD, chúng ta có thể nhân A (BCD), (AB) (CD), (ABC) D, A (BC) D, trong các dãy này. Giống như các chuỗi này, nhiệm vụ của chúng ta là tìm ra thứ tự nào là hiệu quả để nhân lên.

Trong đầu vào đã cho, có một mảng giả sử arr, chứa arr [] ={1, 2, 3, 4}. Nó có nghĩa là các ma trận có thứ tự (1 x 2), (2 x 3), (3 x 4).

Đầu vào và Đầu ra

Input:
The orders of the input matrices. {1, 2, 3, 4}. It means the matrices are
{(1 x 2), (2 x 3), (3 x 4)}.
Output:
Minimum number of operations need multiply these three matrices. Here the result is 18.

Thuật toán

matOrder(array, n)

Đầu vào - Danh sách ma trận, số lượng ma trận trong danh sách.

Đầu ra - Số phép nhân ma trận tối thiểu.

Begin
   define table minMul of size n x n, initially fill with all 0s
   for length := 2 to n, do
      fir i:=1 to n-length, do
         j := i + length – 1
         minMul[i, j] := ∞
         for k := i to j-1, do
            q := minMul[i, k] + minMul[k+1, j] + array[i-1]*array[k]*array[j]
            if q < minMul[i, j], then minMul[i, j] := q
         done
      done
   done
   return minMul[1, n-1]
End

Ví dụ

#include<iostream>
using namespace std;

int matOrder(int array[], int n) {
   int minMul[n][n];          //holds the number of scalar multiplication needed

   for (int i=1; i<n; i++)
      minMul[i][i] = 0;           //for multiplication with 1 matrix, cost is 0

   for (int length=2; length<n; length++) {        //find the chain length starting from 2
      for (int i=1; i<n-length+1; i++) {
         int j = i+length-1;
         minMul[i][j] = INT_MAX;     //set to infinity
         for (int k=i; k<=j-1; k++) {
            //store cost per multiplications
            int q = minMul[i][k] + minMul[k+1][j] + array[i- 1]*array[k]*array[j];
            if (q < minMul[i][j])
               minMul[i][j] = q;
         }
      }
   }
   return minMul[1][n-1];
}

int main() {
   int arr[] = {1, 2, 3, 4};
   int size = 4;
   cout << "Minimum number of matrix multiplications: " << matOrder(arr, size);
}

Đầu ra

Minimum number of matrix multiplications: 18