[Algorithm] DP로 MCM(Matrix-Chain Multiplication) 풀기

다이나믹 프로그래밍(Dynamic Programming)란?

큰 문제를 작은 문제로 쪼개서 그 답을 리스트에 저장해서 사용하는 알고리즘입니다.

DP를 사용하게 되면 같은 문제를 여러 번 반복되지 않아도 되는 장점이 있기 때문입니다.

 

 

Recursion을 사용하면 아래 코드와 같이 자기 자신을 계속 호출하게 됩니다.

Fib(n) {
	if(n<2) return n;
    else return fib(n-1) + fib(n-2);
}

recursion은 top-down으로 문제를 풀어갑니다.

 

 

DP를 사용하면 작은 문제부터 차근차근 해결하면서 같은 문제를 반복하지 않아도 됩니다.

fib(n){
    int fib[n+1], i;
    fib[0] = 0;
    fib[1] = 1;
    
    for(int i = 2; i<n; i++) 
    	fib[i] = fib[i-1]+fib[i-2];
        
 	return 0;
}

dp는 bottom-up으로 문제를 풀어나갑니다.

 

 

MCM(Matrix-Chain Multiplication)이란?

---

MCM은 Matrix 곱을 할때 괄호(parenthesis)을 어떻게 묶냐에 따라서

곱셈의 횟수가 달라짐을 이용해 곱셈을 최소한으로 만드는 알고리즘입니다.

 

 

A = p x q = 10 x 100 (matrix)

B = q x r = 100 x 5 (matrix)

C = r x s = 5 x 50 (matrix)

 

A, B, C matrix가 존재할 때 괄호를 두 가지 방법으로 나눌 수 있습니다.

① (AxB)xC

② Ax(BxC)

 

식을 풀어보면

① (AxB)xC = pxqxr + pxrxs = pxr(q+s) = 10x5(100+50) = 7,500

② Ax(BxC) = qxrxs + pxqxs = (q+r)xqxs = (10+5)x100x50 = 115,000

 

이 곱셈 횟수가 더 적은 ① 으로 문제를 풀게 됩니다.

 

 

 

다른 예제를 보면

Parenthesizations	solution	Nulber of multiplications
(A₁(A₂(A₃A₄))), k = 1	(A₃A₄ = 50*5*30)+(A₂A₃₄ = 10*50*30)+(A₁A₂₃₄=20*10*30)	28500
(A₁((A₂A₃)A₄))	(A₂A₃ = 10*50*30)+(A₂₃A₄ = 10*5*30)+(A₁A₂₃₄ = 20*10*30)	10000
((A₁A₂)(A₃A₄)), k = 2	(A₁A₂ = 20*10*50)+(A₃A₄ = 50*5*30)+(A₁₂A₃₄ = 20*50*3)	47500
((A₁(A₂A₃))A₄), k = 3	(A₂A₃ = 10*50*5)+(A₁A₂₃ = 20*10*5)+(A₁₂₃A₄ = 20*5*30)	6500
(((A₁(A₂)A₃)A₄)	(A₁A₂=20*10*50)+(A₁₂A₃ = 20*50*5)+(A₁₂₃A₄ = 20*50*30)	18000

(k는 괄호를 자른 위치를 의미합니다.)

optimal인 답은 ((A₁(A₂A₃))A₄)됩니다.

 

 

DP이용해서 MCM문제 풀기

---

DP (Dynamic Programming)는 큰 문제를 작은 문제로 분할하여 풀어나가는 최적화 기법입니다.

DP에서 중요한 개념 중 하나는 "optimal substructure" (최적 부분 구조)인데 큰 문제의 최적해가 작은 문제의 최적해들을 활용하여 구할 수 있어야 된다는 개념입니다. 큰 문제를 풀기 위해 작은 문제들의 최적해가 이미 구해져 있어야 된다는 의미입니다.

 

 

문제를 풀기 위해 식을 하나 알아야됩니다.

i는 시작하는 Matrix, j는 마지막 matrix, k는 괄호가 잘린 위치입니다.

 

주어진 matrix입니다.

matrix	dimesion
A1	30(index0) x 35(index1)
A2	35 x 15(index2)
A3	15 x 5(index3)
A4	5 x 10(index4)
A5	10 x 20(index5)
A6	20 x 25(index6)

p = <30, 35, 15, 5, 10, 20, 25>

 

 

아래 표를 bottom-up으로 하나하나 풀어나가면 됩니다.

i \ j	1	2	3	4	5	6
1
2	x
3	x	x
4	x	x	x
5	x	x	x	x
6	x	x	x	x	x

j가 i보다 작은 부분은 풀지 않아도 되기 때문에 x를 쳐줍니다.

 

 

 

if i==j, then m[i,j] = 0 식에 의해 0으로 채워줍니다.

i \ j	1	2	3	4	5	6
1	0
2	x	0
3	x	x	0
4	x	x	x	0
5	x	x	x	x	0
6	x	x	x	x	x	0

 

 

 

아래 공식을 통해 문제를 풀어줍니다.

i \ j	1	2	3	4	5	6
1	0	① 15750
2	x	0	② 2625
3	x	x	0	③ 750
4	x	x	x	0	④ 1000
5	x	x	x	x	0	⑤ 5000
6	x	x	x	x	x	0

① m[1, 2]

A₁A₂ = 30x35x15 = 15750

② m[2, 3]

A₂A₃ = 35x15x5 = 2625

③ m[3, 4]

A₃A₄ = 15x10x5 = 750

④ m[4, 5]

A₄A₅ = 5x10x30 = 1000

⑤ m[5, 6]

A₅A₅ = 10x20x25=5000

 

 

 

i \ j	1	2	3	4	5	6
1	0	15750	① 7875
2	x	0	2625	② 4375
3	x	x	0	750	③ 2500
4	x	x	x	0	1000	④ 3500
5	x	x	x	x	0	5000
6	x	x	x	x	x	0

① m[1, 3]

A₁(A₂A₃) = m[1,1] + m[2,3] +p₀p₁p₃= 7875

(A₁A₂)A₃ = m[1,2] + m[3,3] = m[1,2] + m[3,3] +p₀p₂p₃ = 18000

 

② m[2, 4]

A₂(A₃A₄) = m[2,2] + m[3, 4] + p₁p₂p₄= 21750

(A₂A₃)A₄ = m[2,3] + m[4, 4] + p₁p₃p₄= 4375

 

③ m[3, 5]

A₃(A₄A₅) = m[3,3] + m[4,5] + p₂p₃p₅ = 2500

(A₃A₄)A₅ =  m[3,3] + m[4,5] + p₂p₄p₅ = 3750

 

④ m[4, 6]

A₄(A₅A₆) = m[4,4] + m[5,6] + p₃p₄p₆= 6250 

(A₄A₅)A₆ = m[4,5] + m[6,6] + p₃p₅p₆ =3500

 

 

 

i \ j	1	2	3	4	5	6
1	0	15750	7875	① 9375
2	x	0	2625	4375	② 7125
3	x	x	0	750	2500	③ 5357
4	x	x	x	0	1000	3500
5	x	x	x	x	0	5000
6	x	x	x	x	x	0

① m[1,4]

A₁(A₂A₃A₄) = m[1,1] + m[2,4] + p₀p₁p₄ = 14875

A₁A₂(A₃A₄) = m[1,2] + m[3,4] + p₀p₂p₄ = 21000

A₁A₂A₃(A₄) = m[1,3] + m[4,4] + p₀p₃p₄ = 9375

 

② m[2,5]

A₂(A₃A₄A₅) = m[2,2] + 2[3,5] + p₁p₂p₅ = 13000

A₂A₃(A₄A₅) = m[2,3] + 2[4,5] + p₁p₃p₅ = 7125

A₂A₃A₄(A₅) = m[2,4] + 2[5,5] + p₁p₄p₅ = 11375

 

③ m[3,6]

A₃(A₄A₅A₆) = m[3,3] + m[4,6] + p₂p₃p₆ = 5357

A₃A₄(A₅A₆) = m[3,4] + m[5,6] + p₂p₄p₆ = 9520

A₃A₄A₅(A₆) = m[3,5] + m[6,6] + p₂p₅p₆ = 10000

 

 

 

i \ j	1	2	3	4	5	6
1	0	15750	7875	9375	① 11876
2	x	0	2625	4375	7125	② 10500
3	x	x	0	750	2500	5357
4	x	x	x	0	1000	3500
5	x	x	x	x	0	5000
6	x	x	x	x	x	0

① m[1,5]

A₁(A₂A₃A₄A₅) = m[1,1] + m[2,5] + p₀p₁p₅ = 28125

A₁A₂(A₃A₄A₅) = m[1,2] + m[3,5] + p₀p₂p₅ = 27250

A₁A₂A₃(A₄A₅) = m[1,3] + m[4,5] + p₀p₃p₅ = 11875

A₁A₂A₃A₄(A₅) = m[1,4] + m[5,5] + p₀p₄p₅ = 15375

 

② m[2,6]

A₂(A₃A₄A₅A₆) = m[2,2] + m[3,6] + p₁p₂p₆ = 18482

A₂A₃(A₄A₅A₆) = m[2,3] + m[4,6] + p₁p₃p₆ = 10500

A₂A₃A₄(A₅A₆) = m[2,4] + m[5,6] + p₁p₄p₆ = 18125

A₂A₃A₄A₅(A₆) = m[2,5] + m[6,6] + p₁p₅p₆ = 24625

 

 

 

i \ j	1	2	3	4	5	6
1	0	15750	7875	9375	11876	① 15125
2	x	0	2625	4375	7125	10500
3	x	x	0	750	2500	5357
4	x	x	x	0	1000	3500
5	x	x	x	x	0	5000
6	x	x	x	x	x	0

① m[1,6]

A₁(A₂A₃A₄A₅A₆) = m[1,1] + m[2,6] + p₀p1₁p₆ = 36750

A₁A₂(A₃A₄A₅A₆) = m[1,2] + m[3,6] + p₀p1₂p₆ = 32357

A₁A₂A₃(A₄A₅A₆) = m[1,3] + m[4,6] + p₀p1₃p₆ = 15125

A₁A₂A₃A₄(A₅A₆) = m[1,4] + m[5,6] + p₀p1₄p₆ = 21875

A₁A₂A₃A₄A₅)A₆) = m[1,5] + m[6,6] + p₀p1₅p₆ = 26875

 

 

 

마지막 메트릭스까지 채웠을 때 결과를 확인하면 ((A₁(A₂A₃))((A₄A₅)A₆))가 최적화된 해가 됩니다.

 

 

 

◡̈