Matrix chain multiplication

Explain

• dynamic programming 기법 중 하나이며 주어진 연속되는 행렬의 곱셈에서 최적의 방법을 찾아내는것이 목표이다.
• \(q*p,p*r\) 크기의 행렬의 곱셈 연산의 횟수는 \( q*p*r \) 인점을 기억해야 한다.

기본적으로 행렬의 곱은 associativity하므로 연속되는 행렬의 곱 ABCD 에 대해

\(((AB)C)D = ((A(BC))D) = (AB)(CD) = A((BC)D)\)가 성립한다. 이때 각각의 연산마다의 곱셈 연산의 횟수는 다르므로 이중에서 최소 연산 횟수를 가지는 방법을 찾아야 한다.

예를 들어 \(A = 10*30, B = 30 * 5, C = 5 * 60 \) 의 크기를 가지는 행렬의 곱셈을 진행 할때

$$(AB)C = (10*30*5) + (10*5*60) = 1500 + 3000 = 4500(count\ of\ operations)$$

$$A(BC) = (30*5*60) + (10*30*60) = 9000 + 18000 = 27000(count\ of\ operations)$$

위처럼 괄호의 위치마다 연산의횟수는 크게 차이가 나기때문에 최적의 방법을 찾아내는것이 중요하다.

Approach

• 만약 일반적인 방식으로 모든 경우의수를 비교하는 방식으로 진행할경우 \(\theta(n-2)!\) 의 시간 복잡도를 보이므로 비효율적이다.
• D&C 방식으로 하여 문제를 풀 경우 중복연산이 매우 많이 발생하며 \(\theta(n^3)\) 의 시간 복잡도를 보인다.
• 이떄 dynamic programming 방식을 활용하여 풀이하도록 한다.

Notation 

• \(N =\) 곱셈하는 행렬의 크기 
• \(A(1...N) =\) 행렬
• \(d(0...N) =\) 행렬의 크기 \(A(1) = d(0) * d(1)\) 
• \(M[i,j] =\) 주어진 행렬 중 i~j까지의 곱셈시 필요한 최소 곱셈 연산 횟수
• \(P[i,j] =\) i~j까지의 곱셈시의 intermediate point

Algorithm

해당 알고리즘은 행렬의 최소 연산을위한 괄호위치를 구하는것이므로 \(d\)값 이외의 정보는 크게 중요않다.

만약, \(A_{1} ~ A_{5} \) 까지의 행렬의 곱셈이 주어졌을때. 

$$ 1.A_{1}(A_{2}A_{3}...A_{5}) = M[1,1] + M[2,5] + d_{0}d_{1}d_{5}$$$$ 2.(A_{1}A_{2})(A_{3}...A_{5}) = M[1,2] + M[3,5] + d_{0}d_{2}d_{5}$$$$ ... $$$$ 4.(A_{1}...A_{4})A_{5}) = M[1,4] + M[5,5] + d_{0}d_{4}d_{5}$$$$M[1,k] = M[k+1,6]+d_{0}d_{k}d_{5}$$$$M[1,5] = \min_{1 \ge k \ge 5}(M[1,k] + M[k+1,5] + d_{0}d_{k}d_{5}$$$$M[i,j] = \min_{i \ge k \ge j-1}(M[i,k] + M[k+1,j] + d_{i-1}d_{k}d_{j}$$

추가적으로 A1 * A1 형식의 내용은 의미가 없으므로 \(M[i,i]=0\) 이다.

Code

#include <stdio.h>
#include <limits.h>

#define MAX 6
#define INF 99999

int min(int x,int y);
void print_order(int i,int j, int P[][MAX]);

int main(void)
{
	int M[MAX][MAX]; // 최소 곱셈 횟수
	int D[MAX+1] = { 5,2,3,4,6,7,8 }; // 행렬의 크기 A[0] = 5 * 2, A[1] = 2 * 3
	int P[MAX][MAX]; // 최소 곱셈시의 intermediate point
	int i,j,diag,k,mc;

	for(i=0;i<MAX;++i)
		M[i][i] = 0; 

	for(diag=1;diag<MAX;++diag)
	{
		for(i=0;i<MAX-diag;++i)
		{
			j = i+diag;
			M[i][j] = INF;
			for(k=i;k<j;++k)
			{
				mc = M[i][k] + M[k+1][j] + D[i]*D[k+1]*D[j+1];
				if(mc < M[i][j])
				{
					M[i][j] = mc;
					P[i][j] = k;
				}
			}
		}
	}

	for(i=0;i<MAX;++i)
	{
		for(j=0;j<MAX;++j)
		{
			if(i==j)
				printf("%8d",M[i][j]);
			else if(j>=i)
				printf("%5d(%d)",M[i][j],P[i][j]);
			else
				printf("%8s","NULL");
		}
		puts("");
	}

	puts("");

	print_order(0,MAX-1,P);
	
	puts("");

	return 0;
}

void print_order(int i,int j, int P[][MAX])
{
	if(i==j) printf("%c", 'A' + i);
	else
	{
		int k = P[i][j];
		printf("(");
		print_order(i,k,P);
		print_order(k+1,j,P);
		printf(")");
	}
}

int min(int x,int y)
{
	if(x<y) return x;
	return y;
}

Reference

• Wiki - Matrix chain multiplication