우선 2x3 행렬과 3x4 행렬을 곱해봅시다.
결과물은 2x4 행렬이 나오겠죠?
또한 곱셈의 횟수는 2 x 3 x 4 = 24입니다.
즉 i x j 행렬과 j x k행렬의 곱의 횟수는 i x j x k가 됩니다.
또 다른 예시를 들어봅시다.
A X B X C X D이고, A = 20 x 2, B = 2 x 30, C = 30 x 12, D = 12 x 8입니다.
행렬 곱셈은 결합 법칙이 성립하므로, 곱셈의 순서는 결과에 영향을 미치지 않습니다.
즉, (AB)(CD) = (A(B(CD))와 같습니다.
이때 4개의 행렬은 총 5개의 다른 순서로 곱할 수 있습니다.
A(B(CD)) : 3680
A((BC)D) : 1232
(AB)(CD) : 8880
((AB)C)D : 10320
(A(BC))D : 3120
따라서 A((BC)D)가 최적의 순서가 됨을 알 수 있습니다.
어떻게 최적의 순서를 구해야 할까요?
시작은 단순 무식한 방법으로 접근합니다.
이때 Tn이 전체 순서의 개수라고 가정한다면, T(n-1)은 A1이 없는 경우의 수라고 가정해봅시다.
따라서 Tn >= 2T(n-1)가 됩니다.
그러면 Tn >= 2^(n-2)가 되므로 지수 시간 알고리즘이 나와버립니다.
이 문제에 최적의 원칙이 적용되는지 알아보는 것은 어렵지 않습니다.
즉 n개를 곱하는 최적의 순서는 n개 행렬의 부분 집합을 곱하는 최적의 순서를 포함합니다.
예를 들어서 A1(((A2A3)A4)A5)A6)가 최적의 순서라고 가정했을 때, A2에서 A4까지 곱하는 최적의 순서는 (A2A3)A4가 될 수밖에 없습니다.
그러면 해답의 배열은 어떻게 구축해야 할까요?
M[i][j] = i < j일 때, Ai부터 Aj까지 행렬을 곱하는데 필요한 최소 횟수
M[i][i] = 0 -> 자기 자신을 곱하므로
이때 재귀 관계식을 구해봅시다.
4개의 행렬이 있다고 가정합니다.
이때 경우의 수는
A1(A2A3A4)
(A1A2)(A3A4)
(A1A2A3)A4
가 됩니다.
이 인수분해 중에서 곱셈의 횟수가 최소가 되는 순서가 최적의 해가 됨이 틀림없습니다.
따라서 M[1][4] = M[1][k] + M[k + 1][4] + d_0*d_k*d_4가 됩니다.
d_0는 첫 번째 행렬의 행, d_k는 k번째 행렬의 열, d_4는 네 번째 행렬의 열입니다.
따라서 재귀 관계식은 다음과 같습니다.
M[i][j] = minimum(M[i][k] + M[k+1][j] + d_i-1 * d_k * d_j) -> 이때 k는 i부터 j-1까지
M[i][i] = 0
시간 복잡도는 n^3입니다.
다음 글의 코드를 보시면 이해가 가실 거예요
간단하죠?
아무튼 다음 글에는 코드를 작성해보겠습니다.