25. [다이나믹]효율적인 행렬곱 순서

알고리즘/알고리즘(Java)

25. [다이나믹]효율적인 행렬곱 순서

산을좋아한라쯔 2015. 4. 26. 18:18

문제

여러 행렬들이 주어졌을 때, 이 행렬들을 모두 곱한 값을 구하시오.

여기서, 여러 행렬들은 행렬곱이 가능하다는 것이 보장되고, 두 행렬의 곱은 아래와 같이 정의된다.

행렬 A가 n행 m열이고[n , m], 행렬B가 m행 p열일 때[m , p], 행렬 A와 B의 곱행렬 C는 [n , p] 행렬이 되고, i행 j열일 때의 값 C_ij는 다음과 같이 계산되고, 총 (n x m x p)회 곱셈연산이 이루어진다.

행렬곱을 수행함에 있어서는, 아래와 같이 행렬곱을 하는 순서에 따라, 전체 수행횟수가 달라진다는 것을 참조해서, 최소의 행렬곱 연산이 이루어지도록 최적화해서 계산하시오.

예)A₁A₂A₃를 계산할 경우

A₁= [10 , 100] A₂=[100 , 5] A₃=[5 , 50]

Case 1. (A₁A₂)A₃ : (10 x 100 x 5) + (10 x 5 x 50) = 5000 + 2500 = 7500

Case 2. A₁(A₂A₃) : (100 x 5 x 50) + (10 x 100 x 50) = 25,000 + 50,000 = 75,000

따라서, Case 1 처럼 (A₁A₂)A₃순서로 계산

입력파일

문제로 주어지는 입력파일내 데이터형식은 다음과 같다.

테스트 갯수

행렬갯수(N)

행렬1_행수 행렬1_열수 행렬2_행수 행렬2_열수 ... 행렬N_행수 행렬N_열수

행렬1_1행의 값...

행렬1_2행의 값...

...

행렬N_1행의 값...

행렬N_2행의 값...

...

문제소스

아래 소스를 참조로해서 코딩하시오.

package dynamic;

import java.io.File;

import java.util.ArrayList;

import java.util.Scanner;

public class MatrixMultiOrder {

public static void main(String[] args) throws Exception {

Scanner sc = new Scanner(new File("res/MatrixMultiOrder.in"));

int T, N;

T = sc.nextInt();

for (int testNum = 1; testNum <= T; testNum++) {

N = sc.nextInt(); // 행렬 개수

ArrayList<int[][]> arrList = new ArrayList<int[][]>();

for(int i=0;i<N;i++){

int rowCnt = sc.nextInt();

int colCnt = sc.nextInt();

int[][] arr = new int[rowCnt][colCnt];

for(int r=0;r<rowCnt;r++){

for(int c=0;c<colCnt;c++){

arr[r][c] = sc.nextInt();

}

arrList.add(arr);

}

long t1 = System.currentTimeMillis();

int[][] result = matrixMultiplication(arrList);

long t2 = System.currentTimeMillis();

System.out.println("Test #"+testNum+"("+(t2-t1)+"ms)");

print(result);

System.out.println("");

}

sc.close();

}

private static int[][] matrixMultiplication(ArrayList<int[][]> arrList) {

return null;

}

private static void print(int[][] a){

for(int r=0;r<a.length;r++){

for(int c=0;c<a[r].length;c++){

System.out.print(a[r][c]+" ");

}

System.out.println("");

}

----------------------------------------------------------------------------------

--------------------------------------------------------------------------------

풀이

행렬곱의 특성을 알고 있어야 풀 수 있는 문제이다.

먼저 두 행렬곱을 수행하는 메서드를 작성해 보자.

두 행렬곱은 위와 같은 수식을 따르므로, 코딩하면 다음과 같이 될 것이다.

private static int[][] arrMultiply(int[][] a, int[][] b){

int n=a.length;

int m = a[0].length;

int m2 = b.length;

int p = b[0].length;

if(m != m2){

return null;

}

int[][] c = new int[n][p];

for(int i=0;i<n;i++){

for(int j=0;j<p;j++){

c[i][j]=0;

for(int k=0;k<m;k++){

c[i][j] += a[i][k] * b[k][j];

}

return c;

}

두 행렬 A1=[p,q] A2=[q,r]일 때, ==> A1의 행(row)은 p, 열(column)은 q, A2의 행은 q, 열은 r

행렬곱을 한 결과는 [p,r]행렬이 되고, 연산은 (p x q x r)회 일어난다.

그리고, 행렬곱이 가능하려면 앞 행렬의 열과, 뒷행렬의 행의 크기가 같아야 한다.

이러한 규칙을 만족하려면, 곱이 가능한 행렬들 A1 x A2 x A3 x ... x An을 다음과 같은 형태를 가지고 있어야 한다.

A0 x A1 x A1 x ... x An-1

= (p₀,p₁) (p₁,p₂) (p₂,p₃) ... (p_n-1,p_n)

즉, 각 행렬의 행과 열 수만을 생각하면, n개의 행렬에 대해서 (n+1)개의 어떤 수열 p를 생각할 수 있는 것.

예를 들어, A0=[1,3] A1=[3,10] A2=[10,5] 인 행렬이 있을 때, 행수와 열수로 이루어진 수열 p는,

p = {1,3,10,5}

이제, 최소연산횟수를 토해내는 함수 m을 생각해보자.

m(0,0)은 행렬A0와 A0간 (자기 자신)간의 곱을 의미하므로 실행횟수가 없다. 따라서, m(0,0)=0

m(0,1)은 행렬A0와 행렬A1과의 최소연산횟수이기에, 수열p의 원소로 실행횟수를 표현하면 m(0,1)=p0 x p1 x p2

마찬가지로 생각하면, m(1,2)=(p1 x p2 x p3)

m(0,2)처럼, 세 개 혹은 더 많은 수의 배열에 대해서 m값은 어떻게 표현될 수 있을까?

m(0,2)는 아래 두 개의 값중 작은 쪽이다.

m0 = m(0,0) + m(1,2) + (p0 x p1 x p3)

m1 = m(0,1) + m(2,2) + (p0 x p2 x p3)

즉, A0(A1A2)로 계산하는가, (A0A1)A2로 계산하는게 효율적인가를 나타내는것과 동일

m(0,3)은 아래 3개의 값중 작은 쪽.

m0= m(0,0) + m(1,3) + (p0 x p1 x p4)

==> A0(A1A2A3)의 경우로, 뒷 부분 (A1A2A3)는 [p1,p4]의 행렬이므로, [p0,p1] x [p1,p4]여서, p0 x p1 x p4가 됨

m1 = m(0,1) + m(2,3) + (p0 x p2 x p4)

m2 = m(0,2) + m(3,3) + (p0 x p3 x p4)

이제 m함수에 대해서 일반화해보면 다음과 같이 될 것이다.

m[i,j] = 0 , if i==j

min( m(i,k) + m(k+1,j) + (p_i x p_k+1 x p_j+1) ) where i<=k<j, if j>i

점화식이 완성되었다.

* 점화식의 유도는 아래 그림을 보면 좀 더 이해하기기 쉽겠다. 즉, k가 오른쪽으로 이동해가며, 최소가 되는 k값을 찾는.

위와 같은 원리로, 최적의 k값을 찾는 메서드를 작성하면 다음과 같이 된다. (재귀호출을 이용하는 것으로, 실제 사용은 memoization을 이용하는 메서드를 새로 만들어서 사용해야 한다. 그 메서드 이름은 optimize(). 맨 아랫부분 전체 소스 참조)

private static int optimize_recursive(int i, int j, int[] p, int[][] trace) {

if(i==j) return 0;

int tmp=0;

int min=Integer.MAX_VALUE;

int minK=0;

for(int k=i;k<j;k++){

tmp = optimize_recursive(i,k,p,trace) + optimize_recursive(k+1,j,p,trace)

+ p[i]*p[k+1]*p[j+1];

if(tmp < min) {

min = tmp;

minK=k;

}

trace[i][j] = minK;

return min;

}

위의 A0=[1,3] A1=[3,10] A2=[10,5] 인 행렬에 대해서 계산해보면, 최소연산값 및 최적 k값에 대해 다음과 계산에 의해 테이블이 만들어 진다.

p = {1,3,10,5}

m(0,2) = min(m(0,0) + m(1,2) + (1 x 3 x 5) , m(0,1) + m(2,2) + (1 x 10 x 5))

= min( (3 x 10 x 5) + 15, 50)

= min(165, 50)

= 50 --> k=1

m(1,2) = m(1,1) + m(2,2) + (3 x 10 x 5) = 0 + 0 + 150 = 150 --> k=1

m(0,1) = m(0,0) + m(1,1) + (1 x 3 x 10) = 0 + 0 + 30 = 30 --> k=0

k에 대한 테이블을 해석할 수 있어야 곱셈에 대한 순서를 결정할 수 있다.

(항상, 다이나믹 알고리즘에서 어려운 부분이 트레이싱하는 테이블을 해석하는 부분이다.)

k테이블을 보면 (i,j)가 (0,2)일 때의 값이 1이다.

이 의미를 곰곰이 생각해보자.

0과 2사이, 즉, A₀~A₂까지의 행렬곱에서, 최적의 k위치가 1이라는 것이다. -> (A₀A₁)(A₂) 라는 얘기

4개의 행렬 A0A1A2A3을 곱하는 경우, k에 대한 테이블이 다음과 같다면 어떻게 될까?

답은 A₀(A₁A₂)A₃ 이다.

(0,3)일 때의 k값이 0이므로, A₀(A₁A₂A₃) 이고,

(1,3)에 대해서 2이므로, A₁A₂A₃에 대해서는 (A₁A₂)A₃이기에,

종합해보면 A₀(A₁A₂)A₃ 가 된다.

위와같은 원리로, k값을 이용해서, 어떤 순서로 행렬곱을 수행해야할 지 결정할 수 있다.

먼저, 문제에서 요구하는 행렬곱을 직접 수행하기 전에, 주어진 행렬들에 대해서 효율적으로 나눈 모습을 프린트하는 메서드를 먼저 구현해보자. 아래와 같은 모습이 될 것이다.

private static void printMultiChain(int i, int j, int[][] trace){

if(i==j){

print("A"+i);

}else{

print("(");

printMultiChain(i,trace[i][j],trace);

printMultiChain(trace[i][j]+1,j,trace);

print(")");

}

k테이블을 이용해서 실제 행렬곱을 수행하는 코드는 다음과 같다.

private static int[][] multiply(int i,int j, int[][] t, ArrayList<int[][]> arrList){

if(i==j){

return arrList.get(i);

}

return arrMultiply(multiply(i,t[i][j],t,arrList),multiply(t[i][j]+1,j,t,arrList));

}

전체 소스

package dynamic;

import java.io.File;

import java.util.ArrayList;

import java.util.Scanner;

public class MatrixMultiOrder {

public static void main(String[] args) throws Exception {

Scanner sc = new Scanner(new File("res/MatrixMultiOrder.in"));

int T, N;

T = sc.nextInt();

for (int testNum = 1; testNum <= T; testNum++) {

N = sc.nextInt(); // 행렬 개수

ArrayList<int[][]> arrList = new ArrayList<int[][]>();

for (int i = 0; i < N; i++) {

int rowCnt = sc.nextInt();

int colCnt = sc.nextInt();

int[][] arr = new int[rowCnt][colCnt];

for (int r = 0; r < rowCnt; r++) {

for (int c = 0; c < colCnt; c++) {

arr[r][c] = sc.nextInt();

}

arrList.add(arr);

}

long t1 = System.currentTimeMillis();

int[][] result = matrixMultiplication(arrList);

long t2 = System.currentTimeMillis();

System.out.println("");

System.out.println("Test #" + testNum + "(" + (t2 - t1) + "ms)");

print(result);

System.out.println("");

}

sc.close();

}

private static int[][] matrixMultiplication(ArrayList<int[][]> arrList) {

int n = arrList.size();

int[] p = new int[n + 1]; // 0~n

int[][] trace = new int[n][n];

int[][] a = null;

for (int i = 0; i < n; i++) {

a = arrList.get(i);

p[i] = a.length;

}

p[n] = a[0].length;

int[][] table = new int[n][n];

optimize(0, n - 1, p, trace,table);

int[][] result = doOptimizeMultiplication(arrList, trace);

return result;

}

private static int optimize_recursive(int i, int j, int[] p, int[][] trace) {

if(i==j) return 0;

int tmp=0;

int min=Integer.MAX_VALUE;

int minK=0;

for(int k=i;k<j;k++){

tmp = optimize_recursive(i,k,p,trace) + optimize_recursive(k+1,j,p,trace) + p[i]*p[k+1]*p[j+1];

if(tmp < min) {

min = tmp;

minK=k;

}

trace[i][j] = minK;

return min;

}

private static int optimize(int i, int j, int[] p, int[][] trace, int[][] table) {

if(i==j) return 0;

int tmp=0;

int min=Integer.MAX_VALUE;

int minK=0;

for(int k=i;k<j;k++){

if(table[i][k]==0){

table[i][k] = optimize(i,k,p,trace,table);

}

if(table[k+1][j]==0){

table[k+1][j] = optimize(k+1,j,p,trace,table);

}

tmp = table[i][k] + table[k+1][j] + p[i]*p[k+1]*p[j+1];

if(tmp < min) {

min = tmp;

minK=k;

}

trace[i][j] = minK;

return min;

}

private static int[][] doOptimizeMultiplication(ArrayList<int[][]> arrList, int[][] trace) {

int n = arrList.size();

printMultiChain(0,n-1,trace);

int[][] result = multiply(0,n-1,trace,arrList);

return result;

}

private static void printMultiChain(int i, int j, int[][] trace){

if(i==j){

print("A"+i);

}else{

print("(");

printMultiChain(i,trace[i][j],trace);

printMultiChain(trace[i][j]+1,j,trace);

print(")");

}

private static int[][] multiply(int i,int j, int[][] t, ArrayList<int[][]> arrList){

if(i==j){

return arrList.get(i);

}

return arrMultiply(multiply(i,t[i][j],t,arrList),multiply(t[i][j]+1,j,t,arrList));

}

private static int[][] arrMultiply(int[][] a, int[][] b){

int n=a.length;

int m = a[0].length;

int m2 = b.length;

int p = b[0].length;

if(m != m2){

return null;

}

int[][] c = new int[n][p];

for(int i=0;i<n;i++){

for(int j=0;j<p;j++){

c[i][j]=0;

for(int k=0;k<m;k++){

c[i][j] += a[i][k] * b[k][j];

}

return c;

}

private static void print(String str){

System.out.print(str);

}

private static void print(int[][] a) {

if(a==null) return;

for (int r = 0; r < a.length; r++) {

for (int c = 0; c < a[r].length; c++) {

System.out.print(a[r][c] + " ");

}

System.out.println("");

}

입력파일 (MatrixMultiOrder.in)

1 3

1 2 3

3 1

1 5

1 2 3 4 5

5 10

1 2 3 4 5 6 7 8 9 10

2 2 3 4 5 6 7 8 9 10

3 2 3 4 5 6 7 8 9 10

4 2 3 4 5 6 7 8 9 10

5 2 3 4 5 6 7 8 9 10

10 10

1 2 3 4 5 6 7 8 9 10

10 5

5 5 5 5 5

5 100

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10

100 100

100 5

5 5 5 5 5

5 100

-끝-

저작자표시 비영리 변경금지

'알고리즘 > 알고리즘(Java)' 카테고리의 다른 글

[분할정복]MergeSort_BottomUp (0)	2015.10.26
[분할정복]분할정복 개요-MergeSort (0)	2015.10.26
24.[다이나믹]조립라인 스케줄링(Assembly Line Scheduling) (0)	2015.04.25
23. [다이나믹]옷 (0)	2015.04.24
22. [다이나믹]배낭 문제 (Knapsack problem) (0)	2015.04.21

현재글25. [다이나믹]효율적인 행렬곱 순서

wavelength, Fourier, FFT, 비트코인 논문 번역, 보호 해제, 파장, CIE, excel crack, 비트코인 번역본, 엑셀 크렉, DFT, excel vba, 사토시 논문, Block Chain, 비트코인 번역, bitcoin 번역, 블록체인 번역, RGB, 시트보호, protection remove,

Today :
Yesterday :

컴퓨터 프로그래밍(암호학, 알고리즘)