Chained Matrix Multiplication

[WonYong-Jang]

연쇄 행렬 최소 곱셈 알고리즘

두개 이상의 행렬을 곱할 때, 최소 곱셈 횟수를 구하는 문제

-> 행렬의 곱셈은 아래와 같이 결합법칩이 성립한다.
      A*(B*C) = (A*B)*C
 그러나, 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라진다.

예를들어 설명하면,
행렬 A,B,C,D 4개가 존재한다.
각각 행렬의 차수는 20x1, 1x30, 30x10, 10x10이라고 한다.
4개의 행렬은 여러가지 방법으로 곱할 수 있지만,
다음 4개의 경우에 대하여 생각해볼때, 곱셈 횟수를 비교하면 아래와 같다.

((AB)C)D) = (20130) + (203010) + (201010) = 8,600
A(B*(CD)) = (301010) + (13010) + (20110) = 3,500
(AB)(CD) = (20130) + (301010) + (203010) = 9,600
(A*((BC)D) = (13010) + (11010) + (20110) = 600

위와 같이 곱셈을 하는 순서에 따라 600~9600번의 곱셈 횟수가 나오게 되는데,
그 중 최소 곱셈 횟수는 600번이다.

점화식

풀이

위 관계식을 아래의 행렬로 하나씩 예를 들어보자.
A(20x1),B(1x30),C(30x10),D(10x10) 일때,
d0=20, d1=1, d2=30, d3=10, d4=10

1. M[1][2] (행렬 A~B까지의 곱의 횟수) (1<=k<=1)
   = minimum(M[1][k] + M[k+1][2] + d0dkd2
   = M[1][1] + M[2][2] + d0d1d2
   = 0 + 0 + 20130
   = 600

2. M[2][3](행렬 B~C까지의 곱의 횟수) (2<=k<=2)
   = minimum(M[2][k] + M[k+1][3] + d1dkd3)
   = M[2][2] + M[3][3] + d1d2d3
   = 0+0+13010
   = 300

3. M[1][3](행렬 A~C까지의 곱의 횟수)(1<=k<=2)
   = minimum(M[1][k] + M[k+1][3] +d0dkd2
   = minimum(M[1][1] + M[2][3] + d0d1d3, M[1][2] + M[3][3] + d0d2d3)
   = minimum(0 + 300+20110, 600+0+203010)
   = minimum(500, 6600)
   = 500

행렬 A~D까지의 곱의 횟수 (M[1][4])는
M[1][4] = minimum( M[1][1] + M[2][4] + d0d1d4, M[1][2] + M[3][4] + d0d2d4, M[1][3] + M[4][4] + d0d3d4)
M[1][4]를 구하려면
M[1][1]~M[1][4]의 값이 필요하고,(구하려는 값의 테이블 좌측값)
M[2][4]~M[4][4]의 값이 필요하고,(구하려는 값의 테이블 아랫값)

M[i][j]의 값은,
대각선을 하나씩 증가시키며 아래와 같이 구할 수 있다.

참고링크 :

http://huiyu.tistory.com/entry/DP-%EC%97%B0%EC%87%84%ED%96%89%EB%A0%AC-%EC%B5%9C%EC%86%8C%EA%B3%B1%EC%85%88-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[WonYong-Jang]

행렬 곱셈 순서 (백준)

for(int i=0; i<N; i++)
{
	st = new StringTokenizer(br.readLine());
	num1 = Integer.parseInt(st.nextToken());
	num2 = Integer.parseInt(st.nextToken());
	d[i] = num1;
	d[i+1] = num2;
}
		
for(int diagonal=0; diagonal < N; diagonal++) // 대각선 
{
	for(int i=1; i<= N - diagonal; i++) // (1,1) (2,2) (3,3) (1,2) (2,3) (1,3) 순서 
	{
		int j = i + diagonal;
		if(i == j) {
		dp[i][j] = 0;
		continue;
                 }
	}
	dp[i][j] = INF;
	for(int k= i; k <= j-1; k++) //dp[1][4] ==> (1,1)(2,3)/ (1,2)(3,3)/ (1,3)(4,4) 순으로 검사 
	{
		dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + (d[i-1]*d[k]*d[j]));
	}

}
System.out.println(dp[1][N]);