[Algorithm] 연속된 행렬 곱셈

오늘의 포스팅은, 동적계획 알고리즘을 이용한 연속된 행렬곱셈이다.

 

---

문제

n개의 연속된 행렬곱셈 M = M1M2M3...Mn에서 스칼라 곱셈 횟수가 최소가 되는 곱셈 순서를 찾는 알고리즘

 

 

💡행렬곱셈의 원칙

• 행렬곱셈 C = AB 의 기본적인 요건은 A의 열의 개수와 B의 행의 개수가 같음
• A(p x r) x B(r x q) = C(p x q) 
  • 스칼라 곱셈은 모두 ( p x r x q ) 번

 

 

무작위 기법

• 모든 행렬 곱셈 순서를 구하여, 각각의 스칼라 곱셈 횟수를 계산하여 비교
• Xn = (n개의 행렬을 곱하는 가능한 모든 곱셈 순서의 수) 라면,
• Xn은 다음의 세경우의 수를 합한 것
  1. M1을 가장 나중에 곱하는 경우의 수  = M1(M2M3...Mn)의 순서로 곱 = M2M3...Mn을 곱하는 경우의 수 = X(n-1)
  2. Mn을 가장 나중에 곱하는 경우의 수 = (M1M2M3...M(n-1))Mn의 순서로 곱 = M1M2...M(n-1)을 곱하는 경우의 수 = X(n-1)
  3. 나머지 모든 경우의 수 = a x {(M1M2)(M3...M(n-1)Mn), ...., ....}
• 따라서
  • Xn = X(n-1) + X(n-1) + a 
  • Xn >= 2X(n-1) >= 2^2X(n-2) >= 2^3X(n-3) >= ... >= 2^(n-2)X(2) (두 행렬을 곱하는 가짓수 X(2) = 1)
  • Xn = 2^(n-1)
  • 지수 경우의 수로 굉장히 많음..!

 

 

 

💡최적 부분 구조 : 부문제의 최적해가 더 큰 문제의 최적해를 구하는데 사용될 수 있는지 알아보자

• 이전에 2~3개의 적은 수의 행렬의 곱의 최적 순서가 다음 상위 여러개의 행렬의 곱의 최적 순서에 영향을 미친다
• 하위 문제에서의 최적순서(해)를 저장하여 다음 상위 문제에서의 최적순서(해)를 구할 때 사용한다.
• 행렬의 수가 많은 곱은 작은 행렬들의 곱으로 이루어져있다 -> 부분문제들이 겹쳐져있다.
• 따라서 연속된 행렬 곱셈 문제는 최적 부분 구조를 갖는다.

 

 

💡순환적 정의

• 최종 목표 : n개의 연속된 행렬 M1M2...Mn에 대한 최적 곱셈 순서
• 최우선 목표 : M1M2M3...Mn에 대한 최소의 스칼라 곱셈 횟수
  • ci = 행렬 Mi의 열의 수,
    • Mi와 인접한 M(i+1)의 행의 수 = ci (M1의 행의 수 = c0)
    • Mi는 c(i-1) x ci 행렬
    • 행렬곱셈 MiMi+1...Mj-1Mj의 결과는 어떤 순서로 곱해도 c(i-1)xcj 행렬
• 순환구조! 행렬의 곱셈에서는 교환 법칙이 성립하지 않으므로, 인접한 행렬끼리 곱해야함. 따라서,
• 일반화 : n개의 연속된 행렬곱셈 MiM(i+1)...M(j-1)Mj에서의 최소의 스칼라 곱셈 횟수 = 다음의 j-i개의 경우 최소의 스칼라 곱셈 횟수 (괄호안의 행렬 곱셈도 최적의 순서로 곱해야 함)
  • (Mi) (Mi+1Mi+2...Mj-1Mj) -> c(i-1)xci 행렬과 ci x cj 행렬의 곱
  • (MiMi+1) (Mi+2Mi+3...Mj-1Mj) -> C(i-1)xc(i+1) 행렬과 c(i+1)xcj행렬의 곱
  • ...
  • (Mi...Mj-1)Mj -> c(i-1)xc(j-1)행렬과 c(j-1)xcj 행렬의 곱

 

💡최소 스칼라 곱셈 횟수 S(i,j) 정리

i=j -> 행렬이 하나밖에 없는 경우 -> 스칼라 곱셈 횟수 0

 

 

 

 

➰중첩된 부문제와 분할 정복

• 연속된 행렬 곱셈 문제는 중첩된 부분제 특성을 가짐
• Ω(2^n)

• int mat_chain_X_DC(int C[], int i, int j){
  	int min = 무한, k, s;
      if (i==j) return 0;
      for( k=i;k<=j-1;k++ ){
      	s = mat_chain_X_DC(C,i,k) + mat_chain_X_DC(C,k+1, j) + C[i-1]*C[k]*C[j];
          if(s<min) min = s;
      }
      return min;
  }

 

 

 

 

💡동적 계획법

• 최우선 목표 : n개의 연속된 행렬 곱셈 M1M2....Mn에 대한 최소 스칼라 곱셈 횟수 S(1,n)을 계산하는 것
• 부문제의 최적해 S(i,j)을 저장하기 위해서는 2차원 배열이 필요
• 2차원 배열의 원소 S[i][j]에 S(i,j)의 값을 저장하고 필요할 때마다 재사용
• 가정 : 1차원 배열의 원소 C[k]에는 행렬 Mk의 열의 수를 저장
  • 열의 수를 기준으로 scala 곱셈의 연산과 Matrix크기를 정의했음!
• 따라서 2차원 배열에 저장될 값들은 다음과 같이 정의
  

  

• 배열 S에는 최소 스칼라 곱셈 횟수만 저장될 뿐!
• 최종 목표인 최적 곱셈 순서에 관한 어떤 정보도 없음 -> 최소 스칼라 곱셈 횟수에 대한 곱셈 순서를 기억할 배열이 필요
  • S[i][j] 의 값을 최소로 만든 k를 배열 T[i][j]에 저장
  • Mi...Mj의 스칼라 곱셈 횟수가 최소인 경우가 (Mi...Mk)(Mk+1...Mj)라면 T[i][j]=k로 지정
  • T[1][n]부터 거꾸로 조사해 내려가면 곱셈 순서를 알아낼 수 있음

 

 

 

 

💡알고리즘

• 대각선
• 각 대각선 별로 채워야 하는 원소의 수
• 위의 모든 S[i][j]를 보면, i와 j는 항상 대각선 d(=j-i)만큼 차이

 

💡의사코드 (동적계획법)

int mat_chain_X_DP(int C[], int n){
	int S[MAX][MAX], T[MAX][MAX];
    int d,i,j,k;
    for(i=1;i<=n;i++) S[i][j]=T[i][j]=0;	//배열 S와 T의 대각선 0의 원소들을 0 초기화
    for(d=1;d<=n-1;d++)		//대각선 수-1 만큼 반복 : n-1개 -> 대각선 1부터 대각선 n-1까지 채워나감
    	for(i=1;i<=n-d;i++){	//한 대각선 원소의 수만큼 반복, i가 1씩 증가하므로, j=i+d (d=j-i)로 정해주면 S[i][j]위치가 정확히 결정됨.
        	j=i+d;
            S[i][j] = 무한대;
            // S[i][j]순환 정의에 따라, j-i개의 경우를 대상으로 최소 곱셈횟수와 최적 분할점을 구함.
            for(k=i;k<=j-1;k++){
            	if(S[i][k]+S[k+1][j]+C[i-1]*C[k]*C[j] < S[i][j]){
                	S[i][j] = S[i][k]+S[k+1][j] + C[i-1]*C[k]*C[j];
                    T[i][j] = k;
                }
            }
        }
    return S[1][n];
}

 

 

 

⏰복잡도

• 복잡도를 결정하는 부분은 위의 의사코드의 가장 내부의 for문이다.

  

 

---

➕연속된 행렬 최적의 곱셈 순서 구하기 (의사코드)

void optimal_order(int T[][MAX], int i, int j){
	if(i==j) printf("M%d", i);
    else{
    	printf("(");
        optimal_order(T,i,T[i][j]);
        optimal_order(T,T[i][j]+1,j);
        printf(")");
    }
}

---

Reference

• 서울과학기술대학교 컴퓨터공학과 알고리즘 수업
• 알기쉬운 알고리즘 도서