"동적 계획법"의 두 판 사이의 차이

2023년 11월 5일 (일) 11:36 판

다른 뜻에 대해서는 동적 프로그래밍 언어 문서를 참조하십시오.

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

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

@@ 4번째 줄: / 4번째 줄: @@
 ;[[動的]] [[計劃]][[法]]
 ;동적 계획법, 동적 프로그래밍
+* 대략 "재귀에 대한 최적화"
 * 의사결정 최적화를 위한 [[수리적 계획법]]
 * [[수학적 최적화]] 방법이자 [[알고리즘 패러다임]]의 하나