Chap 5-2.연속 행렬 곱셈

연속 행렬 곱셈(Chained Matrix Multiplication)

문제 = 연속된 행렬들의 곱셈에 필요한 원소 간의 최소 곱셈 횟수를 찾는 문제

 

행렬 곱셈

(1) 두 행렬의 곱셈이란?

     두 행렬 A, B가 있다. 

     A = 10 x 20

     B = 20 x 5 라면

총 곱셈의 횟수 = 10 * 20 * 5 = 1000이다.

 

(2) 3개의 행렬 곱셈

    A = 10 x 20

    B = 20 x 5

    C = 5 x 15

행렬의 곱셈은 결합법칙 성립하므로 (A* B) * C  , A * ( B * C) 이 둘 다 성립한다.

하지만 둘의 결과값는 같지만 곱셈의 횟수는 전자가 더 적다.(과정이 다르다)

[ 행렬 곱셈의 주의점 ] 

주어진 행렬의 순서를 지켜서 “반드시 이웃하는 행렬끼리” 곱해야 한다.

 

동적 알고리즘 적용

(1) 부분 문제

행렬 A, B, C, D, E가 있다. 이 행렬들을 곱하려고 할 때의 경우들을 생각해볼 수 있다. 

단, 행렬의 곱셈의 특성 상 이웃하는 행렬끼리만 곱한다는 것을 고려하여 나올 수 있는 경우들을 생각한 것이다.  

 

알고리즘

C[i, j] = 최소 곱셈 횟수 저장 공간 

입력: 연속된 행렬 A1xA2x⋯xAn , 단, A1은 d0xd1, A2는 d1xd2 , ⋯, An은 dn-1xdn이다.
출력: 입력의 행렬 곱셈에 필요한 원소의 최소 곱셈 횟수

1. for i = 1 to n
2.     C[i, i] = 0 //자기 자신은 곱할 필요 없으므로 0이다. 
3. for L = 1 to n-1 // L은 부분 문제의 크기를 조절하는 인덱스이다.
4.     for i = 1 to n-L //부분 문제는 1개씩 줄어든다. (앞의 표에서 부분 문제의 개수 5, 4, 3, 2, 1 순으로 줄어드는 것을 표현)
5.        j = i + L
6.        C[i, j] = ∞ //일단 이렇게 두자 
7.        for k = i to j-1  
8.            temp = C[i, k] + C[k+1, j] + di-1dkdj //
9.            if (temp < C[i, j])
10.              C[i, j] = temp
11. return C[1,n] 

 

 

예시를 통해 다음과 같은 과정을 이해해보자. 

4개의 행렬을 곱하는 문제가 있다고 하자

그렇다면 L(부분 문제의 크기)는 1, 2, 3, 4개가 가능할 것이다. 

 

 

 

(1) L = 1일 때, i = 1 ~ 3,  j = 2 ~ 4

• i = 1일 때 , k = 1

temp = C[1, 1] + C[2, 2] + 10 * 20 * 5 = 1000

• i = 2일 때 , k = 2

temp = C[2, 2] + C[3, 3] + 20 * 5 * 15 = 1500

• i = 3일 때,  k = 2

temp = C[3, 3] + C[4, 4] + 5 * 15 * 30 = 2250

---

(2) L = 2 일 때,  i = 1~2 , j = 3 ~4

[ i = 1 ]

1) k = 1일 때

[i = 1, j = 3, k = 1]

temp = C[1, 1] + C[2, 3] + 10 * 20 * 15 = 4500

*C[2, 3]이라는 의미는 A2와 A3을 먼저 곱하고 A1을 곱한다는 것이다.

*10 * 20 * 15은 새로 추가된 부분의 곱셈 횟수

  ex)  A = a*b 행렬이 있고 B = c * d행렬이 있다고 하자 곱셈을 하는 횟수는 a * c * d이다. 

2) k = 2일 때

temp = C[1, 2]+ C[3, 3] + 10 * 5 * 15 = 1750

 

---

[ i = 2 ]

i = 2, j = 4 → A2 ~ A4의 행렬을 곱하라

 

(1) k = 2

temp = C[2, 2] + C[3, 4] +20 * 5 * 30 = 5250

A3, A4를 먼저 곱하고 A2를 곱하는 방법이라고 할 수 있다. 

 

(2) k = 3

temp = C[2, 3] + C[4, 4] + 20 * 15 * 30 = 5250

 

---

(3) L = 3, i = 1, j = 4

A1 ~ A4 까지 행렬이 곱을 구하자

• k = 1

temp = C[1, 1] + C[2, 4] + 10 * 20 * 30 = 11250

• k = 2

temp = C[1, 2] + C[3, 4] + 10 * 5 * 30 = 4750

• k = 3

temp = C[1, 3] + C[4, 4] + 10 * 15 * 30 = 620

 

 

[코드 구현]

#include <stdio.h>
#include <stdlib.h>

#define INF 10000000
#define N 5

void print(int C[N][N])
{
	printf("======");
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
		
			printf("%4d", C[i][j]);
		}
		printf("\\n");
	}
}

void matrinxChain(int C[N][N], int D[n])
{
    for(int L = 1 ; L < N-1 ; L++){
        for(int i = 1; i < N-L; i++)
        {
            int j = i + L; //L, i, j 세팅 
            C[i][j] = INF;

            for (int k = i; k < j ; k++)
            {
                int temp = C[i][k] + C[k+1][j] + D[i-1] * D[j];
                if(temp < C[i][j])
                {
                    C[i][j] = temp;
                }
            }
        }
        printf("\\nL == %d\\n", L);
        print(C);
    }

}

int main()
{
    int D[N] = {10, 20, 5, 15, 30};
    int C[N][N] = {0}; //0으로 초기화 

    matrixChain(C, D);

    return 0;
}

 

시간 복잡도

O(n^3)