[ 알고리즘 ] Dynamic Programming : Matrix multiplication

1. 문제정의

 

행렬의 곱에서 어떤 행렬을 먼저 곱하냐에 따라 걸리는 시간이 달라진다.

행렬들은 M1, M2, ... Mn으로 표현되며, 행렬의 크기는 di-1 * bi로 표현된다.

 

Cij는 Mi부터 Mj까지 곱했을 때 최소 비용을 의미하며

C1n이 최종 답이 된다.

 

2. solution

 

 전체 답을 제일  좋은 답으로 만들기 위해서는 어떤 곱을 나중에 해야할까?

우리는 이 문제에 대한 해답을 알지 못한다. 따라서 하나씩 다 해볼 것이다. 

 

Cij에서 i-j가 작은 값부터 해볼 것이다. 

 

1) i-j =0 

C11,C22,C33, ... Cnn

위와 같은 경우는 비용이 모두 0이라고 할 수 있다. 

 

2) i-j =1

C12,C23,C34, ... Cn-1n

비용은 di-1 * di * di+1 

 

3) i-j =2

C13,C24,C35, ... Cn-2n

여기서는 이제 계산 순서에 따라 비용이 달라질 수 있다. 

 

C13으로 예를 들어보자.

C13 = M1 * M2 * M3 이다. 

이는 ( M1 * M2 )* M3이 될 수도 있고 M1 * (M2 * M3)이 될 수도 있다. 

1. ( M1 * M2 )* M3 => d0 *d2 * d3 + C12
2.  M1 * (M2 * M3) => d0 *d1 * d3 + C23

위와 같이 다른 비용이 나온다. 이중 더 좋은 것을 pick하면 된다. 

근데 여기서 빨간색으로 표시된 C12와 C23은 이미 2) 에서 계산이 되었다. 

따라서 이를 바로 가져다 쓸 수 있다면 하나하나 다 해보는 과정에서 계산과정을 많이 줄일 수 있을 것이다. 

 

 

3. 코드 (이해못함)

int D[n + 1][n + 1]; // D[i][j] = C(i->j)

for (i = 1; i <= n; i++)
	D[i][i] = 0;
for (s=1; s<=n-1; s++)
	for (i = 1; i <= n - s; i++) {
		minval = INF;
		for (k = i; k <= i + s - 1; k++)
			minval = min(minval, D[i][k] + D[k + 1][i + s] + d[i - 1] * d[k] * d[i + s]);
		D[i][i + s] = minval;
	}