동적프로그래밍 예제

하위 문제가 겹치는 것은 하위 문제의 공간이 작아야 한다는 것을 의미하며, 즉 문제를 해결하는 재귀 알고리즘은 새로운 하위 문제를 생성하는 대신 동일한 하위 문제를 반복해서 해결해야 합니다. 예를 들어, 피보나치 시리즈를 생성하기 위한 재귀 제형을 고려하십시오: Fi = Fi-1 + Fi−2, 기본 케이스 F1 = F2 = 1. 그런 다음 F43 = F42 + F41 및 F42 = F41 + F40. 이제 F41은 F43뿐만 아니라 F42의 재귀 하위 트리에서 해결되고있다. 하위 문제의 총 수는 실제로 작지만 (그 중 43 개만), 우리는 이와 같은 순진한 재귀 솔루션을 채택하면 동일한 문제를 반복해서 해결하게됩니다. 동적 프로그래밍은 이러한 사실을 고려하여 각 하위 문제를 한 번만 해결합니다. 이 퍼즐에 대한 동적 프로그래밍 함수 방정식을 도출하려면 동적 프로그래밍 모델의 상태를 쌍 s = (n,k)로 하자, 여기서 하위 문제가 큰 문제 내에 재귀적으로 중첩 될 수 있는 경우 동적 프로그래밍 메서드를 적용할 수 있습니다. 더 큰 문제의 값과 하위 문제의 값 사이에 관계가 있습니다. [1] 최적화 문헌에서 이 관계를 벨만 방정식이라고 합니다. 이전 무차별 대입 솔루션에 대한 총 불량 점수는 5022이며 동적 프로그래밍을 사용하여 더 나은 결과를 만들어 보겠습니다! 일부 프로그래밍 언어는 이름별 호출 평가 속도를 높이기 위해 특정 인수 집합을 사용하여 함수 호출의 결과를 자동으로 기억할 수 있습니다(이 메커니즘은 호출별 필요라고 함). 일부 언어는 이식 가능한 언어(예: 체계, 공통 리스프, 펄 또는 D)를 가능하게 합니다. 일부 언어에는 M.

부사로 의한 메모를 지원하는 표가 있는 프롤로그 및 J와 같은 자동 메모가 내장되어 있습니다. [4] 어떤 경우에도 참조적으로 투명한 함수에 대해서만 가능합니다. 또한 Wolfram 언어와 같은 용어 재작성 기반 언어 내에서 쉽게 액세스할 수 있는 디자인 패턴으로 메모가 발생합니다. 동적 프로그래밍 기술은 주로 이전에 계산된 정보 나 테이블을 보고하지 않고 로컬 의사 결정에 따라 최적화를 시도하는 탐욕스러운 알고리즘과는 달리 수학 유도의 원리를 기반으로합니다. 욕심 알고리즘의 일부 고전적인 경우는 욕심 배낭 문제, 허프만 압축 트리, 작업 일정입니다. 삽입 정렬은 동적 프로그래밍의 예이며, 선택 정렬은 탐욕스러운 알고리즘의 예이며 병합 정렬 및 빠른 정렬은 분할 및 정복의 예입니다. 따라서 이 경우 정렬과 같은 목표를 달성하는 데 다양한 범주의 알고리즘이 사용될 수 있습니다. 이 문제에 대한 해결책은 최적의 제어 법 또는 정책 U = h (x (t) , t) {표시 스타일 mathbf {u} ^{ast }=h(mathbf {x} (t,t)},*s-#p- 표시 스타일 mathbf {x} {{at}를 생성하는 최적의 궤적 x{at}와 x*{at}를 생성하는 최적의 궤적 x{{{at}와 e J^{ast }} . 후자는 동적 프로그래밍의 기본 방정식을 준수 : 2.) 상향식 : 문제를 분석하고 하위 문제가 해결되는 순서를 확인하고 주어진 문제를 향해 사소한 하위 문제에서 해결을 시작합니다.