Chained Matrix Multiplication (연쇄 행렬 곱셈)

A1, A2, A3 이 세 행렬이 있고,

A1은 3*5

A2는 5*1

A3는 1*2 행렬이라고 합시다.

행렬의 곱셈에서도 결합법칙은 성립하는데, 위 예시에서는 (A1*A2)*A3, A1*(A2*A3) 이 두 가지가 가능합니다.

그런데, 앞 식에서는 3*5*1 + 3*1*2 = 21번 연산,

뒷 식에서는 5*1*2 + 3*5*2 = 40번을 연산하게 됩니다.

 

즉 행렬의 곱셈은 연산 순서에 따라 연산 횟수가 달라지게 됩니다. 이때 최소 연산 횟수와 연산 순서를 구하는 알고리즘이 연쇄 행렬 곱셈 알고리즘입니다.

코드는 다음과 같습니다.

int chainedMatrix(int n, int d[], int P[][N]){
    int dp[N][N] = {};
    for(int diag=1; diag<=n; diag++){
        for(int i=1; i<=n; i++){
            int j=diag+i;
            dp[i][j] = INF;
            for(int k=i; k<=j-1; k++){
                if(dp[i][j]>dp[i][k]+dp[k+1][j]+d[i-1]*d[k]*d[j]){
                    dp[i][j] = dp[i][k]+dp[k+1][j]+d[i-1]*d[k]*d[j];
                    P[i][j] = k;
                }
            }
        }
    }
    return dp[1][n];
}

이 코드의 가장 중요한 부분은 점화식인 dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+d[i-1]*d[k]*d[j]) 입니다.

앞서 말씀 드린 세 행렬 A1(3*5), A2(5*1), A3(1*2)가 있다고 합시다.

dp[i][j]는 i번째 행렬부터 j번째 행렬까지 연산하는데 필요한 최소 연산 횟수입니다. k는 괄호를 나누는 기준점입니다.

예를 들어, A1,A2,A3이 있을 때 k가 2라면 (A1*A2)*A3이 됩니다.

그리고 행렬들은 행렬곱이 가능하므로 붙어있는 행렬의 열크기와 행크기는 같고, 이를 붙여 나열하면 3,5,1,2(index는 0,1,2,3) 입니다.

d는 이런 방식으로 행렬의 크기를 나열한 배열입니다.

 

따라서, dp[i][k] + dp[k+1][j] + d[i-1]*d[k]*d[j]에서,

dp[i][k]는 Ai에서 Ak까지 행렬곱 했을 때의 연산 횟수,

dp[k+1][j]는 A(k+1)에서 Aj까지 행렬곱 했을 때의 연산 횟수,

d[i-1]*d[k]*d[j]는 dp[i][k]와 dp[k+1][j]를 행렬곱 했을때의 연산 횟수이고,

 

이를 합친 값이 최소가 되도록 만드는 기준점 k를 찾는 것이 핵심입니다.

 

예시

A(5*2) * A(2*3) * A(3*4) * A(4*6) * A(6*7) * A(7*8)일 때 위 알고리즘을 적용시킨 후의 배열은 이렇게 됩니다.

 

 예시 P

또, 위 알고리즘을 수행하면서 P배열을 구했는데, 그 배열은 다음과 같이 그려집니다.

현재 A1 * A2 * A3 * A4 * A5 * A6이 있으므로 P(1,6)을 보면 값이 1입니다. 따라서 1을 기준으로 나누어집니다.

-> A1 * (A2 * A3 * A4 * A5 * A6) 여기서 P(2,6)은 5입니다.

-> A1 * ((A2 * A3 * A4 * A5) * A6) 여기서 P(2,5)는 4입니다.

-> A1 * (((A2 * A3 * A4) * A5) * A6) 여기서 P(2,4)는 3입니다.

-> A1 * ((((A2 * A3) * A4) * A5) * A6)

 

 

오늘도 마무리로 시간 복잡도를 계산하고 마치도록 하겠습니다.

따라서 이 알고리즘의 시간복잡도는 항상 𝜃(n³) 입니다.