문제

나는 동적 프로그래밍에서 최적의 하위 구조 속성의 사용에 대한 더 완전한 그림을 얻으려고 노력하고 있지만 왜 그것을 증명해야 하는지는 알지 못했습니다. 어느 문제에 대한 최적 솔루션에는 하위 문제에 대한 최적 솔루션이 포함됩니다.

그걸 보여주는 것만으로도 충분하지 않을까요? 일부 문제에 대한 최적 솔루션에는 이 속성이 있으며 이를 사용하여 재귀 알고리즘에 의해 구축된 솔루션이 적어도 최적 솔루션만큼 좋기 때문에 자체적으로 최적이 될 것이라고 주장할 수 있습니까?즉, 우리 알고리즘의 정확성 주장에서 모든 최적 솔루션이 하위 문제에 대한 최적 솔루션을 포함해야 하는 위치를 파악하지 못했습니다.

명확히 하기 위해:

최적의 하위 구조에 대한 CLRS 정의는 "다음과 같은 경우 문제가 최적의 하위 구조를 나타냅니다. 어느 문제에 대한 최적해에는 하위 문제에 대한 최적해가 포함되어 있습니다."

"문제가 다음과 같은 경우 최적의 하위 구조를 보인다"라고 말하는 것만으로는 충분하지 않은 이유는 무엇입니까? 일부 문제에 대한 최적의 솔루션에는 하위 문제에 대한 최적의 솔루션이 포함되어 있습니다."?

도움이 되었습니까?

해결책

나는 대략적으로 최적의 솔루션을 찾는 동적 프로그램을 포함하는 근사 알고리즘에 대한 연구에서 이것 때문에 약간 괴로움을 겪었습니다.동적 프로그램의 정확성에 대해 생각하는 올바른 방법은 (복잡도 이론의 의미에서) 문제를 하위 문제로 줄이는 것이라고 생각합니다.이러한 감소는 종종 재귀적으로 적용되고 메모 기능을 통해 적용되지만 지금은 세부 사항입니다.

A를 문제로 하고 B를 하위 문제로 둡니다.일반화된 데카르트 곱을 통해 여러 개의 독립적인 하위 문제를 하나로 결합할 수 있으므로 하위 문제는 하나만 있습니다.축소는 두 가지 기능으로 구성됩니다.f는 A-인스턴스에서 B-인스턴스로, h는 B-솔루션에서 A-솔루션으로입니다.우리에게 필요한 정확성 속성은 각 B 인스턴스에서 해당 최적 B 솔루션(오라클)까지의 모든 함수 g에 대해 구성 h 입니다.g .f는 각 A 인스턴스에서 해당 최적 A 솔루션까지의 함수입니다.(h가 A 인스턴스에 액세스해야 하는 경우 해당 인스턴스가 해당 B 솔루션에 그대로 복사되어야 하는 A 인스턴스를 포함하도록 B를 확장합니다.)

요점을 말하자면, 특정 A 인스턴스와 최적의 A 솔루션에 대해 파이프라인 h와 같은 오라클 g가 존재할 필요는 없습니다.g .f는 주어진 인스턴스에서 해당 솔루션을 생성합니다.(즉, h는 전사적일 필요가 없습니다.) 반면, h는 f에 의해 구성된 B-인스턴스에 대해 g에서 가능한 모든 최적 B-해를 처리할 수 있어야 합니다.

h가 올바른지 확인하기 위한 한 가지 일반적인 전략은 A-솔루션에서 B-솔루션으로 "하위 구조" 함수 k를 찾고 하위 구조를 "접속"하는 방법, 즉 A-솔루션 x와 a가 주어지면 이를 증명하는 것입니다. k(x)보다 나쁘지 않은 B-해 y, k(x') = y인 x보다 나쁘지 않은 A-해 x'가 존재합니다.그러면 h는 입력 k에 해당하는 역이미지의 모든 것을 최적화할 수 있습니다.접합이 모든 솔루션 x에 적용될 필요는 없으며 단지 하나의 최적 솔루션만 적용됩니다.

다른 팁

동적 프로그래밍에서는 문제를 더 작은 하위 문제로 분리하고 조작을 수행하고 더 큰 답변을 위해 답변을 제공합니다. 재귀 접근법 (및 일치 없음)과 매우 유사합니다.

이제, 우리가 공식적으로 그러한 알고리즘의 정확성을 증명할 때 이것은 유도에 의해 수행됩니다. 우리는 우리의 'Base 절'이 정확한 것 (일반적으로 매우 쉽습니다)이며, 현재 하나의 것보다 작은 문제가 최적 인 것으로 가정합니다. 그런 다음 우리는이 가설을 사용하여 더 큰 문제의 정확성을 증명합니다.

모든 솔루션이 최적 인 것을 알지 못했다면 하나의 추가 단계를 사용하여 더 큰 문제에 대한 최적의 해결책에 최적의 해결책에 최적의 해결책을 수정할 수 있음을 증명할 수는 없습니다. 이 주장을 증명할 수있는 충분한 정보.

서브 프로 파일 중 일부가 최적의 해결책이라는 것을 알고 있다면, 우리가 최적의 해결책을 가지고있는이 하위 프로바스를 사용하는 것이 충분하지는 않습니다. ...에

예를 들어 배낭을 찾아보고 DP 단계를 살펴 보겠습니다. 

f(x,i) = max(f(x-weight[i],i-1) +val[i], f(x,i-1))
.

우리가 그들 중 하나만 알고있는 경우 최적이면 알고리즘을 증명할 수 없었습니다. 우리가 최적의 해결책이없는 경우 '다른'사례가 필요했을 수도 있기 때문에 알고리즘이 올바르지 않습니다.

f(x,i-1)에서 max()를 선택하면 잘못된 선택이었을 수 있습니다. 우리가 모든 하위 프로바스에 최적의 해결책을 갖도록 보장함으로써 우리는 이것이 일어날 수 없는지 확인합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top