[1][연쇄행렬 최소곱셈 알고리즘] (Matrix chain multiplication)

연쇄행렬 최소곱셈 알고리즘 (Matrix chain multiplication)

연쇄행렬 최소곱셈 알고리즘이란 주어진 행렬들의 곱을 최소의 연산으로 수행하는 최소횟수를 구하는 알고리즘이다.

 

행렬의 곱셈에서 결합법칙은 성립하지만 어떤 형태로 결합되느냐에 따라 계산 횟수는 달라질수 있다.

 

예를 들어 아래와같은 행렬이 있다고 할때 결합 형태에 따른 연산횟수 차이는 다음과 같다.

 

위와 같이 결합되는 순서에 따라 전체 연산횟수가 달라짐을 알수 있다.

 

그렇다면 본격적으로 연쇄행렬 최소곱셈 알고리즘에 대해 알아보자.

 

 

 

 

먼저 행렬의 개수가 5개일때 모든 결합의 마지막 결합 형태는 크게 다음과같이 네가지로 분류가 가능하다. ( 행렬의 개수가 n개일때 (n-1)가지로 분류가 가능하다.)

예를 들어

(AB)(C(DE)) 는 최종적으로 AB와 CDE의 곱이므로 type 2 에 해당하고

(A(B(CD)))E 는 최종적으로 ABCD와 E의 곱이므로 type 4에 해당한다.

 

따라서 위 4가지 방법들 중 가장 최소값이 최종적인 답이 될것이다.

 

이를 DP로 구현하면

 

DP[i][j] = i번째 행렬부터 j번째행렬까지 최소 연산 횟수

 

가 된다.

 

점화식은 주어진 행렬을 다음과 같이 표현할때

i번째에 n by m 행렬을 matrix[i][0] = n, matrix[i][1] = m 

 

DP[i][j] = min(DP[i][k] + DP[k+1][j] + matrix[i][0] * matrix[k][1] * matrix[j][1]) (i<=k<j)

가 된다.

 

따라서 c언어로 작성된 최종 코드는 다음과 같다.

// 연쇄행렬 최소곱셈 알고리즘
#include <stdio.h>

int matrix[501][2];
int dp[501][501];
int mat(int n);

int main(){
    int n,i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d %d",&matrix[i][0],&matrix[i][1]);
    }
    int ans = mat(n);
    printf("최소연산 횟수 : %d\n",ans);
}

int mat(int n){
    int a,b;
    int i,j,k;
    for(i=0;i<n;i++){
        for(j=0;j<n-i;j++){
            a = j;
            b = j+i;
            if(a == b){
                dp[a][b] = 0;
            }
            else{
                dp[a][b] = 987654321;
                for(k = a; k < b; k++){
                    dp[a][b] = min(dp[a][b],dp[a][k] + dp[k+1][b] + ( matrix[a][0] * matrix[k][1] * matrix[b][1] ));
                }
            }
        }
    }
    return dp[0][n-1];
}

int min(int x, int y){
    return x < y ? x : y;
}

 

처음의 예제를 실행했을때 채워지는 dp 배열은 다음과 같다.