Dynamic Programming

Dynamic Programming Version of a Recursive Algorithm

- 시간 절약을 위해 메모리를 더 사용. sub-problem을 저장함으로써 중복된 계산을 피함.

- 재귀 호출하기 전에, subproblem Q에 대한 solution이 dictionary soln에 이미 있는지 확인한다. 없으면 재귀 호출하고, 결과를 저장한다.

- ex) 피보나치

 

Matrix-Chain Multiplication problem

- matrix chain ( <A1, A2, ..., An> )의 곱셈 연산의 수가 최소가 되는 순서 구하기(행렬곱은 순서에 따라 연산의 수가 달라지니까) -> 최적화 문제!

- Computation Time

- p x q 와 q x r 두 행렬을 곱한다면

- pqr scalar multiplications: pr elements에 대해 각각 q 스칼라 곱

- 따라서, 곱셈 순서에 따라 연산 수가 달라진다.

 

 

Development

1. Characterize the structure of an optimal solution: 구조(특성) 파악

2. Recursively define the value of an optimal solution: 점화식 정의

3. Compute the value of an optimal solution in a bottom-up(top-down) fashion: 점화식대로 값 계산

(4는 옵션) Construct an optimal soluion from computed informationn: 과정(solution) 찾기

 

Step 1: 구조(특성) 파악

- AiAI+1...AJ 를 Ai...Ak 와 Ak+1...Aj 로 나눈다. (i<=k<j)

- cost = (cost of computing Ai...k) + (cost of computing Ak+1...j) + (cost of multiplying them)

- Ai...Ak 와 Ak+1...Aj 는 k에 대해 optimal이어야 한다.

- 나눌 place를 결정하기 위해, 가능한 모든 place들을 고려해야 한다.

Step 2: 점화식 정의

- m[i,j]: Ai..j 계산에 필요한 최소 곱셈 연산 수

- i=j 라면 0

- i<j 라면 min{m[i,k] + m[k+1,j] + pi-1pkpj}

- s[i,j]: 행렬곱을 최적으로 분리하는 k값

Step 3: 계산

- input: p=<p0,...,pn> (실제 matrix대신 차원으로 인풋 정의)

- 행렬의 개수 n은 ‘p길이 - 1’

- 시간 분석: 각 cell 계산하는 데 최악의 경우 O(n) 걸리고, cell이 O(n2)개 존재하므로 총 O(n3) time.

- 공간 분석: O(n2)  (m테이블과 s테이블)

Step4: (optional) S테이블을 이용해 solution 계산