1. Optimization problem 최적화 문제
- 주어진 문제에 대하여 하나 이상의 많은 해답이 존재할 때, 그 중에서 가장 최적인 해답(optimal solution)을 찾는 문제를 최적화 문제라고 한다.
- 최단경로 찾기 문제가 최적화 문제의 대표적인 예시이다.
2. 최적의 원칙
- 어떤 문제의 입력에 대한 최적 해가 그 입력을 나누어 쪼갠 여러 부분에 대한 최적해를 항상 포함하고 있으면, 그 문제는 최적의 원칙(the principle of optimality, optimal substructure)이 적용된다고 한다.
- 최단경로를 구하는 문제에서
Vk를 Vi에서 Vj로 가는 최적 경로 상의 정점이라고 하자. (Vi -> Vk -> Vj)
이 때 Vi -> Vk로 가는 부분 경로와 Vk -> Vj로 가는 부분경로도 반드시 최적이어야 한다.
3. 최적의 원칙이 적용되지 않는 예: 최장 경로
위와 같은 그래프가 있을 때, v1에서 v4로 가는 최장경로는 [v1, v3, v2, v4]이다.
그러나 이 경로의 부분 경로인 [v1, v3]의 최장경로는 [v1, v2, v3]이다.
따라서 전체 문제의 최적해가 부분 문제의 최적해를 포함하고 있지 않기 때문에 최적의 원칙이 적용되지 않는다.
