유래
2차 세계 대전 → 군사 작전 연구 OR (Operation Research) 학문
OR 의 연구중 하나가 다단계 의사 결정 문제 (Multistage decision problem)
Richard Bellman이 다단계 의사 결정 문제를 연구하기 시작
연구 부서의 이름을 Planning → Programming 으로 결정,
연구의 이름을 단계적 의사 결정이 동적 (Dynamic)으로 불리우기를 원했음
즉 다단계 의사 결정은 동적으로 변화하는 결정을 만드는 방법을 연구하는 것.
동적 계획법
여러 문제가 여러 단계의 반복되는 부분 문제로 이루어질 때, 각 단계에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법을 말한다.
•
동적 계획법과 분할 정복은 다르다. 분할 정복은 문제를 위에서 아래로 (Top-Down) 쪼개지만, 동적 계획법은 제일 작은 부분 문제부터 상위에 있는 문제로 풀어 올라간다. (Bottom Up)
•
분할 정복 기법으로 쪼갠 각 부분 문제는 완전히 새로운 하나의 문제로 다룰 수 있지만, 동적 계획법에서 문제의 각 단계에 있는 부분 문제들은 그 이전 단계에 있는 문제들의 답에 의존한다.
•
동적 계획법은 분할정복과 달리 한번 푼 적이 있는 부분 문제의 답은 다시 푸는 일이 없도록 테이블 등에 저장해 둔다.
알고리즘
1.
문제를 부분 문제로 나눈다.
2.
가장 작은 부분 문제부터 해를 구한 뒤에 테이블에 저장한다.
3.
테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차 상위 부분 문제에 최적해를 구한다.
최적 부분 구조
독적 계획법을 이용하여 문제를 풀기 위해서는 그 문제가 ‘최적 부분 구조(Optimal Substructure)’를 갖추고 있다는 전제가 필요하다.
최적 부분 구조 : 전체 문제의 최적해가 부분 문제의 최적해로부터 만들어지는 구조.
