Algorithm design - Matrix-chain Multiplication

---

연쇄 행렬곱셈

i × j행렬과 j × k 행렬을 곱하기 위해서는 일반적으로 i × j × k 번 만큼의 기본적인 곱셈이 필요하다. 연쇄적으로 행렬을 곱할 때, 어떤 행렬곱셈을 먼저 수행하느냐에 따라서 필요한 기본적인 곱셈의 횟수가 달라지게 된다.

예를들어 M1, M2, M3, M4이 각각 10x100, 100x5, 5x50, 50x20이라고 할때 아래와 같이 다양한 결과가 나올 수 있다.

 

(1) M1x(M2x(M3xM4)) : 5x50x20+100x5x20+10x100x20 = 35,000
(2) M1x((M2xM3)xM4) : 100x5x50+100x50x20+10x100x20 = 145,000
(3) (M1xM2)x(M3xM4) : 10x100x5+5x50x20+10x5x20 = 11,000
(4) ((M1xM2)xM3)xM4 : 10x100x5+10x5x50+10x50x20 = 75,000
(5) (M1x(M2xM3))xM4 : 100x5x50+10x100x50+10x50x20 = 85,000

 

연쇄 행렬곱셈(Matrix-chain Multiplication)은 가능한 모든 순서를 모두 고려해 보고, 그 가운데에서 가장 최소를 택하는 알고리즘이고 시간복잡도는 최소 exponential-time이다.

d_k를 행렬 A_k의 열(column)의 수라고 하자. 그러면 자연히 A_k의 행(row)의 수는 d_k-1가 된다.
A_1의 행의 수는 d_0라고 하면 다음과 같이 재귀 관계식을 구축할 수 있다.

Subproblem의 중간결과를 기록하여 그 다음 결과를 계산할 때 재사용한다. 여기서도 DP를 활용하기 위해 table을 채워야하는데 DP가 tabular method라고 불리는 이유를 알 수 있다.

 

실제 예시를 통해 과정을 살펴보자. 아래와 같은 6개의 행렬이 존재할때 최적의 곱셈 순서를 찾아보자.

최종 결과는 아래와 같이 나온다.

 

 

알고리즘은 아래와 같이 된다.

int minmult(int n, const int d[], index P[][]) {
	index i, j, k, diagonal;
	int M[1..n, 1..n];
	for(i=1; i <= n; i++)
		M[i][j] = 0;
	for(diagonal = 1; diagonal <= n-1; diagonal++)
		for(i=1; i <= n-diagonal; i++) {
			j = i + diagonal;
			M[i][j] = minimum(M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j]);
				where i <= k <= j-1
			P[i][j] = 최소치를 주는 k의 값
		}
	return M[1][n];
}

 

최적 순서를 얻기 위해서는 M[i][j]를 계산할 때 최소값을 주는 k값을 P[i][j]에 기억한다.
예를들어 P[2][5] = 4인 경우의 최적 순서는 (A2 A3 A4) A5이다. 구축한 P는 다음과 같다.

따라서, 최적 분해는 (A1((((A2 A3) A4) A5) A6))이다.

void order(index i, index j) {
	if (i == j) cout << “A” << i;
	else {
		k = P[i][j];
		cout << “(”;
		order(i,k);
		order(k+1,j);
		cout << “)”;
	}
}

---