동적계획법 (Dynamic Programming)
쉽게 풀면
여러 도시를 거쳐 목적지까지 가는 최단 경로를 찾는다고 생각해봅시다. 전체 경로를 한 번에 고민하는 대신, 마지막 도시 바로 앞 단계부터 시작해 각 도시까지의 최적 경로를 하나씩 구해 기록해두면, 그 정보를 재사용해 전체 최적 경로를 훨씬 효율적으로 찾을 수 있습니다. 동적계획법은 바로 이렇게 문제를 단계별로 쪼개고, 한 번 구한 부분 답을 다시 계산하지 않고 저장해서 재활용하는 방식으로 전체 최적해를 구하는 방법입니다. 같은 계산을 반복하지 않기 때문에 무작정 모든 경우를 따져보는 것보다 훨씬 빠릅니다.
왜 중요한가
생산 계획, 재고 관리, 설비 교체 시점 결정 등 여러 시점에 걸친 의사결정이 서로 영향을 주고받는 문제는 산업공학에서 매우 흔합니다. 동적계획법은 이런 다단계 의사결정 문제를 체계적으로 풀 수 있는 이론적 틀을 제공하기 때문에 최적화 관련 논문에서 폭넓게 활용됩니다.
논문에서는 이렇게 쓰입니다
여러 기간에 걸친 재고 주문 결정을 단계별 부분 문제로 나누어 최적의 주문 정책을 구했다는 의미입니다.
설비를 언제 교체할지를 매 시점마다 독립적으로 정하지 않고, 전체 기간을 아우르는 최적 전략을 순차적으로 계산했다는 뜻입니다.
조금 더 깊게 보면
동적계획법은 문제가 최적 부분구조를 가진다는 전제, 즉 전체 문제의 최적해가 부분 문제들의 최적해로 구성된다는 성질을 이용합니다. 각 단계의 상태와 그 상태에서의 최적값을 저장해두는 이 과정을 흔히 메모이제이션이라 부르며, 벨만 방정식이라 불리는 재귀적 관계식을 통해 단계 간 최적값을 연결합니다.
주의할 점
동적계획법은 상태의 개수가 많아지면 저장해야 할 정보량이 급격히 늘어나는 차원의 저주 문제를 겪을 수 있어, 실제 적용 시에는 상태 공간을 적절히 축소하거나 근사하는 기법이 함께 필요합니다.