Matrix chain multiplication(행렬 최소 곱셈 알고리즘) 간단 핵심 정리 및 수도코드!

안녕하세요.

 

 

 

Matrix chain multiplication(행렬 최소 곱셈 알고리즘)

 

길죠.

 

 

 

간단하게 설명드리겠습니다!

 

 

 

 

 

Matrix chain multiplication(행렬 최소 곱셈 알고리즘) 이란?

---

  -  M : Matrix(행렬), d : dimension(차원)

 

  -  Matrix는 1 ~ 4 까지 4개가 존재하고, dimension은 0 ~ 4 까지 5개가 존재한다고 하자.

 

  -  각 Matrix의 왼쪽 dimension 은 행, 오른쪽 dimension 은 열이다.

 

  -  위 알고리즘이 성립하기 위한 필수 조건은 위 그림처럼

   

 

    1)  이전 Matrix의 열 과 다음 Matrix의 행 이 같다.

    2)  이전의 이전 Matrix의 열과 이전 Matrix의 행이 같다.

 

 

이다. 

 *** 행렬의 곱셈을 위한 조건과 동일하다.

 

 

 

 

 

즉,

 

  -  이와 같이 행렬이 존재할 때, 각 행렬(Matrix) 을 곱해야 할 때 최소로 곱할 수 있는 횟수를 구하는 알고리즘

  *** 최소로 곱할 수 있는 횟수 = 연산 횟수

 

 

예를 들어

 

  M1 = 4 x 3 

  M2 = 3 x 5 

 

에서 M1 과 M2 를 곱했을 때, 연산 횟수는

 

  4 x 3 x 5 = 60 가지 가 된다.

 

 

 

그렇지만 행렬 특성 상 두 개의 행렬끼리만 곱이 가능하다.

 

그렇기 때문에

 

M1 , M2, M3, M4  4개의 행렬을 곱하려고 한다면

 

 

  1)  ((M1 x M2) x M3) x M4

  2)  (M1 x M2) x (M3 x M4)

  3)  (M1 x (M2 x M3)) x M4

  4)  M1 x (M2 x (M3 x M4))

  5)  M1 x ((M2 x M3) x M4)

 

 

총 5가지 경우의 수가 생긴다.

 

 

 

그리고 곱셈 연산의 횟수를 전부 더한 결과가 모든 행렬의 곱셈 연산 횟수 이므로

위 표처럼 연산 방법에 따라 곱셈의 수가 천차만별이다.

 

 

 

 

 

그럼 어떻게하면 최소인 곱셈의 수를 구할 수 있는가?

 

 

 

 

구하는 방법

---

   -  DP(동적 프로그래밍) 방식을 통해 구할 수 있다.

 

 

 

  -  DP 점화식. M[i][j] 는 행렬 Mi부터 Mj 까지의 곱셈 연산 횟수 를 의미한다.

 

  -  d는 dimension을 의미한다. 맨 위 그림처럼 dimension은 Matrix의 개수보다 1 많다.

 

 

 

 

소스코드(JAVA)

---

  -  시간복잡도 : O(n^3)

 

  -  l, i, j가 헷갈리는데, 저렇게 알고리즘이 구성된 이유는

 

위 그림처럼 대각선으로 구하기 위함이다.

 

즉, dp[1][2] 는 가능해도 dp[2][1] 은 불가능하기 때문이다.

*** M2 x M1 은 될 수 없다. (dimension이 다르기 때문에)

 

 

 

 

 

이상입니다.

 

 

 

감사합니다!