동적 프로그래밍(비교)

r27 vs r28
... ...
10 10
> Divide & Conquer, Overlapping Subproblem
11 11
12 12
=== 최적제어에서의 동적 프로그래밍 ===
13
기본적으로 동적 프로그래밍은 최적 제어 문제를 해결하기 위해서 고안된 방법이다. 특히나 이산 시간(discrete time) 제어 문제에 적용하기 위한 방법으로 시작한다. 최적제어는 어떤 시스템의 상태 [math(x(t))]와 현재의 입력 [math(u(t))]을 기반으로 계산되는 비용 [math(J(t))]을 최소화 하는 문제상황을 말한다. 벨만은 이 문제를 해결하기 위해서 2가지의 핵심 개념을 제시하는데 첫번째는 '''최적성의 원리'''이다. 최적성의 원리란 별로 어렵지 않다. 어떤 문제에 대한 최적의 경로(=비용을 최소화 하는)가 존재할때, 그 하위 경로 역시 최적이어야 한다라는 의미이다. 때문에 동적 프로그래밍은 문제를 전체적으로 한 번에 푸는 것이 아니라, 문제를 시간적으로 나누어 각 시점마다 최적의 결정을 순차적으로 내려가는 방식으로 접근한다. 이를 수학적으로 표현한 것이 바로 두 번째 핵심 개념인 '''벨만 방정식(Bellman Equation)'''이다.
14
16
>[math(J^*(t, x) = \min_{u \in \mathcal{U}} \left[ c(x, u) + J^*(t+1, x(t+1), u(t+1))) \right])]
18
>-----
20
>벨만 방정식
13
기본적으로 동적 프로그래밍은 최적 제어 문제를 해결하기 위해서 고안된 방법이다. 특히나 이산 시간(discrete time) 제어 문제에 적용하기 위한 방법으로 시작한다. 최적제어는 어떤 시스템의 상태 [math(x(t))]와 현재의 입력 [math(u(t))]을 기반으로 계산되는 비용 [math(J(t))]을 최소화 하는 문제상황을 말한다. 벨만은 이 문제를 해결하기 위해서 핵심 개념을 제시하는데 이것이 바로 '''최적성의 원리'''이다. 최적성의 원리란 별로 어렵지 않다. 어떤 문제에 대한 최적의 경로(=비용을 최소화 하는)가 존재할때, 그 하위 경로 역시 최적이어야 한다라는 의미이다. 때문에 동적 프로그래밍은 문제를 전체적으로 한 번에 푸는 것이 아니라, 문제를 시간적으로 나누어 각 시점마다 최적의 결정을 순차적으로 내려가는 방식으로 접근한다.
18 14
=== 컴퓨터 과학에서의 동적 프로그래밍 ===
19 15
상태기반의 문제를 재귀적으로 해석하는 방법은 너무나도 일반화 하기 쉬운 강력한 방법이었다. 이 문제를 최적제어 문제에만 쓰기 아까웠던 벨만은 다른 문제에도 사용하기 시작하였고 최적 경로, 그래프 탐색 문제등을 시작으로 동적 프로그래밍의 사상 아래에서 해결될 수 있음을 보였다.
20 16
... ...