Chained matrix multiplication

1. Problem

- n개의 2차원 행렬이 주어졌을 때, 곱셈 연산을 최소화하는 방법을 찾아보자,

// 두 행렬의 곱셈 A*B을 수행할 때, A의 열의 개수와 B의 행의 개수가 같아야하기 때문에 교환 법칙은 성립하지 않지만, 결합 법칙은 성립한다.

// 예를 들어, 2*3 행렬과 3*4 행렬을 곱해서 2*4 행렬을 얻을 때, 총 8개의 항이 나오고, 각 항마다 필요한 곱셈 연산의 수는 3개이므로 2 * 4 * 3 = 24번의 곱셈 연산이 필요하다.

 

2. Input

1) 곱해야 하는 행렬의 개수 n

- 여기서는 예시로 주어진 6개의 행렬을 곱하고자 한다.

2) 행렬의 크기를 담은 int배열 d (0-indexed)

- i번째 행렬의 크기 == d[i-1] * d[i]

 

3. Output

1) 최소 곱셈 연산의 수

 

4. PseudoCode

int minmult(int n, const int d[], index P[][]){
    index i, j, k, diagonal;
    int M[1...n][1...n];
    
    for(i=1 ; i<=n ; i++)
        M[i][i] = 0;
    for(diagonal=1 ; diagonal<=n-1 ; 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(minimum);
        }
    return M[1][n];
}

- 설명: A1 * A2 * ... * A6을 계산하려고 한다.

1) 다음과 같은 5가지로 나눠서 계산을 한다.

  - A1*(A2A3A4A5A6)

  - (A1A2)*(A3A4A5A6)

  - (A1A2A3)*(A4A5A6)

  - (A1A2A3A4)*(A5A6)

  - (A1A2A3A4A5)*A6

  - ( ) 안에서 결합법칙을 이용해 곱셈 순서를 바꿀 수 있다.

2) M[i][j]:( A1부터 Ai까지의 곱) * (Ai+1부터 A6까지의 곱)의 곱셈 연산 횟수 중 가장 작은 것

  - 이를 수식으로 쓰면 1 <= i < 6에 대해 minimum(M[1][i] + M[i+1][6] + d0*di*d6)이 된다.

  - M[i][i] = 0

  - 6개인 경우 M이 아래와 같이 채워진다. 문제에서 찾을 값은 M[1][6]이지만, 이해를 돕고자 예시로 M[1][4]를 찾는 방법을 써봤다.

3) P[i][j]: M[i][j]를 최소로 만들어 준 k값이 저장되어 있다.

 

5. Example

public class TestClass {
    static int[][] P;
    
    public static void main(String[] args) {
        int n = 6;
        int[] d = {5,2,3,4,6,7,8};
        P = new int[n+1][n+1];
        int min = minmult(n, d, P);
        System.out.println("최소 곱셈 연산 수 = " + min); // 최소 곱셈 연산 수 = 348
        order(1, 6); // (A1((((A2A3)A4)A5)A6))
    }
	
    static int minmult(int n, int[] d, int[][] P) {
        int[][] M = new int[n+1][n+1];
        for(int diagonal=1 ; diagonal<n ; diagonal++)
            for(int i=1 ; i<=n-diagonal ; i++) {
                int j = i + diagonal;
                int min = Integer.MAX_VALUE;
                for(int k=i ; k<j ; k++){
                    int mul = M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j];
                    if(mul<min) {
                        min = mul;
                        P[i][j] = k;
                        M[i][j] = min;
                    }
                }
            }
        return M[1][n];
    }
	
    static void order(int i, int j) {
        if(i==j)
            System.out.print("A"+i);
        else {
            int k = P[i][j];
            System.out.print("(");
            order(i,k);
            order(k+1,j);
            System.out.print(")");
        }
    }
}