1. DP의 개발절차
1. 최적의 해답을 주는 재귀 관계식을 세운다. -> Divide and Conquer를 해본다.
2. bottom-up 방식으로 최적 해를 찾는 계산한다.
3. bottom-up 방식으로 최적 해를 구축한다.
보통은 2번과 3번이 동시에 이루어집니다.
만약 답만 구하고 최적화를 하지 않는다면, 3번이 빠져있는 것입니다.
최적화 문제를 모두 DP로 풀 수 있는 것이 아닙니다. 문제에 최적의 원칙이 반드시 성립해야합니다.
최적의 원칙은 다음과 같습니다.
The Principle of Optimality
if an optimal solution to an instance of a problem always contains optimal solutions to all subinstances.
문제의 instance의 최적 해가 분할된 instance의 최적 해를 항상 포함하면 principle of optimality가 성립한다.
예를 가지고 설명을 드리겠습니다.
vi에서 vj로 가는데 vk가 최적 경로상의 정점이라고 합시다.
그렇다면 vi -> vk도 최적의 경로일거고, vk -> vj도 당연히 최적의 경로겠죠?
따라서 최단 경로 문제에서 부분 경로들이 최단 경로라면, 그것을 합한 경로는 최적이 됩니다.
그러므로 재귀 관계식을 통해서 점점 상향식으로 더 큰 instance에 대한 최적해를 구축해 나갈 수 있습니다.
물론 너무나도 당연한 소리 같지만, DP를 적용하여 최적해를 구할 수 있는지 단정하려면 이 원칙이 성립하는지 증명해야합니다.
다음 예는 원칙이 성립하지 않는 최적화 문제입니다.
간단하죠?
최적 경로가 있음에도, 부분 instance는 최적이 아닙니다.
감사합니다.
지적 환영합니다.