행렬의 연쇄적 곱셈

🟩 n개의 행렬을 연쇄적으로 곱할 때 최소의 기본 곱셈 횟수를 갖는 행렬의 곱셈 순서를 구하는 문제

i x j 행렬과 j x k 행렬을 곱하기 위해서는 i x j x k 번 만큼의 곱셈이 필요하다.

연쇄적으로 행렬을 곱할 때 어떤 행렬을 먼저 수행하느냐에 따라서 필요한 총 곱셈의 횟수가 달라진다.

🟩 연쇄행렬

행렬의 곱셈은 아래와 같이 결합법칙이 성립한다.

A x (B x C) = (A x B) x C

그러나, 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라진다.

 

👉 즉, 연쇄행렬 최소곱셈 알고리즘은 행렬곱셈에서 곱하는 순서에 따라 곱셉의 횟수가 달라지는데 이러한 법칙을 이용하여 최소로 곱하는 횟수를 구하는 것이다.

 

연쇄행렬 최소곱셈 알고리즘 재귀관계식

 

✨ 예제로 이해하면 쉽게 이해 가능!

EX) A(20x1),B(1x30),C(30x10),D(10x10) 일때, d0=20, d1=1, d2=30, d3=10, d4=10

 

1. M[1][2] (행렬 A~B까지의 곱의 횟수) (1<=k<=1)
  = minimum(M[1][k] + M[k+1][2] + d0*dk*d2 
  = M[1][1] + M[2][2] + d0*d1*d2
  = 0 + 0 +  20*1*30
  = 600

 

2. M[2][3](행렬 B~C까지의 곱의 횟수) (2<=k<=2)
  = minimum(M[2][k] + M[k+1][3] + d1*dk*d3)
  = M[2][2] + M[3][3] + d1*d2*d3
  = 0+0+1*30*10
  = 300

 

3. M[1][3](행렬 A~C까지의 곱의 횟수)(1<=k<=2)
  = minimum(M[1][k] + M[k+1][3] +d0*dk*d2 
  = minimum(M[1][1] + M[2][3] + d0*d1*d3, M[1][2] + M[3][3] + d0*d2*d3)
  = minimum(0 + 300+20*1*10, 600+0+20*30*10)
  = minimum(500, 6600)
  = 500

 

행렬 A~D까지의 곱의 횟수 (M[1][4])는
M[1][4] = minimum( M[1][1] + M[2][4] + d0*d1*d4, M[1][2] + M[3][4] + d0*d2*d4, M[1][3] + M[4][4] + d0*d3*d4)
M[1][4]를 구하려면
M[1][1]~M[1][4]의 값이 필요하고,(구하려는 값의 테이블 좌측값)
M[2][4]~M[4][4]의 값이 필요하고,(구하려는 값의 테이블 아랫값)

 

🟩 시간복잡도

O(N^3)

 

cf. 최적의 행렬 곱셈 순서를 구하는 알고리즘 O(n)

나뉠 부분이 하나씩 줄어드는데, n개 행렬의 곱셈 순서에서는 n-2번의 분할 지점이 필요하다. 👉 O(n)

 

🟩 구현

#include<iostream> 
using namespace std; 

#define MIN(A, B) ((A)>(B)?(B):(A))
#define MAX_VALUE 9999999
#define MAX_SIZE 101 

int M[MAX_SIZE][MAX_SIZE];
int d[MAX_SIZE]; 

int main(){    
	int size = 4;     
    d[0] = 20, d[1] = 1, d[2] = 30, d[3] = 10, d[4] = 10;     
    
    // 구하려는 행렬의 사이즈만큼 반복한다.
    for (int diagonal = 0; diagonal < size; diagonal++) {
    	// i 값은 상단 1부터 시작, 반복하는 횟수가 1씩 감소한다.
    	for (int i = 1; i <= size - diagonal; i++) {
        	// j값은 우측부터 diagnonal만큼 반복할 때마다 이동한다.
        	int j = i + diagonal;            
        	if (j == i) { // i==j일 경우 M[i][j] = 0 
            	M[i][j] = 0;                
                continue;            
            }            
            
            // k = i~ j-1만큼 반복하여, 공식을 적용하여 M[i][j]에 들어갈 곱의 최소값을 구한다.
            M[i][j] = MAX_VALUE;            
            for (int k = i; k <= j - 1; k++)               
            	M[i][j] = MIN(M[i][j], M[i][k] + M[k + 1][j] + d[i - 1] * d[k] * d[j]);         
        }    
    }     
    
    /*결과 출력*/    
    cout << M[1][size] << endl;    
    for (int i = 1; i <= size; i++) {
    	for (int j = 1; j <= size; j++) {            
        	cout << M[i][j] << " ";        
        }        
        cout << endl;    
    }
    
    return 0;
}

---

자료 출처

https://huiyu.tistory.com/entry/DP-%EC%97%B0%EC%87%84%ED%96%89%EB%A0%AC-%EC%B5%9C%EC%86%8C%EA%B3%B1%EC%85%88-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98