연쇄행렬곱셈 알고리즘... Minimum Multiplication

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

 연쇄행렬곱셈의 요지행렬 곱셈에는 결합 법칙이 성립함으로 행렬 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 저 / 도경구 역

by sakuragi | 2007/04/19 03:52 | :: R space :: 과제 | 트랙백 | 덧글(16)

트랙백 주소 : http://sakuragis.egloos.com/tb/3322692
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Commented by 환상경 at 2007/04/19 21:01
햐 알고리즘 멋진데요 -0-
Commented by sakuragi at 2007/04/20 02:54
환상경, 시험기간이라 이번주는 알고리즘 과제로부터는 해방이네요. 하지만 시험 얘기를 들어보니, 무지하게 빡시게 내신듯.. T_T
Commented by nidev at 2007/04/29 16:51
알고리즘 멋있네요!
Commented by sakuragi at 2007/04/30 15:12
nidev, 네.. 요즘 가장 절 힘들게(?) 하고있는 알고리즘이죠..
Commented by popo at 2007/11/19 21:51
메인함수 안에 M[n+1][n+1] 이부분에서 오류 나네요;

상수식이 필요하다고 나오는데 어떻게 고치나요?
Commented by sakuragi at 2007/11/20 01:11
popo, Visual C++ 에서 돌아가도록 수정했습니다.
M 에 관련해서 메모리를 동적으로 할당했었야 했는데 이 부분 때문에 Visual C++에서는 에러가 났네요.
리눅스에서 gcc로 컴파일하고 실행했을 때는 에러가 없어 미처 생각 못했던 부분이였네요.
Commented by popo at 2007/11/20 01:34
감사합니다^^
그런데 실행해보고 위의 값대로 입력 해봤는데 디버그 에러가 뜨는군요..
vc++로 실행했구요. DAMAGE: after Normal block(#45) at 0x00430030. 이라고 뜨는데
이건또 뭔가요?
Commented by sakuragi at 2007/11/20 01:41
popo, main() 함수에 free(P); 라인도 삭제 되었습니다. 지우고 다시 해보세요. :)
Commented by popo at 2007/11/20 01:44
잘되는군요^^ malloc함수 사용해서 동적 할당을 해줬는데 free 함수로 메모리 할당 해제를 해줘야 맞는게 아닌가요?
Commented by sakuragi at 2007/11/20 02:42
popo, 저도 그렇게 생각하는데 에러가 나니 어쩔 수 없죠. 뺄 수 밖에... :D
제가 전문가는 아니지만 프로그램이 종료되면 메모리는 모두 반환된다고 알고 있습니다. 뭔가 뒷가 구린 느낌이지만, 이렇게 짧은 프로그램에서 free가 없어도 별 문제는 없어 보입니다. :)
Commented by maz at 2011/12/15 14:52
연쇄행렬곱셈 다시 보려고 찾다가 글남기네요~

4년이 지난글이지만 댓글에 대한 답을 드리자면

다차원배열은 각각 의 행을 돌면서 메모리 해제를 모두 해주여야 하기때문에 free(P);로는 정상적으로 해제가 안되셨을 겁니다~
Commented by sakuragi at 2011/12/16 01:34
그렇군요. 각각의 행을 돌면서 메모리 해제를 해야 하는 것이였군요.
저도 어느덧 졸업하고, 자바가 주력 개발 언어라서 C를 안 본지 너무 오래 되었네요. :D
Commented by 몽키해드 at 2012/10/22 13:41
int* input_array_number(int n) // 입력 받은 number 만큼 dx를 입력 받음
{
int i, *d;
printf("Plz Input d0 ~ d%dn", n);
d = (int*)malloc(sizeof(int)*n);
for(i = 0; i <= n; i++) {
printf("d%d=? ", i);
scanf("%d", &d[i]);
}
return d;
}

이 부분에서

d = (int*)malloc(sizeof(int)*n+1);

로 바꿔야지 문제가 해결됩니다. 생성은 n개까지만 하고 n+1까지 영역을 할당하니 문제가 생기더군요.
Commented by sakuragi at 2012/10/30 23:51
테스트 해보고 수정할께요~ 감사합니다~ ( __)
Commented by dkdk at 2014/10/28 23:12
결과값이 제대로 나오지 않어요
Commented by 감사합니다 at 2017/10/30 10:49
감사합니다. 덕분에 알고리즘 문제 해결했습니다.

:         :

:

비공개 덧글

◀ 이전 페이지          다음 페이지 ▶

:+: sakuragi's Steam :+: