[알고리즘/DP] Chained Matrix Multiplication 연쇄 행렬 곱셈

연쇄적으로 행렬을 곱할 때, 어떤 행렬 곱셈을 먼저 수행하느냐에 따라서 다음 예시와 같이 필요한 기본적인 곱셈의 횟수가 달라진다.

Minimum Multiplication 알고리즘은 곱셈 횟수의 최소치를 결정하고 그 최소치를 구하는 순서를 결정하는 알고리즘이다.

---

1. Brute force로 풀어보기

먼저 가능한 모든 순서를 모두 고려해보고 그 가운데에서 가장 최소인 경우를 선택하는 brute force로 문제를 풀어본다.

 

• n개의 행렬(A1, A2, ..., An)을 곱할 수 있는 모든 순서의 가짓 수를 $t_{n}$이라고 한다.
• 만약 A1이 마지막으로 곱하는 행렬이라면 (ex. A1(A2A3))  행렬 A2부터 An을 곱하는 가짓수는 $t_{n-1}$일 것이다.
• 만약 An이 마지막으로 곱하는 행렬이라면 (ex. (A1A2...))An  행렬 A1부터 $A_{n-1}$을 곱하는 가짓수는 $t_{n-1}$일 것이다.
• 그러면 $t_{n} \geq t_{n-1}+t_{n-1}=2t_{n-1}$ 이고 따라서 t2 = 1이라는 것을 알 수 있다.
• 따라서 $t_{n} \geq 2t_{n-1} \geq 2^2t_{n-2} \geq ... \geq 2^{n-2}t_{2}=\theta (2^n)$

brute force로 문제를 풀면 최소한 지수시간 exponential-time이 나오기 때문에 이것은 비효율적이며 최적의 방법이 아니다.

---

2. Chained Matrix Multiplication

우리는 연쇄적인 행렬 A1부터 A6까지를 곱할 때, 곱셈 횟수가 가장 적은 곱셈 순서를 찾아야 한다. 다시 말해서, A1A2A3A4A5A6 라는 곱셈 식이 있을 때, 괄호로 어디서 끊고 무엇을 묶어야 하는지 알아야 한다.

ex. ((A1A2))((A3(A4A5))A6)

$d_{k}$를 행렬 Ak의 열의 수라고 한다.

• 행렬 Ak의 행의 수는 이전 행렬인 $A_{k-1}$의 열의 수와 같으므로 $d_{k-1}$가 된다.
• 행렬 A1의 행의 수는 $d_0$이다.

이러한 상황에서 행렬 곱셈 횟수를 정리한 2차원 배열 M을 만든다.

• $1 \leq i \leq j \leq n$에 대하여,
• $M[i][j]$은 $i < j$일 때 $A_i$부터 $A_j$까지의 행렬을 곱하는데 필요한 곱셈의 최소 횟수이다.

$M[i][j] = minimum_{i \leq k \leq j-1}(M[i][k] + M[k+1][j] + d_{i-1}d_kd_j)$

$M[i][i] = 0$

이 성립한다. 여기에서

$M[i][k]$가 행렬 Ai부터 Ak까지 곱셈의 횟수를 의미할 때, 곱셈 과정과 행, 열의 수를 그림으로 표현하면 이렇다. 

또한 $M[k+1][j]$가 행렬 A_k+1부터 A_j까지 곱셈의 횟수를 의미할 때, 곱셈 과정과 행, 열의 수를 그림으로 표현하면 이렇다. 

 

그러면 A_i부터 A_j까지의 곱셈 과정은 i <= k<= j인 k값을 이용하여 아래처럼 표현할 수 있다. 

 

 

즉,

$M[i][j] = minimum_{i \leq k \leq j-1}(M[i][k] + M[k+1][j] + d_{i-1}d_kd_j)$

이 식에서 행렬 A_i부터 A_k까지의 곱셈#1에 대한 최소 곱셈 횟수(M[i][k])와 행렬 A_k+1부터 A_j까지의 곱셈#2에 대한 최소 곱셈 횟수(M[k+1][j])를 더하고 #1과 #2를 곱할 때의 곱셈 횟수인 $d_{i-1}d_kd_j$를 더하면 M[i][j]의 최소값을 구하는 식이 완성된다.

 

이 과정을 모든 $1 \leq i \leq j \leq n$ 인 경우에 대하여 계산하면

이렇게 우측상단만 채워진 배열이 완성된다.

이 때 j-i가 0이면 diagonal 0, 1이면 diagonal 1 ... 6이면 diagonal 6이라고 한다. 또한 행렬이 n개 있을 때, A1부터 An까지의 최소 곱셈 횟수는 M[n][n]이 된다.(아래 그림에서는 n=6이므로 M[6][6]이 Final answer 최종 답이다.)

---

최소 곱셈 Minimum Multiplication 알고리즘

• 문제

n개의 행렬을 곱하는데 필요한 기본적인 곱셈의 횟수의 최소치를 결정하고, 그 최소치를 구하는 순서를 결정한다.

• 입력

행렬의 수 n과 배열 d[0...n], d[i-1]*d[i]는 i번째 행렬의 규모를 나타낸다.

• 출력

기본적인 곱셈의 횟수의 최소치를 나타내는 minmult;

최적의 순서를 얻을 수 있는 배열P

여기서 P[i][j]는 행렬 A_i부터 A_j까지에서 최적의 순서로 갈라지는(괄호로 나뉘어지는) 기점=k값을 의미한다.

---

minmult pseudo code

int minmult(int n, const int d[], index P[][]) {
	index i, j, k, diagonal;
	int M[1..n, 1..n];
	for(i=1; i <= n; i++)
		M[i][i] = 0;
	
    for(diagonal = 1; diagonal <= n-1; diagonal++)
    	for(i=1; i <= n-diagonal; i++) {
 	    j = i + diagonal;
            M[i][j] = minimum(M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j]);	// i <= k <= j-1
            P[i][j] = 최소치를 주는 k의 값
        }
    return M[1][n];
}

---

최소곱셈 알고리즘의 모든 경우 분석

• 단위 연산

각 k값에 대하여 실행된 명령문(최소값인지 알아보는 비교문도 포함)

• 입력 크기 : 곱할 행렬의 수 n
• 분석

i-루프를 수행하는 횟수 = n - diagonal

k-루프를 수행하는 횟수 = (j-1)-i+1 = ((i+digonal)-1)-i+1 = digonal

 

따라서,