[알고리즘] 동적 계획법 | 행렬의 연쇄적 곱셈 | 연쇄 행렬 최소곱셈 알고리즘

연쇄행렬 최소곱셈 알고리즘

 두 개 이상의 행렬을 곱할 때, 최소 곱셈 횟수를 구하는 문제이다. 

 

-> 행렬의 곱셈은 아래와 같이 결합법칩이 성립한다.
      A*(B*C) = (A*B)*C
 그러나, 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라진다.

 

예를들어 설명하면,
행렬 A,B,C,D 4개가 존재한다.
각각 행렬의 차수는 20x1, 1x30, 30x10, 10x10이라고 한다.
4개의 행렬은 여러가지 방법으로 곱할 수 있지만,
다음 4개의 경우에 대하여 생각해볼때, 곱셈 횟수를 비교하면 아래와 같다.

 

((A*B)*C)*D) = (20*1*30) + (20*30*10) + (20*10*10) = 8,600
A*(B*(C*D)) = (30*10*10) + (1*30*10) + (20*1*10) = 3,500
(A*B)*(C*D) = (20*1*30) + (30*10*10) + (20*30*10) = 9,600
(A*((B*C)*D) = (1*30*10) + (1*10*10) + (20*1*10) = 600

 

위와 같이 곱셈을 하는 순서에 따라 600~9600번의 곱셈 횟수가 나오게 되는데,
그 중 최소 곱셈 횟수는 600번이다.

 

즉, 연쇄행렬 최소곱셈 알고리즘은 행렬곱셈에서 곱하는 순서에 따라 곱셈의 횟수가 달라지는데
이러한 법칙을 이용하여 최소로 곱하는 횟수를 구하는 것이다.

 

연쇄행렬 최소곱셈 알고리즘은 아래와 같이 재귀관계식을 세울 수 있다.

 

 

위 관계식을 아래의 행렬로 하나씩 예를 들어보자.

A(20x1),B(1x30),C(30x10),D(10x10) 일때,
d0=20, d1=1, d2=30, d3=10, d4=10

 

1. M[1][2] (행렬 A~B까지의 곱의 횟수) (1<=k<=1)
  = minimum(M[1][k] + M[k+1][2] + d0*dk*d2 
  = M[1][1] + M[2][2] + d0*d1*d2
  = 0 + 0 +  20*1*30
  = 600

 

2. M[2][3](행렬 B~C까지의 곱의 횟수) (2<=k<=2)
  = minimum(M[2][k] + M[k+1][3] + d1*dk*d3)
  = M[2][2] + M[3][3] + d1*d2*d3
  = 0+0+1*30*10
  = 300

 

3. M[1][3](행렬 A~C까지의 곱의 횟수)(1<=k<=2)
  = minimum(M[1][k] + M[k+1][3] +d0*dk*d2 
  = minimum(M[1][1] + M[2][3] + d0*d1*d3, M[1][2] + M[3][3] + d0*d2*d3)
  = minimum(0 + 300+20*1*10, 600+0+20*30*10)
  = minimum(500, 6600)
  = 500

 

행렬 A~D까지의 곱의 횟수 (M[1][4])는
M[1][4] = minimum( M[1][1] + M[2][4] + d0*d1*d4, M[1][2] + M[3][4] + d0*d2*d4, M[1][3] + M[4][4] + d0*d3*d4)

M[1][4]를 구하려면
M[1][1]~M[1][4]의 값이 필요하고,(구하려는 값의 테이블 좌측값)
M[2][4]~M[4][4]의 값이 필요하고,(구하려는 값의 테이블 아랫값)

 

M[i][j]의 값은,
대각선을 하나씩 증가시키며 아래와 같이 구할 수 있다.

1) (1,1)~(4,4), (i==j, M[i][j] = 0)

	1	2	3	4
1	0
2		0
3			0
4				0

2) (1,2)~(3,4)

	1	2	3	4
1	0	600
2		0	300
3			0	3000
4				0

3) (1,3)~(2,4)

	1	2	3	4
1	0	600	500
2		0	300	400
3			0	3000
4				0

4) (1,4)

	1	2	3	4
1	0	600	500	600
2		0	300	400
3			0	3000
4				0