[알고리즘] 연쇄 행렬 곱셈 알고리즘(Chained Matrix Multiplication)

반응형

 

연쇄 행렬 곱셈 알고리즘(Chained Matrix Multiplication)

연쇄 행렬(ex, 2 by 4 행렬 x 4 by 7 행렬 x 7 by 9 행렬 x ...)의 곱셈을 할 때 곱셈 연산을 최소로 하는 곱셈 순서를 찾는 알고리즘이다. 행렬 곱셈은 결합 법칙이 성립하기 때문에 곱하는 순서에 상관은 없지만, 순서에 따라 연산의 양이 달라진다.

 

2 x 3 행렬 A와 3 x 5 행렬 B, 5 x 7 행렬 C가 있다고 하자. 이 행렬들의 곱 ABC를 구하는 경우는 아래와 같다.

1. AB를 먼저 곱하고 C를 곱할 때의 연산 수 = 2 x 3 x 5 +  2 x 5 x 7 = 100

2. BC를 먼저 곱하고 A를 곱할 때의 연산 수 = 3 x 5 x 7 + 2 x 3 x 7 = 147

 

둘은 같은 곱셈이지만, 연산의 수가 다름을 알 수 있다. 아래는 연쇄행렬 최소곱셈 알고리즘의 점화식이다.

$$M[i][j]=\{\begin{array}{ll}min(M[i][k]+M[k+1][j]+d_{i-1}{d}_k{d}_j),& (i\le k\le j-1)\\ 0,& (i=j)\end{array}$$

 

위 ABC 행렬을 예시로 해당 점화식을 전개해보자.

$d_0=2,d_1=3,d_2=5,d_3=7$

1. $M[1][2]$ (행렬 A, B의 곱 연산 수) $(1\le k\le 1)$

$=min(M[1][k]+M[k+1][2]+d_0{d}_k{d}_2)$

$=M[1][1]+M[2][2]+d_0{d}_1{d}_2$

$=0+0+2\times 3\times 5$

$=30$

 

2. $M[2][3]$ (행렬 B, C의 곱 연산 수) $(2\le k\le 2)$

$=min(M[2][k]+M[k+1][3]+d_1{d}_k{d}_3)$

$=M[2][2]+M[3][3]+d_1{d}_2{d}_3$

$=0+0+3\times 5\times 7$

$=105$

 

3. $M[1][3]$ (행렬 A, B, C의 곱 연산 수) $(1\le k\le 2)$

$=min(M[1][k]+M[k+1][3]+d_0{d}_k{d}_3)$

$=min(M[1][1]+M[2][3]+d_0{d}_1{d}_3,M[1][2]+M[3][3]+d_0{d}_2{d}_3)$

$=min(0+105+2\times 3\times 7,30+0+2\times 5\times 7)$

$=min(147,100)$

$=100$

 

최소 곱셈이 100회가 됨을 알 수 있다.

 

위의 예시를 코드로 나타내면 아래와 같다.

#include <iostream>

using namespace std;

int dp[4][4];

int main() {
    int d[4] = { 2, 3, 5, 7 };
    
    // 행렬의 수 만큼 반복
    for (int n = 0; n < 3; n++) {
        for (int i = 1; i <= 3 - n; i++) {
            int j = i + n;
            if (i == j) {
                dp[i][j] = 0;
            }
            else {
                dp[i][j] = 9999999;
                for (int k = i; k <= j - 1; k++) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + d[i - 1] * d[k] * d[j]);
                }
            }
        }
    }
    
    return 0;
}

---

 

[Reference]

https://en.wikipedia.org/wiki/Matrix_chain_multiplication

 

 

728x90