Phép nhân chuỗi ma trận (Giải pháp A O (N ^ 3)) trong C ++

Nếu một chuỗi ma trận được cho, chúng ta phải tìm số lượng tối thiểu 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 trình tự 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 - Thứ tự của các ma trận đầu vào. {1, 2, 3, 4}. Nó có nghĩa là các ma trận là

{(1 x 2), (2 x 3), (3 x 4)}.

Đầu ra - Số phép toán tối thiểu cần nhân ba ma trận này. Ở đây kết quả là 18.

Thuật toán

matOrder(array, n)
Input: List of matrices, the number of matrices in the list.
Output: Minimum number of matrix multiplication.
Begin
   define table minMul of size n x n, initially fill with all 0s
   for length := 2 to n, do
      for 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