Dynamic programming — 동적 계획법

동적 계획법(DP; 영어: dynamic programming, DP)은 원래의 문제를 더 단순한 부분 문제들의 연속으로 분할하는 방식에 기반한 복잡한 최적화 문제의 풀이 방법이다. 이 방법은 다단계 의사결정 과정에 적용되며, 전체 문제의 최적해를 각 부분 문제의 최적해로부터 구성할 수 있다.

이 용어는 1950년대 미국의 수학자 리처드 벨만에 의해 도입되었다. 이 맥락에서 '프로그래밍'이라는 단어는 컴퓨터 코드 작성이 아닌 '계획' 또는 '최적 행동 계획 수립'의 의미로 사용된다.

핵심 성질과 정리

동적 계획법의 적용 가능성은 문제가 두 가지 근본적인 성질을 갖는지에 의해 결정된다.

벨만의 최적성 원리

이 방법의 중심 개념은 벨만의 최적성 원리(영어: Bellman's principle of optimality)이다. 이는 다음과 같이 서술된다: 초기 상태와 초기 결정이 무엇이든 간에, 이후의 결정들은 첫 번째 결정의 결과로 얻어진 상태에 대하여 최적 전략을 구성해야 한다.

다시 말해, 최적 경로의 어떤 부분도 그 자체로 최적이다. 이 성질은 전체 문제를 더 단순한 부분 문제들의 연속으로 분할하고 재귀적으로 풀 수 있게 해 준다.

중복 부분 문제

문제가 재귀적으로 풀릴 때 동일한 부분 문제가 반복적으로 나타나면, 그 문제는 중복 부분 문제(영어: overlapping subproblems) 성질을 가진다고 한다. DP는 이미 풀린 부분 문제의 해를 저장함으로써(이 기법을 메모이제이션 또는 테뷸레이션이라 한다) 중복 계산을 피할 수 있으며, 이는 단순한 재귀적 완전 탐색에 비해 효율성을 크게 향상시킨다.

벨만 방정식

최적성 원리로부터 이 방법의 핵심 점화식인 벨만 방정식이 도출된다. 이 방정식은 현재 상태의 '가치'(최적 이득 또는 비용)를 이후 상태들의 가치와 연결한다. 가산적 목적 함수를 가진 결정론적 다단계 과정에 대한 일반적인 형태는 다음과 같다:

$V_{k-1}(x)=\underset{y\in U(x)}{\max }\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

여기서:

• $k$ — 단계 번호($m$에서 1까지);
• $x$ — 단계 $k-1$에서의 시스템 상태;
• $y$ — 단계 $k$에서 채택되는 제어 결정;
• ${\phi }_k(x,y)$ — k번째 단계에서의 이득(또는 비용);
• $f_k(x,y)$ — 시스템의 새로운 상태를 정의하는 함수;
• $V_k(s)$ — 단계 $k$에서 상태 $s$로 시작하는 부분 문제에 대한 목적 함수의 최적값.

이 방정식은 일반적으로 마지막 단계에서 첫 번째 단계로 거슬러 올라가는 방식, 즉 '끝에서부터' 순차적으로 풀린다.

적용 예시

• 그래프에서의 최단 경로 문제: 이 문제는 최단 경로의 어떤 구간도 그 자체로 최단이라는 최적 부분구조 성질을 가진다. 벨만-포드 알고리즘과 플로이드-워셜 알고리즘은 이 문제를 DP로 풀기 위한 고전적인 적용 사례이다.
• 배낭 문제: 서로 다른 가치와 무게를 가진 물건들로 제한된 용량의 배낭을 최적으로 채우는 문제이다. DP는 물건들을 순차적으로 고려하고 각 단계에서 남은 용량의 모든 가능한 값에 대해 최대 가치를 계산함으로써 이 문제를 풀 수 있다.
• 자원 배분 문제: 전체 효과를 최대화하기 위해 제한된 자원(예: 투자금)을 여러 프로젝트에 배분하는 문제이다.

한계

이 방법의 주요 한계는 차원의 저주(영어: curse of dimensionality)이다. 이는 시스템 상태를 기술하는 변수의 수가 증가함에 따라 상태 수가 지수적으로 증가하고 그 결과 계산 복잡도가 폭발적으로 증가하는 현상을 나타내기 위해 벨만이 도입한 용어이다. 이로 인해 매우 고차원 문제에 대한 정확한 DP의 실용적 적용이 제한된다.

관련 개념

• 운용 과학
• 최적 제어 이론
• 마르코프 결정 과정(확률론적 일반화)
• 해밀턴-야코비-벨만 방정식(연속 시간에 대한 유사체)

각주

</references>