[Introduction to Algorithms] 행렬-체인 곱셈

1) 행렬-체인 곱셈이란?

-다음에 소개할 동적 프로그래밍은 행렬 곱셈 문제를 해결하는 알고리즘이다.

 행렬 곱셈을 위한 다음과 같은 n개의 행렬 체인(순서) <A1, A2, ... , An>이 주어지고,

 행렬의 곱을 계산하려고 한다. 

 

A1A2... An

 

- 먼저 n개의 행렬을 어떻게 곱할지 애매함(ambiguity)을 없애기 위해서 

  괄호로 묶고나면, 두 개의 행렬을 곱하는 표준 알고리즘을 서브 루틴으로 이용해

  위의 식의 결과를 계산할 수 있다. 

 

- 행렬의 곱은 결합 법칙이 성립하므로, 괄호를 어떤 방법으로 묶더라도 결과는 같다.

  어떤 행렬들의 곱이 하나의 행렬 또는 완전히 괄호로 묶인 두 행렬의 곱일 때

  완전하게 괄호로 묶였다고 한다.

  

- 예를 들어, 행렬 <A1, A2, A3, A4>의 곱 A1A2A3A4를 계산한다면,

  다음과 같이 5가지 방법으로 완전하게 괄호로 묶을 수 있다. 

 

(A1(A2(A3A4)))

(A1((A2A3)A4))

((A1A2)(A3A4))

((A1(A2A3))A4)

(((A1A2)A3)A4)

 

- 행렬들의 체인을 완전하게 괄호로 묶는 방법에 따라 곱을 계산하는 비용에 

  큰 차이가 있을 수 있다.

  먼저, 두 개의 행렬을 곱하는 비용을 고려해보자. 

  표준 알고리즘은 다음 의사코드와 같다.

  rows와 column 속성은 행렬에서의 행과 열의 수를 나타낸다. 

MATRIX-MULTIPLY(A, B)
 if A.columns != B.rows
   error "서로 호환성 없는 차원들"
 else C를 새로운 A.rows x B.columns 행렬이라 한다. 
   for i = 1 to A.rows
     for j = 1 to B.columns
         cij = 0
         for k = 1 to A.columns
         	cij = cij + aik*bkj
     return C

 

- 두 개의 행렬 A와 B가 서로 호환성(compatible)이 있어야 곱할 수 있다.

  즉, A의 열의 개수와 B의 행의 개수가 같아야 한다.

  즉, A가 pxq 행렬이고 B가 qxr 행렬일 때, 결과 행렬 C는 pxr 행렬이 된다. 

 

- C를 계산하는데 걸리는 시간은 스칼라 곱 횟수 pqr에 의해 결정된다.

  이후부터는 행렬-체인 곱의 비용을 스칼라 곱의 횟수로 나타낸다.