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

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

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

-> 행렬의 곱셈은 아래와 같이 결합법칩이 성립한다.
      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

코드로 구현해보자. (아래코드는 4개의 행렬값을 기준으로 하고 있다.)

#include<iostream>
 
using namespace std;
 
#define MIN(A, B) ((A)>(B)?(B):(A))
#define MAX_VALUE 9999999
#define MAX_SIZE 101
 
int M[MAX_SIZE][MAX_SIZE];
int d[MAX_SIZE];
 
int main()
{
    int size = 4;
 
    d[0] = 20, d[1] = 1, d[2] = 30, d[3] = 10, d[4] = 10;
 
    for (int diagonal = 0; diagonal < size; diagonal++)
    {
        for (int i = 1; i <= size - diagonal; i++)
        {
            int j = i + diagonal;
            if (j == i)
            {
                M[i][j] = 0;
                continue;
            }
            M[i][j] = MAX_VALUE;
            for (int k = i; k <= j - 1; k++)
                M[i][j] = MIN(M[i][j], M[i][k] + M[k + 1][j] + d[i - 1] * d[k] * d[j]);
 
        }
    }
 
    /*결과 출력*/
    cout << M[1][size] << endl;
    for (int i = 1; i <= size; i++)
    {
        for (int j = 1; j <= size; j++)
        {
            cout << M[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

(line 18) for (int diagonal = 0; diagonal < size; diagonal++)   ->  구하려는 행렬 사이즈만큼 반복한다.
(line 20) for (int i = 1; i <= size - diagonal; i++)   -> i값은 상단 1부터 시작, 반복하는 횟수가 1씩 감소한다.
(line 22) int j = i + diagonal;  -> j값은 우측으로 diagnonal만큼 반복할때마다 이동한다.
(line 23~25) if (j == i) 
 -> i와 j가 같을 경우 M[i][j] = 0
(line 28~30) 
 -> k=i~j-1만큼 반복하며, 공식을 적용하여 M[i][j]에 들어갈 곱의 최소값을 구한다.

[참고 링크]
http://egloos.zum.com/sakuragis/v/3322692
http://yimoyimo.tk/MatrixMultiplication/
http://web.skhu.ac.kr/~mckim1/Lecture/DS/dna/class13/class13_02.html