[알고리즘] 연쇄 행렬 곱셈 (Matrix-chain Multiplication)

연쇄 행렬 곱셈 (Matrix-chain Multiplication)

 

• i × j 행렬과 j × k행렬을 곱하기 위해서는 일반적으로 i × j × k번 만큼의 기본적인 곱셈이 필요하다.
• 연쇄적으로 행렬을 곱할 때, 어떤 행렬곱셈을 먼저 수행하느냐에 따라서 필요한 기본적인 곱셈의 횟수가 달라지게 된다.
• 예를 들어서, 다음 연쇄행렬곱셈을 생각해 보자:
  • A1 × A2 × A3
  • A1의 크기는 10 × 100이고, A2의 크기는 100 × 5이고, A3의 크기는 5 × 50라고하자.
  • A1 × A2를 먼저 계산한다면, 기본적인 곱셈의 총 횟수는 7,500회
  • A2 × A3를 먼저 계산한다면, 기본적인 곱셈의 총 횟수는 75,000회
  • 따라서, 연쇄적으로 행렬을 곱할 때 기본적인 곱셈의 횟수가 가장 적게 되는 최적의 순서를 결정하는 알고리즘을 개발하는 것이 목표이다.
    
    
• 알고리즘: 가능한 모든 순서를 모두 고려해 보고, 그 가운데에서 가장 최소를 택한다. (동적계획법 DP)
• 시간복잡도 분석: 최소한 지수(exponential-time) 시간
• 증명:
  • 개의 행렬(A1, A2, ..., An)을 곱할 수 있는 모든 순서의 가지 수를  이라고 하자.
  • 만약 A1이 마지막으로 곱하는 행렬이라고 하면, 행렬 A2, ..., An을 곱하는 데는  개의 가지수가 있을 것이다.
  • An이 마지막으로 곱하는 행렬이라고 하면, 행렬 A1, ..., A(n-1)을 곱하는 데는 또한  개의 가지수가 있을 것이다.
  • 그러면,  이고  이라는 사실은 쉽게 알 수 있다.
  • 따라서 
    
    
• 를 행렬 의 열(column)의 수라고 하자. 그러면 자연히 의 행(row)의 수는 가 된다.
• 의 행의 수는 라고 하자. 그러면, 다음과 같이 재귀 관계식을 구축할 수 있다.
  • 
  • = 일 때,  부터  까지의 행렬을 곱하는데 필요한 기본적인 곱셈의 최소 횟수
  • 
  • if