[알고리즘][동적계획법] 동적계획법 #4 Matrix-Chain Multiplication

학습목표
1. n개의 행렬의 곱 A1, A2, ... , An을 계산하는 최적의 순서의 순환식을 정의
2. Java언어 기반 행렬의 곱셉 최소 계산 동적계획법 구현

 

1. 행렬의 곱셈

p*q 행렬 A와 q*r 행렬 B를 곱하여 p*r 행렬 C를 계산한다고 가정할때 코드는 다음과 같습니다.

void product(int A[][], int B[][], int C[][]) {
	for (int i=0; i<p; i++) {
		for (int j=0; j<r; j++) {
			C[i][j] = 0;
			for (int k=0; k<q; k++)
				C[i][j] += A[i][k]*B[k][j;]
			}
		}
	}
}

위와 같은 반복문 수행시 곱셈 연산의 횟수는 p * r * q일 것입니다.

 

예를 들어 행렬 A, B, C의 행*열크기가 다음과 같다고 가정합니다.

A = 10 * 100
B = 100 * 5
C = 5 * 50

 

행렬의 곱은 교환법칙은 성립되지 않지만 결합 법칙은 성립되기 때문에 세 행렬의 곱 ABC는 두가지 방법으로 계산이 가능합니다.

세 행렬의 곱 ABC의 두가지 계산방법 (결합법칙 성립)
1. (AB)C
2. A(BC)

 

그런데 주목할점은 위의 두가지 계산방법이 차이가 많이 발생한다는 점입니다. 다음은 세 행렬의 곱 ABC의 두가지 계산방법의 곱셈 연산 횟수를 계산한 것입니다.

세 행렬의 곱셈 연산 횟수
1. (AB)C = {(10*100) * (100*5)} * (5*50) // 10*100*5 곱셈 연산 횟수
         = (10*5) * (5*50)               // 10*5*50 곱셈 연산 횟수
         = 10 * 50                       // 최종 곱셈 연산 횟수 = (10*100*5) + (10*5*50)
                                         //                     = 7500

2. A(BC) = (10*100) * {(100*5) * (5*50)} // 100*5*50 곱셈 연산 횟수
         = (10*100) * (100*50)           // 10*100*50 곱셈 연산 횟수
         = 10 * 50                       // 최종 곱셈 연산 횟수 = (100*5*50) + (10*100*50)
                                         //                     = 75000

위의 계산 결과를 통해서 (AB)C 계산방법과 A(BC) 계산방법이 10배 차이나는 것을 알 수 있습니다.

 

만약 n개의 행렬의 곱 A1, A2, ..., Ai , An이 있다면 최소의 곱셈 연산 횟수가 나오기 위한 최적의 순서를 생각해볼 수 있다.

 

여기서 Ai는 p_i-1 * p_i 행렬입니다. 예를 들어 A1 = p_0 * p_1, A2 = p_1 * p_2인 것을 알 수 있습니다. 그래야지 행렬의 곱이 계산되기 때문입니다.

 

2. Optimal Substructure

행렬의 곱셈의 최소 곱셈 연산 횟수를 구하기 위해서 행렬의 곱셈이 Optimal Substructure를 가지고 있는지 확인합니다. Optimal Substructure란 행렬의 곱셈 A1, A2, ..., An이 전체적인 문제라면 이 행렬의 부분문제의 최적해가 전체의 최적해로 계산이 가능한지를 의미합니다. 

 

행렬의 곱셈 A1, A2, ..., An에서 주목할점은 마지막 행렬 An은 부분적인 행렬의 곱셈 A1, A2, ... , An-1의 결과와 곱셈연산을 수행한다는 점입니다. 이는 전체적인 문제가 부분적인 문제로 나누어질 수 있다는 것을 의미하며 전체적인 문제의 행렬의 곱을 다음 그림과 같이 표현이 가능하다는 점입니다.

위의 그림에서 X와 Y 행렬을 계산하는 과정에서 최소 곱셉 연산 횟수를 계산하여 저장한다면 전체적인 문제를 해결할 수 있을 것입니다.

 

다음 순환식은 위의 그림을 기반으로 정의한 순환식입니다.

위의 그림에서 p_i-1*pk*pj 는 X행렬과 Y 행렬의 곱셈 연산의 횟수입니다.

 

위 순환식의 게산순서를 그림으로 표현하면 다음과 같습니다.

m[3,7] = min(m[3,k] + m[k+1, 7] + p_2 * p_k * p_7)

예를 들어 k=4라면 m[3,4] + m[5,7] + p_2 * p_4 * p_7이 됩니다. 이는 A3A4 행렬의 최소 곱셈 연산횟수(X) + A5A6A7 행렬의 최소 곱셈 연산횟수(Y) + XY 행렬의 곱셈 연산 횟수의 합계중 최소값이 됩니다.

 

2. Java언어 기반 동적계획법 구현

public class Driver {
	public static int[][] m;
	public static int[] p;
	
	public static int martixChain(int n)
	{
		for(int i=1;i<=n;i++)
		{
			m[i][i] = 0;
		}
		
		for(int r=1; r<=n-1; r++)
		{
			for(int i=1; i<=n-r; i++)
			{
				int j = i + r;
				m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];
				
				for(int k=i+1; k<=j-1; k++) {
					if(m[i][j] > m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j])
					{
						m[i][j] = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; 
					}
				}
			}
		}
		
		return m[1][n];
	}
	public static void main(String[] args) {
		int n = 3;
		m = new int[n+1][n+1];
		// P0 = 10
		// P1 = 100
		// A1 = P0 * P1 = 10 * 100
		p = new int[]{10,100,5,50};
		
		System.out.println(martixChain(n));
	}

}

7500

 

References

source code : https://github.com/yonghwankim-dev/inflearn_algorithm/tree/master/dp/dp04_martix_mul
[인프런] 영리한 프로그래밍을 위한 알고리즘 강좌