[알고리즘] 동적프로그래밍 Part 3 - 연쇄행렬곱셈

다음의 사실을 이용하여 연쇄행렬곱셈의 최적의 곱셈 순서를 구한다.
1. n*m 행렬과 m*l을 곱하기 위해서 필요한 곱셈들의 수는 n*m*l이다.
2. 행렬의 곱셈은 겹합적이다. (A*B)*C = A*(B*C)

위의 사실을 가지고 3개이상의 행렬 곱셈을 수행하는대 순서에 따라서 곱셈의 수가 큰차이가 있음을 발견했다.
ex) A(100*1), B(1*100), C(100*5) 행렬이 있다.
     ⓐ (A * B) * C 의 곱셈의 수는 A*B를 구하는데 곱셈의 수 "100*1*100"에 A*B에 의해서 생성된 배열(100*100)
        행렬에 C를 곱하여 해를 구하는데 필요한 곱셈의 수 "100*100*5"를 더한 수 "60,000"이다.
     ⓑ A * (B * C) 의 곱셈의 수는 B*C를 구하는데 곱셈의 수 "1*100*5"에 A*B에 의해서 생성된 배열(1*5)  
         행렬에 A를 곱하여 해를 구하는데 필요한 곱셈의 수 "100*1*5"를 더한 수 "1,000"이다.
      위 경우 곱하는 순서에 따라서 59,000번의 곱셈의 수가 차이가 나게 된다.

원 문제 : n개의 행렬들의 곱셈 M1 * ... * Mn을 수행하는데 필요한 곱셈 횟수의 최소치를 구하는 것
일반화 : Mi * ... * Mj를 수행하는데 필요핸 곱셈의 최소치를 구하라.
            (가정, Mi는 R(i-1) * Ri 행렬이다)

해법 A : 분할 정복기법을 사용
 - i <= k < j 인 어떤 k에 대해 행렬곱을 다음과 같이 두개의 행렬 곱들로 나눈다.
 (Mi * ... * Mk) * (M(k+1) * ... * Mj) 
 즉 Mi부터 Mj까지를 곱하는데의 최소치는 k가 i+1부터 j까지 가면서 구해진 곱셈의 수들중 최소값을 찾으면 된다. 
 곱셈의 수 :
  Mk를 기준으로 왼쪽행렬을 곱하는데 필요한 곱셈의 수 + 오른쪽 행렬을 곱하는데 필요한 곱셈의 수 + Ri*Rk*Rj  
 
 슈도코드 :
 int Matmult(int i, int j){

   int k;
   if ( i == j ) return 0;
   else return (min(Matmult(i,k)+Matmult(k+1,j) + Ri*Rk*Rj ); // k는 i+1부터 j까지 이동한다.
                 // i~k까지 행렬을 곱하는 것의 최소치 + k+1~j까지 행렬을 곱하는 것의 최소치 + Ri*Rj*Rk 
} 

해법 B : 동적 프로개래밍 해법을 구하기 위해서 행렬곱들의 순서를 정한다.
 ex) W ( 10 * 2 ) , X ( 2 * 20 ) , Y ( 20 * 5 ) , Z ( 5 * 15 )
     

  
     위는 일단 2개를 곱하는데 최소값을 구한후 이를 확장해나가며 3개, 마지막으로 4개까지 가면서 곱셈의 수를  
     구한 것이다. 
     
슈도코드 : 
// R[n] : R[0] ... R[N] 까지 각 행렬의 좌우를 입력받는다. 예를들어 3번째 배열은 R[2]*R[3]행렬이다.
for ( i = 1 ; i <= n ; i++ ){
  m[i][i] = 0;
}
for ( l = 1 ; l <= n - 1 ; l++ ){
  for ( i = 1 ; i <= n - l ; i++ ){
    j = l+i;
    for ( k = i ; k < j ; k++ ){
      if ( M[i][j] < M[i][k] + M[k+1][j] + R[i-1]*R[k]*R[j] ) {
        M[i][j] = M[i][k] + M[k+1][j] + R[i-1]*R[k]*R[j];
      }
    } 
  }
}  

필자도 이것에 대해선 이해는 했지만 완벽하지 안아서 부가설명을 못하겠다.
위의 예를 순서에 따라서 계산한 것의 그림은 다음과 같다.

소스코드도 위에서 짠 슈도코드가 전부 일 것이다.  이 소스의 효율은 세타의 N^3이고 
지속적인 알고리즘의 발달로 현재 나온 행렬곱을 푸는 알고리즘의 최고효율은 세타의 nlgn이다.