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

Chained Matrix Multiplication (연쇄 행렬 곱셈)

:  행렬 i x j와 행렬 j x k 처럼 열의 갯수와 행의 갯수가 같은 연속적인 행렬의 곱셈

- 행렬의 곱은 결합법칙이 적용하기 때문에 곱하는 순서는 상관없지만 곱하는 횟수가 달라지기 때문에 최적의 순서를 구해야한다.

 

e.g.
A1 x A2  x  A3. 
A1은 10  x  100, A2는 100  x  5, A3은 5  x  50.
(A1  x  A2)  x  A3
10  x  100  x  5 + 10  x  5  x  50 = 7,500
A1  x  (A2  x  A3)
100  x  5  x  50 + 10  x  100  x  50 = 75,000 //100을 2번 계산하기 때문에 연산 횟수가 증가함

Brute force algorithm

: 전부 해보기

이런 방법에 대한 시간복잡도를 알아야할까

아무튼  Θ(2^n)인걸루.

 

 

 

 Dynamic Programming Design

A1부터 An까지 연속된 행렬의 곱을 계산한다면

각 행과 열의 값을 살펴봤을 때 A1의 행의 값을 d0, A1의 열의 값을 d1이라고 한다면 행렬 A는 곱이 가능한 연속된 행렬이기 때문에 A2의 값이 d1과 동일하다. 

그렇기 때문에 행렬들의 곱은 d0 x d1 x ... x dn이라고 할 수 있다.

만약 1 <= i <= j <= n인 i와 j가 있다면 M[i][j]의 최소값은

M[i][k] + M[k+1][j] + d[i-1]d[k]d[j]의 최소값으로 계산할 수 있다.

(A(B(CD)), ((AB)(CD)), A((BC)D) 처럼 곱 계산의 위치를 변수 k로 설정하여 최소값을 찾을 수 있다.

M[i][k]는 Ai에서 Ak까지 행렬 곱 연산 횟수,

M[k-1][j]는 Ak-1엣 Aj까지 행렬 곱 연산 횟수,

d[i-1]*d[k]*d[j]는 dp[i][k]와 dp[k+1][j]의 행렬 곱 연산 횟수이다.

Example

M[4][6]을 계산할 때 ((A4xA5)xA6)과 (A4x(A5xA6)) 중에 더 작은 값을 찾는 경우에 둘 다 계산하여 더 작은 값을 사용한다.

 

 

아무튼 diagonal을 n-1번 계산해서 값을 찾아낸다.?

 각 단계에서의 계산은 n-diag개가 필요하다.

ex. diag1의 경우는 6-1(n-diag)개가 필요하다.

∴ 전체적으로 1<=diag<= n-1 번 연산하고 각 diag는 n-diag번 계산한다.

//저 선들이 뭘 의미하는지 아시는 분 계시면 알려주세요ㅠ

 

Minimum Multiplication

- Problem : n개의 행렬을 곱하는데 필요한 최소 곱셈 수와 그 최소 수를 산출하는 순서를 결정한다.

- Input : 행렬의 크기 n, 0부터 n까지 정렬된 배열 dk < di-1 x di는 i번째 행렬이다.

- output : n개의 행렬 곱을 위해 필요한 최소 곱셈 수, 최적의 차수를 얻을 수 있는 2차원 배열 P, < P[i][j]는 최적의 순서로 행렬을 나누는 point

//Minimum Multiplication Algorithm

int minmuit(int n, const int d[], index P[][]) {
	index i, j, k, diagonal;
    int M[1..n, l..n]; //n의 크기로 배열 M 생성
    for(i = 1; i <= n; i++)
    	M[i][j] = 0; //자기 자신으로부터의 거리는 0
    for(diagonal = 1; diagonal <= n-1; diagonal++) //diagonal 배열 만들기?
    	for(i = 1; i <= n-diagonal; i++) {
        	j = i + diagonal; //현재로서 가장 큰 값
            M[i][j] = minimum(M[i][k] + M[k+1][j]+d[i-1]*d[k]*d[j]);
            //i <= k <= j - 1
            P[i][j] = 최소값을 제공하는 k의 값;
        }
    return M[1][n]; //최종적으로 계산된 결과 값
}

그럼 뭐 이런식으로 된다고 생각하면 된다는거죠?

 

 

 

 

 

 

 

Every Case Time Complexity : Minimum Multiplication

- Basic operation : n의 값에 의해 실행되는 명령어? 최소 값을 위한 비교 테스트..- Input size : 곱할 행렬의 수 n- Analysis

아마 전체적으로 1<=diag<= n-1 번 연산하고

각 diag는 n-diag번 계산하기 때문에 전체적으로 반복하는거 아닐까?

몰라요 교수님이 안알려줌