DAA-동적 프로그래밍

동적 프로그래밍은 최적화 문제에도 사용됩니다. 나누기 정복 방법과 마찬가지로 동적 프로그래밍은 하위 문제의 솔루션을 결합하여 문제를 해결합니다. 또한 동적 프로그래밍 알고리즘은 각 하위 문제를 한 번만 해결 한 다음 그 답을 테이블에 저장하므로 매번 답을 다시 계산하는 작업을 피할 수 있습니다.

문제의 두 가지 주요 속성은 주어진 문제가 동적 프로그래밍을 사용하여 해결 될 수 있음을 시사합니다. 이러한 속성은overlapping sub-problems and optimal substructure.

중복되는 하위 문제

Divide-and-Conquer 접근 방식과 마찬가지로 Dynamic Programming은 솔루션을 하위 문제에 결합합니다. 주로 하나의 하위 문제 해결이 반복적으로 필요한 경우에 사용됩니다. 계산 된 솔루션은 테이블에 저장되므로 다시 계산할 필요가 없습니다. 따라서이 기술은 중복되는 하위 문제가있는 경우 필요합니다.

예를 들어 이진 검색에는 중복되는 하위 문제가 없습니다. 반면 피보나치 수의 재귀 프로그램에는 중첩되는 하위 문제가 많습니다.

최적의 하위 구조

주어진 문제는 하위 문제의 최적 솔루션을 사용하여 주어진 문제에 대한 최적의 솔루션을 얻을 수있는 경우 최적의 하위 구조 속성을 갖습니다.

예를 들어, 최단 경로 문제에는 다음과 같은 최적의 하부 구조 속성이 있습니다.

노드가 x 소스 노드의 최단 경로에 있습니다. u 목적지 노드로 v, 다음에서 가장 짧은 경로 u ...에 v 가장 짧은 경로의 조합입니다. u ...에 x및 최단 경로 x ...에 v.

Floyd-Warshall 및 Bellman-Ford와 같은 표준 All Pair Shortest Path 알고리즘은 동적 프로그래밍의 전형적인 예입니다.

동적 프로그래밍 접근법의 단계

동적 프로그래밍 알고리즘은 다음 네 단계를 사용하여 설계되었습니다.

• 최적 솔루션의 구조를 특성화합니다.
• 최적 솔루션의 값을 재귀 적으로 정의합니다.
• 일반적으로 상향식 방식으로 최적 솔루션의 가치를 계산합니다.
• 계산 된 정보에서 최적의 솔루션을 구성합니다.

동적 프로그래밍 접근법의 응용

• 매트릭스 체인 곱셈
• 가장 긴 공통 하위 시퀀스
• 여행하는 세일즈맨 문제