개요

Chained Matrix Multiplication)은 여러 행렬의 곱셈 순서를 최적화하여 계산 비용을 최소화하는 문제이다

행렬 곱셈은 결합법칙을 따르기 때문에 곱셈 순서를 자유롭게 바꿀 수 있지만 그러나 곱셈 순서에 따라 계산 복잡도가 크게 달라지므로, 최적의 순서를 찾는 것이 중요함

전략

Dynamic Programming(동적계획법)을 사용하여 해결할 수 있다

행렬간의 곱을 부분문제들로 나누고 값들을 이용하여 최적 비용을 찾는것이 목표

구현

Input:
A1 (10x20)
A2 (20x5)
A3 (5x15)
A4 (15x30)

#include <stdio.h>
#define MAX 100
int C[MAX][MAX];
int INF =10000;
int answer[3];
//Chained Matrix Multiplication
int chainedMatrixMulitiplication(int num) 
{
	int d[MAX];
	int i, j, k, L, temp;
	
	//d0 ~ d4
	d[0] =10, d[1] =20, d[2] =5, d[3] =15, d[4] =30;
	//initialization
	for(i=1; i<=num; i++)
	{
		C[i][i] =0;
	}
	//diagonal loop
	for (L=1; L<num; L++) 
	{ 
		for (i=1; i<=num-L; i++) 
		{
			j = i+L;
				
			C[i][j] = INF; 
			
			//최저값 갱신 
			for (k=i; k <= j-1; k++) 
			{
				temp = C[i][k] + C[k+1][j] + d[i-1] * d[k] * d[j];
				if (C[i][j] > temp) 
				{
					C[i][j] = temp;
					answer[0] = i;
					answer[1] = k;
					answer[2] = j;
				}
			}
		}
	}
	return C[1][num];
}
int main() {
	int num =4;
	int result = chainedMatrixMulitiplication(num);
	int i, j;
	
	//행렬 출력 
	printf("M    ");
	
	for(i =1; i<=num; i++)
		printf("%-5d", i);
	
	printf("\n");
	
	for (i =1; i <= num; i++) 
	{
		printf("%-5d", i);
		for (j =1; j <= num; j++) 
			printf("%-5d", C[i][j]);
	
		printf("\n");
	}
	printf("\n");
	
	//최종해 출력 
	printf("Final Solution : %d\n\n", result);
	//결과 출력 
	printf("Implicit Order for Matrix Multiplication : (");
	printf("(");
	for (i =1; i<answer[1]; i++) 
	{
		printf("A%d X ", i);
	}
	printf("A%d", i);
	
	printf(")");
	printf(" X ");
	printf("(");
	for (i = answer[1]+1; i<answer[2]; i++) 
	{
		printf("A%d X ", i);
	}
	printf("A%d)", i);
	printf(")");
	
	return 0;
}