[알고리즘] 다이나믹 프로그래밍 적용 문제 (3) 행렬 곱셈 순서

다이나믹 프로그래밍 적용 문제 (3) 행렬 곱셈 순서

 

문제 설명

행렬 A1, A2, A3, . . . , An을 곱하는 수를 최소로 하는 최적의 곱셈 순서를 구하라.

 

예로, 행렬 A(2 × 3), B(3 × 5), C(5 × 2)가 있을 때 곱할 수 있는 경우의 수는 다음과 같다.

(AB)C = 2 × 3 × 5 + 2 × 5 × 2 = 50

A(BC) = 3 × 5 × 2 + 2 × 3 × 2 = 42

두 경우의 수에서 최솟값인 42에 해당하는 연산이 최소의 곱셈 횟수 42와 최적의 곱셈 순서 A(BC) 가 된다.

 

마지막 행렬 곱셈이 수행되는 상황을 다음과 같이 정리할 수 있으며, 경우의 수는 총 n - 1이다.

 

 

점화식

Ak의 크기 : pk-1 * pk

m[i, j] : 행렬 Ai, …, Aj의 곱을  계산하는 최소 비용

m[i, j] = {

    0    ( if  i = j )

    min{ m[i, k] + m[k + 1, j] + pi-1 * pk * pj }    ( if  i < j )  ※ i <= k <= j-1

}

 

※ 밑줄 : 일반형 (Ai ×. . .× Ak)(Ak ×. . .× Aj)

 

 

 

행렬 곱셈 순서 : 재귀적 알고리즘 (효율적 측면에서 부적합)

minSum(i, j) { # 행렬곱 Ai...Aj를 구하는 최소 비용 구하기 
	if (i = j) then return 0;    # 행렬이 하나뿐인 경우의 비용은 0 
	min ← -INF; 
	for k ← i to j-1 { 
      	q ← minSum(i, k) + minSum(k + 1, j) + pi-1 * pk * pj; 
		if (q < min) then min ← q; 
	} 
	return min; 
}
print(minSum(1, n))

 

행렬 곱셈 순서 : 다이나믹 프로그래밍

for i ← 1 to n          
	m[i, i] ← 0; # 행렬이 하나뿐인 경우의 비용은 0 

for r ← 1 to n-1 { # r: 문제 크기를 결정하는 변수,  r = j - i
	for i ← 1 to n-r { 
		j ← i+r; 
		m[i, j] ← min{m[i, k] + m[k + 1, j] + pi-1 * pk * pj}; 
	} 
}
print (m[1, n]);
# Θ(n^3)

 

 

문제 예시1

A1 (2×3)

A2 (3×2)

A3 (2×10)

A4 (10×2)

---

	1	2	3	4
1	0	12	52	60
2		0	60	52
3			0	40
4				0

풀이

A1A2 = 2*3*2 = 12

A2A3 = 3*2*10 = 60

A3A4 = 2*10*2 = 40

 

A1A3

① A1(A2A3) = 2*3*10 + 60 = 120

② (A1A2)A3 = 12 + 2*2*10 = 52 (최솟값)

A2A4

① A2(A3A4) = 3*2*2 + 40 = 52 (최솟값)

② (A2A3)A4 = 60 + 3*10*2 = 120

 

A1A4

① A1(A2A3A4) = 2*3*2 + 52 = 64

② (A1A2)(A3A4) = 12 + 2*2*2 + 40 = 60 (최솟값)

③ (A1A2A3)A4 = 52 + 2*10*2 = 92

 

 

문제 예시2

A1 (10×2)

A2 (2×20)

A3 (20×5)

A4 (5×15)

---

	1	2	3	4
1	0	400	300	650
2		0	200	350
3			0	1500
4				0

풀이

A1A2 = 10*2*20 = 400

A2A3 = 2*20*5 = 200

A3A4 = 20*5*15 = 1500

 

A1A3

① A1(A2A3) = 10*2*5 + 200 = 300 (최솟값)

② (A1A2)A3 = 400 + 10*20*5 = 1400

A2A4

① A2(A3A4) = 2*20*15 + 1500 = 2100

② (A2A3)A4 = 200 + 2*5*15 = 350 (최솟값)

 

A1A4

① A1(A2A3A4) = 10*2*15 + 350 = 650 (최솟값)

② (A1A2)(A3A4) = 400 + 10*20*15 + 1500 = 4900

③ (A1A2A3)A4 = 300 + 10*5*15 = 1050

 

 

문제 예시3

A1 (5×4)

A2 (4×6)

A3 (6×2)

A4 (2×7)

---

	1	2	3	4
1	0	120	88	158
2		0	48	104
3			0	84
4				0

풀이

A1A2 = 5*4*6 = 120

A2A3 = 4*6*2 = 48

A3A4 = 6*2*7 = 84

 

A1A3

① A1(A2A3) = 5*4*2 + 48 = 88 (최솟값)

② (A1A2)A3 = 120 + 5*6*2 = 180

A2A4

① A2(A3A4) = 4*6*7 + 84 = 252

② (A2A3)A4 = 48 + 4*2*7 = 104 (최솟값)

 

A1A4

① A1(A2A3A4) = 5*4*7 + 104 = 244

② (A1A2)(A3A4) = 120 + 5*6*7 + 84 = 414

③ (A1A2A3)A4 = 88 + 5*2*7 = 158 (최솟값)

 

 

문제 예시4

A1 (5×2)

A2 (2×3)

A3 (3×4)

A4 (4×6)

A5 (6×7)

A6 (7×8)

---

	1	2	3	4	5	6
1	0	30	64	132	226	348
2		0	24	72	156	268
3			0	72	198	366
4				0	168	392
5					0	336
6						0

풀이

A1A2 =

A2A3 = 

A3A4 = 

A4A5 = 

A5A6 = 

 

A1A3

① A1(A2A3) = 

② (A1A2)A3 = 

A2A4

① A2(A3A4) = 

② (A2A3)A4 = 

A3A5

① A3(A4A5)

② (A3A4)A5

A4A6

① A4(A5A6)

② (A4A5)A6

 

A1A4

① A1(A2A3A4) = 

② (A1A2)(A3A4) = 

③ (A1A2A3)A4 = 

A2A5

① 

② 

③ 

A3A6

① 

② 

③ 

 

A1A5

① 

② 

③ 

④

A2A6

① 

② 

③ 

④

 

A1A6

① A1(A2A3A4A5A6) = 

② (A1A2)(A3A4A5A6) = 

③ (A1A2A3)(A4A5A6) = 

④ (A1A2A3A4)(A5A6) = 

⑤ (A1A2A3A4A5A6)A7 =