[알고리즘] 다이나믹 프로그래밍 (2)

matrix chain multiplication

fully parenthesized: 어떤 행렬들의 곱이 하나의 행렬 또는 완전히 괄호로 묶인 두개의 행렬의 곱

어떤 방법으로 행렬들을 묶는 지에 따라 곱을 계산하는 비용에 큰 차이가 있을수 있다.

두 행렬 곱하는 비용

MATRIX_MULTIPLY(A,B)
	if A.Column != B.Row 
    	error
    else let C new matrix (AxB)
    	for i =1 to A.Row
        	for j=1 to B.Column
            	cij = 0
                for k =1 to A.Column
                c ij = cij + aik *bij
     	return C
            	

A, B 가 Compatible 해야 곱할수 있다 , if 문 이용 A.Column = B.Row
C 수행시간 는 pqr 에 결정

(1 2 ) 3 = (101005 ) + (10550)
1 (2 3) = (100550) +(1010050)

matrix- chain multiplication problem : 스칼라 곱의 개수를 최소화 하도록 괄호로 묶어라

• 이때 모든 가능한 방법을 조사하는 것은 효과적이지 않음

P(n) = 1 if n =1
시그마(k=1~n-1) p(k)p(n-k) if n>= 2

이러면 너무 커짐

동적 프로그래밍의 적용
1. 최적해의 구조의 특징을 찾는다
Ai..j = AiAi+1.. Aj (i <= j) -> Ai..k , Ak+1...j (i<=k<j)

* cost of Ai..k + cost of Ak+1..j +cost of multiply 
* A i ..k , Ak+1..j 에 헤당하는 각각의 optimal 해야한다
* construct an optimal solution to a subproblems 

2. 최적해의 값을 재귀적으로 정의한다
3. 최적해의 값을 계산한다
4. 계산된 정보들로부터 최적해를 구성한다