sakuragi's miscellaneous space

 사실 이 과제는 그냥 수업시간에 보고 넘어갔던 알고리즘이라, 프로그램을 짤 생각은 없었는데, 오늘 수업을 들어갔는데... 교수님께서 '어! 최소곱셈 알고리즘을 몇명 제출했더라~' 라는 말에 결국에는 짜게 되었다.

 연쇄행렬곱셈의 요지는 행렬 곱셈에는 결합 법칙이 성립함으로 행렬 A, B, C, D가 있다고 할 때, A × (B × C) × D 이런식으로 곱해도 결과값에는 영향을 주지 않는 다는 말이다. 하지만 A × B × C × D 로 계산 해서 풀었을 때와 A × ((B × C) × D) 이렇게 풀었을 때 중간에 곱셈을 하는 횟수가 달라진다.

 예를 들어 다음과 같은 행렬이 있다고 할 때

        A   ×   B    ×   C    ×   D
    20×2     2×30    30×12   12×8

결합법칙에 의해서 나올 수 있는 경우를 살펴보면 다음과 같아진다.

A(B(CD))   30 × 12 × 8 +  2  × 30 × 8 + 20 ×  2 × 8   = 3,680
(AB)(CD)   20 ×  2 ×30 + 30 × 12 × 8 + 20 × 30 × 8   = 8,880
A((BC)D)    2 × 30 × 12 +  2 × 12 × 8 + 20 × 2 × 8    = 1,232
((AB)C)D   20 × 2 × 30 + 20 × 30 × 12  + 20 × 12 × 8 = 10,320
(A(BC)D     2 × 30 × 12 + 20 × 2 × 12 + 20 × 12 × 8   = 3,120

보는 바와 같이 A((BC)D)의 순서로 곱셈을 하게 될 경우 곱셈의 횟수를 줄일 수 있다. 이 알고리즘은 어떤 순서로 곱하면 최적의 순서가 되는지 그렇게 해서 나온 최소 곱셉은 몇번을 하게 되는지 출력해 준다.

#include <stdio.h>
#include <malloc.h>

int minmult(int n, int d[], int *P[]);  // 최소 곱셈 알고리즘
void order(int i, int j, int *P[]);     // 최적 순서 출력
int* input_array_number(int n);     // dx를 입력 받음
int** make_array(int n);    // P 행렬 동적 할당

int main()
{
    int *d, **P;
    int number, result;

    printf("Minimum Multiplication\nhow many numbers of array? ");
    scanf("%d", &number);  // 형렬의 갯수 입력 받음

    d = input_array_number(number); // 알고리즘의 입력이 되는 d 행렬
    P = make_array(number);     // 최적 순서 출력을 위한 P 행렬 만듬

    result = minmult(number, d, P); // 알고리즘의 결과값을 result에 저장
    printf("\nArray Multiplication Order is ");
    order(1, number, P);   // 행렬 곱셈 최적 순서 출력
    printf("\nMinimum Multiplication is %d\n", result);

    return 0;
}

int** make_array(int n) // P 행렬을 동적 메모리 할당으로 만듬
{
    int i;
    int **P = (int**)malloc(0);
    for (i = 0; i < n; i++)
        P[i] = (int*)malloc(sizeof(int)*n);
    return P;
}

int* input_array_number(int n)  // 입력 받은 number 만큼 dx를 입력 받음
{
    int i, *d;
    printf("Plz Input d0 ~ d%d\n", n);
    d = (int*)malloc(sizeof(int)*n);
    for(i = 0; i <= n; i++) {
        printf("d%d=? ", i);
        scanf("%d", &d[i]);
    }
    return d;
}

void order(int i, int j, int *P[])  // 최적의 순서 출력
{
    int k;
    if(i == j)
        printf("A%d", i);
    else {
        k = P[i][j];
        printf("(");
        order(i,k,P);
        order(k+1, j,P);
        printf(")");
    }
}

int minmult(int n, int d[], int *P[])   // 최소 곱셉 알고리즘
{
    int i, j, k, diagnonal, min_k = 0;
    int **M, temp = 0;
    M = make_array(n+1);
    for(i = 1; i <= n; i++)
        M[i][i] = 0;
    for(diagnonal = 1; diagnonal <= n-1; diagnonal++)  // diagonal값이 1이면
        for(i = 1; i <= n - diagnonal;i++) {          // 주대각선의 바로 위에
            j = i + diagnonal;                          // 있는 대각선을 의미한다.
            /* for(k~~~)는 아래에 해당한다.
             * M[i][j] = minimum(M[i][k] + M[k+1][j] + d[i-1] * d[k] * d[j]);
             *           i<= k <= j-1                   */
            for(k = i; k <= j-1; k++) {
                M[i][j] = M[i][k] + M[k+1][j] + d[i-1] * d[k] * d[j];
                if(i == k) {
                    temp = M[i][j];
                    min_k = k;
                } else if(M[i][j] > temp) {
                    M[i][j] = temp;
                } else
                    min_k = k;
            }
            P[i][j] = min_k;    // 최소값을 주는 k의 값
        }
    return M[1][n];    // 최소 곱셈 값 리턴
}

결과는 다음과 같다.

 전의 플로이드 알고리즘이나 이 연쇄행렬곱셈 알고리즘은 동적계획법에 의한(?) 알고리즘인데 동적계획법의 요점은 행렬을 이용해서 이미 한번 계산된 결과를 나중에 필요할 때 계산하지 않고 행렬에서 가져다가 쓴다는 점이다.

참고자료
• 알고리즘(Foundatations of Algorithms Using C++ Pseudocode) - Neapolitan, Naimipour 저 / 도경구 역