Parallel computing (Dynamic Programming) - 1
Dynamic Programming : Discrete optimization(이산 최적화) 문제들을 풀기 위해 일반적으로 사용됨.
>> Discrete optimization : 문제의 해가 연속적이지 않다. 즉, 이산적이다.
ex) 해 = [1, 2, 3, 4] << 이산적, 해 = [1, 2, 3 ...... , infinite] << 연속적.
* It solves subproblems and uses the results to solve larger subproblems until the entire problem is solved.
- 큰 문제의 작은 문제(subproblem)을 풀어서 그것들을 가지고 더 큰 문제를 풀어나감. (이전 값들을 저장 및 재사용)
* If the optimal soltuion to each problem is determined by composing optimal solutions to the subproblems and selecting the minimum (or maximum), the formulation is said to be a DP formulation.
- 큰 문제의 최적 해(optimal solution)가 작은 문제(subproblem)의 최적 해들의 값으로 결정 된다면, 해당 문제는 DP 식 으로 표현될 수 있다.
* If subproblems at all levels depend only on the results at the immediately preceding levels, the formulation is called a serial DP formulation; otherwise, it is called a nonserial DP formulation.
- next level 의 최적 해를 구하기 위해서 바로 이전 level 의 최적 해 값이 사용되면 serial 아닌 경우, non-serial.
* A functional equation that contains a single recursive term yields a monadic DP formulation. For an arbitrary DP formulation, the cost function may contain multiple recursive terms. DP formulations whose cost fucntion contains multiple recursive terms are called polyadic formulations.
- 함수 식에서 하나의 재귀만 사용된다면 monadic DP이고, 여러 개의 재귀가 사용된다면 polyadic DP이다.
예) f(x) = min {f(j) + c(j, x)} 1<= x <= n - 1
※ DP 4가지 class로 분류 가능
1. serial monadic : 다음 단계의 최적 해를 구하기 위해 바로 이전 최적 해 값 사용 + DP 식(functional equation)에 재귀 호출의 함수가 단수(한개) 인 경우.
2. serial polyadic : 다음 단계의 최적 해를 구하기 위해 바로 이전 최적 해 값 사용 + DP 식에 재귀 호출의 함수가 복수(여러개) 인 경우.
3. nonserial monadic : 다음 단계의 최적 해를 구하기 위해 바로 이전 최적 해 값 사용x + DP 식에 재귀 호출의 함수가 단수(한번) 인 경우.
4. nonserial polyadic : 다음 단계의 최적 해를 구하기 위해 바로 이전 최적 해 값 사용x + DP 식에 재귀 호출의 함수가 복수(여러개) 인 경우.
PS. 이 외에도 다른 카테고리가 있을 수 있을 수 있다.
위의 4가지 class의 parallel algorithm을 고안하기 위한 샘플들을 예제로 소개한다.