4-(1) Dynamic Programming 2)Matrix Chain Multiplication

이 챕터에서는 Dynamic Programming 문제 카테고리에 속하는 Matrix Multiplication 문제에 대해 다뤄보고자 한다.

 

(1)Intuition: 행렬의 연쇄곱 ABCDE같은 것을 생각해보자.(행렬곱이 conformable하다는 것을 가정하고) 이 행렬곱은 (((AB)C)D)E로 계산하든, A(B(C(DE)))로 계산하든, 그 결과는 동일하지만, 하는 연산의 횟수가 동일하지 않다. 우선,

mxn행렬 A와 nxr행렬 B를 생각해보면 AB를 계산하는데 걸리는 시간은 mnr이다. (loop를 작성해보면 3중 loop가 보여서 명확히 알 수 있을 것이다.) 또한, 이를 바탕으로 밑의 그림과 같은 예제를 보면 행렬곱의 순서에 따라 연산횟수가 달라지는 것이 명백히 보일 것이다.

<그림1: 행렬 곱 연산 순서에 따라 달라지는 연산 횟수>

따라서 이런 연산 횟수를 줄이는 것이 행렬의 연쇄곱에서 중요해진다.

 

(2) 문제

Matrix Chain Multiplication이란 다음과 같이 제시되는 문제를 말한다.

 

Q: 행렬곱 A₁A₂A₃...A_n이 주어졌을 때 최소 연산 횟수를 구하고 그 순서를 출력하여라 

Input: A_i의 행 차원이 p_i-1,열 차원이 p_i로 주어진 배열 p[0:n], (이런 경우 행렬은 n개가 주어진 것이다.)

Output: 연산의 최소 횟수, 연산의 순서

 

이 문제를 풀기 위해 다음과 같은 변수들을 정의한다.

<그림2: 변수정의>

S[i][j]는 특히 무엇을 말한 것인지 이해가 안 될텐데, 우리가 행렬 곱을 할 때 Optimal한 순서에서 마지막으로 곱이 이루어지는 위치를 얘기하는 변수이다. (이해가 안 될 수도 있는데, 뒤의 해결 방식 설명을 보면 이해가 될 수도 있다.)

 

자 그럼 이 문제의 성질을 생각해보자, DP를 적용하기 위해 문제가 만족해야 하는 Property로는 크게 두 가지가 있었는데, 그 성질을 만족하는지 확인해보면 될 것이다.

(1) Optimal SubStructure: 내가 Subproblem의 Optimal solution을 알 때 그것을 가지고 현재 Problem의 solution을 만들 수 있는가?

(2) Overlapping Subproblem: subproblem이 Overlapping되는가?

 

우선, 문제를 좀 생각해보면 곱이 이루어지는 지점의 순서를 구하면, 곱의 순서를 구하는 것과 마찬가지가 된다. 이 때 내가 마지막으로 곱이 이루어져야 하는 곳을 안다면, 그 지점을 기준으로 행렬곱을 왼쪽과 오른쪽으로 나눌 수 있게 된다. 그러면, 왼쪽과 오른쪽의 solution, 즉 최적의 곱 순서를 안다면 이것을 합쳐서 최종 solution을 만들 수 있게 된다. 이것이 Optimal Substructure 성질이다. Overlapping substructure도 이런 관점에서 생각해보면 1~n의 최적곱을 알고 싶을 때와 2~n-1의 최적곱을 알고 싶을 때 겹치는 문제가 생길 것이다. 따라서 두가지 성질을 모두 만족한다.

 

그럼 어떻게 m[1,n]을 구하면 되는걸까? 생각해보면 최종곱 k가 어디서 날지 모르기 때문에 m[i,j]는 다음과 같이 구하면 된다.

P_i-1*P_k*P_j는 k에서(A_k의 오른쪽) 잘렸을 때 (A_i*....*A_k)(A_k+1A_j)의 곱에서 왼쪽 항의 행의 차원이 p_i-1이고, 왼쪽 항의 열=오른쪽 항의 행의 차원이 p_k가 되며 오른쪽 항의 열의 차원이 P_j가 됨을 이용하여 계산한 것이다. 

이를 bottom up으로 구현하려면 다음과 같이 하면 된다.

bottom-up으로 하려면 m[i,j]에서 그 길이가 짧은 것부터 해야한다. m[i,j]=m[i][j]인 2차원 배열을 준비하여 구현하였다. 

우선, 모든 m[x][x]=0이다. 이것은 그냥 맨 처음에 채워주면 된다. 또한 길이라는 변수를 l로 둔다면, 행렬곱의 길이는 1부터 n-1까지 가능하다. 따라서 그 for loop가 하나 돈다. 그 다음에는 처음 시작하는 것을 i로 잡았을 때 m[i,i+l]을 결정하는 for loop를 i가 1부터 n-1까지 돌리면 된다. 그것이 위의 matrix그림에서 for-loop이 돌아가는 순서를 필기해놓은 것이다.

 

그것을 구현한 코드는 테스트 코드를 포함하여 밑과 같다.

#include<iostream>
using namespace std;
const int INFINITE = 10000000000;

int** matmult(int* p,int n,int** s) { //bottom up fashion으로 가자.
	/*
	총 n개의 matrix
	p의 크기는 n+1즉 p[0]~p[n]이 존재한다.
	A_i는 dimension p_i-1 * p_i를 갖는다.
	m[i,j]의 정의: A_i...A_j를 계산하는데 걸리는 시간
	*/
	int** m = new int*[n+1] ;// m[i][j]:Ai...Aj를 계산하는데 걸리는 최소 시간 
//	int** s = new int* [n+1];//s[i][j]:Ai,,,,,Aj를 계산할 때 마지막으로 AkAk+1에서 곱이 이루어지는 경우 k를 저장
	for (int i = 0; i <= n; i++) {
		m[i] = new int[n+1];
	}
	for (int i = 1; i <= n; i++) {
		m[i][i] = 0;	//basis case
	}
	int j;
	for (int l = 1; l<= n-1; l++) {
		for (int i = 1; i <= n - l; i++) {
			j = i + l;
			m[i][j] = INFINITE; //최소를 골라야 하니까 무한대로 설정해놓는다.

			for (int k = i; k < j; 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];
					s[i][j] = k;
				}
			}
		}
	}
	return m;
}

void PrintMultorder(int** s,int i,int j) {
	if (i == j) {
		cout << "A" << i;
		return;
	}
	int k = s[i][j]; // k번째 위치에서 잘림.
	cout << "(";
	PrintMultorder(s, i, k);
	PrintMultorder(s, k + 1, j);
	cout << ")";
}
int main() {
	int n=4;
	int p[] = { 10,100,5,50,30 };
	int** s = new int*[n+1];
	for (int i = 0; i <= n; i++) {
		s[i] = new int[n + 1];
	}
	int** m = matmult(p, n, s);
	for (int i = 0; i < n; i++) {
		cout << "A" << (i + 1) << ": " << p[i] << "X" << p[i + 1]  << endl;
	}

	cout << "총 연산 횟수" << m[1][n] << endl;
	cout << "계산하는 방법 " << endl;
	PrintMultorder( s, 1, n);
	return 0;
}

또한 s[i][j]=k는 자르는 곳을 파악한 건데 이는 나중에 이 글에 추가하겠다.