동적 계획법

1 개요[ | ]

하위문제들이 서로 독립적이지 않은 경우가 있다(분할정복과 다른 점).

여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달한다.
복잡한 문제를 재귀적인 방식으로 더 간단한 하위 문제로 분해하여 단순화하는 것이다.
부분 문제 반복과 최적 기본 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
1950년대, Richard Bellman이 개발하였다.
항공우주공학에서 경제학에 이르기까지 다양한 분야에서 응용되었다.
여러 시점에 걸친 의사결정은 재귀적으로 분리할 수 있는 경우가 있다. (모든 의사결정 문제를 이런 방식으로 분리할 수 있는 것은 아니다)
컴퓨터 과학에서는 문제를 하위 문제로 나눈 다음 하위 문제에 대한 최적의 솔루션을 재귀적으로 찾아 최적으로 해결할 수 있는 경우 해당 문제를 최적 하위 구조라고 한다.
하위문제가 더 큰 문제 내에 재귀적으로 중첩되어 동적 계획법을 적용할 수 있는 경우, 더 큰 문제의 값과 하위 문제의 값 사이에는 관계가 있다. 이 관계를 최적화 문헌에서는 벨만 방정식이라고 한다.