C++의 행렬 사슬 곱셈(A O(N^3) 해)

일련의 행렬이 주어지면 곱할 올바른 행렬 시퀀스의 최소 수를 찾아야 합니다.

우리는 행렬 곱셈이 연관적이라는 것을 알고 있으므로 4개의 행렬 ABCD를 사용하면 이 시퀀스에서 A(BCD), (AB)(CD), (ABC)D, A(BC)D를 곱할 수 있습니다. 이러한 시퀀스와 마찬가지로 우리의 임무는 곱하기에 효율적인 순서를 찾는 것입니다.

주어진 입력에는 arr[] ={1, 2, 3, 4}를 포함하는 arr 배열이 있습니다. 행렬이 (1 x 2), (2 x 3), (3 x 4) 순서라는 것을 의미합니다.

입력 − 입력 행렬의 차수. {1, 2, 3, 4}. 이는 행렬이 다음과 같다는 것을 의미합니다.

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

출력 − 최소 연산 수는 이 세 행렬을 곱해야 합니다. 결과는 18입니다.

알고리즘

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

예시

#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);
}

출력

Minimum number of matrix multiplications: 18