최적 하부구조

Optimal substructure
그림 1. 최적의 하부 구조를 사용하여 최단 경로 찾기 숫자는 경로의 길이를 나타낸다. 직선은 단일 가장자리를 나타내고, 물결선은 최단 경로를 나타낸다. 즉, 여기에 표시되지 않는 다른 정점이 있을 수 있다.

컴퓨터 과학에서 문제는 그 하위문제의 최적의 솔루션으로 최적의 솔루션을 구축할 수 있다면 최적의 하부구조를 가지고 있다고 한다. 이 속성은 문제에 대한 동적 프로그래밍과 탐욕스러운 알고리즘의 유용성을 결정하는 데 사용된다.[1]

일반적으로 각 단계에서 이것이 최적이라는 것을 유도로 증명할 수 있다면 최적의 하부구조로 문제를 해결하는 데 탐욕스러운 알고리즘이 사용된다.[1] 그렇지 않으면 문제가 중첩되는 하위 문제인 경우 동적 프로그래밍을 사용한다. 적절한 탐욕스러운 알고리즘이 없고 문제가 중복되는 하위 문제를 보여주지 못한다면, 종종 솔루션 공간에 대한 장황하지만 직접적인 검색이 최선의 대안이다.

동적 프로그래밍을 수학적 최적화에 적용함에 있어서, 리차드 벨먼의 최적성의 원칙은 동적 최적화 문제를 일부 시작 기간 t에서 종료 기간 T까지 풀기 위해서는, 후일 s부터 시작하는 하위 문제를 암묵적으로 해결해야 한다는 생각에 근거한다. 이것은 최적의 하부 구조의 한 예다. 최적성의 원리는 벨만 방정식을 도출하기 위해 사용되는데, 이것은 t에서 시작하는 문제의 값이 s에서 시작하는 문제의 가치와 어떻게 관련이 있는지를 보여준다.

예

그림 1에서와 같이 자동차로 두 도시를 여행할 수 있는 가장 짧은 경로를 찾는 것을 고려하십시오. 그러한 예는 최적의 하부구조를 보여줄 가능성이 높다. 즉 시애틀에서 로스앤젤레스로 가는 최단 노선이 포틀랜드를 거쳐 그 다음 새크라멘토를 통과한다면 포틀랜드에서 LA로 가는 최단 노선이 새크라멘토를 통과해야 한다. 즉, 포틀랜드에서 로스엔젤레스로 어떻게 갈 것인가 하는 문제는 시애틀에서 로스엔젤레스로 어떻게 갈 것인가 하는 문제 안에 내포되어 있다. (그래프의 물결선은 하위 문제에 대한 솔루션을 나타낸다.)

최적의 하부구조를 보여줄 것 같지 않은 문제의 예로 부에노스아이레스에서 모스크바까지 가는 가장 저렴한 항공권을 찾는 문제를 생각해 보자. 비록 그 티켓이 마이애미와 그 다음에 런던에 정차한다고 해도, 우리는 마이애미에서 모스크바까지 가는 가장 싼 티켓이 런던에 정차한다고 단정할 수 없다. 왜냐하면 항공사가 다중 비행 여행을 판매하는 가격은 보통 여행에서 개별 항공편을 판매하는 가격의 합계가 아니기 때문이다.

정의

최적 하부구조에 대한 약간 더 공식적인 정의가 주어질 수 있다. "문제"를 "대안"의 집합으로 하고, 각 대안에는 관련 비용인 c(a)가 있게 한다. 과제는 c(a)를 최소화하는 일련의 대안을 찾는 것이다. 대안이 하위 집합으로 분할될 수 있다고 가정합시다. 즉, 각 대안이 하나의 하위 집합에만 속한다고 가정합시다. 각 부분 집합에 고유한 비용 함수가 있다고 가정해 보십시오. 이러한 각각의 비용 함수의 미니마는 글로벌 비용 함수의 미니마가 동일한 하위 집합으로 제한되는 것과 마찬가지로 찾을 수 있다. 만약 이 미니마가 각 서브셋에 대해 일치한다면, 전체 대안이 아니라 우리가 정의한 더 작은 국지 비용 함수의 미니마로 구성된 집합에서만 글로벌 최소값을 선택할 수 있다는 것은 거의 명백하다. 국소 기능을 최소화하는 것이 "하위 순서"의 문제라면, 그리고 (특히) 한정된 수의 이러한 감소 후에 문제가 사소한 것이 되면, 문제는 최적의 하부 구조를 갖게 된다.

최적의 하부구조 문제

최적의 하부 구조가 없는 문제

  • 가장 긴 경로 문제
  • 추가 체인 지수화
  • 최저가 항공료. (온라인 항공편 검색을 이용하면 A공항에서 B공항으로 가는 가장 저렴한 항공편은 C공항을 통한 단일연결이 수반되지만, A공항에서 C공항으로 가는 가장 저렴한 항공편은 일부 다른 공항 D를 통한 연계가 수반된다는 사실을 자주 발견할 수 있을 것이다.) 그러나 문제가 최대 경유 횟수를 다른 공항 D공항으로 가져간다면, 그 다음에 문제는 최적의 하부 구조를 가지고 있다: 단일 연결을 포함하는 A에서 B로 가는 가장 저렴한 비행은 직접 비행이다; 또는 A에서 목적지 C로 가는 비행과 C에서 B로 가는 최적의 직접 비행이다.

참고 항목

참조

  1. ^ a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). MIT Press. ISBN 978-0-262-03384-8.