동적 프로그래밍 또는 욕심 많은 방법을 사용하는 문제에 대한 해결책?

Question

동적 프로그래밍이나 욕심쟁이 방법을 사용하는 방법을 결정할 수 있도록 문제가 있어야하는 속성은 무엇입니까?

Answer 1

동적 프로그래밍 문제는 최적의 하부 구조를 나타냅니다. 이것은 문제에 대한 해결책이 엄밀하게 작은 하위 문제에 대한 해답의 함수로 표현 될 수 있음을 의미합니다.

이러한 문제의 한 예로는 matrix chain multiplication입니다.

로컬로 최적의 선택이 완전히 최적의 솔루션으로 연결되는 경우에만 욕심 많은 알고리즘을 사용할 수 있습니다. 이것은 즉시보기가 더 어려울 수 있지만 일반적으로 구현하기가 더 쉽습니다 (여러 가지 작은 하위 문제에 대한 해결책) 대신 여러 가지 고려해야 할 사항 (탐욕적인 선택)이 있기 때문입니다.

하나의 유명한 그리 디 알고리즘은 최소 스패닝 트리를 찾기 위해 Kruskal's algorithm입니다.

Answer 2

정말 알고 있어야하는 엄격한 규칙이 있습니다. 이미 말했듯이 빨간불을 켜야 할 몇 가지가 있지만, 결국에는 경험 만이 말할 수 있습니다.

Answer 3

Cormen, Leiserson, Rivest 및 Stein 's Algorithms 책의 두 번째 에디션에는 욕심 많은 방법이 최적의 솔루션을 산출하는시기를 설명하는 "욕심 많은 방법의 이론적 토대"라는 제목의 섹션이 있습니다 (16.4). 실용적인 많은 사례를 다루지 만, 최적의 결과를 산출하는 모든 욕심 많은 알고리즘이이 이론의 관점에서 이해 될 수있는 것은 아닙니다.

"동적 프로그래밍에서 욕심쟁이 알고리즘으로"제목이 붙은 here이라는 제목의 논문은 동적 프로그래밍의 개선점으로 볼 수 있습니다. 빠른 검사에서, 당신의 관심사일지도 모른다.

Answer 4

우리는 각 단계에서 사용할 수있는 지역 정보를 결정할 때 욕심쟁이 방법을 적용합니다. 우리는 각 단계에서 일련의 결정을 따르면 최적의 해결책을 찾을 것이라고 확신합니다. 그러나 동적 접근 방식에서는 한 단계에서 결정을 내릴 수 있는지 확실하지 않을 수 있으므로 가능한 결정 집합을 수행하므로 가능한 요소 중 하나가 해결책을 제시 할 수 있습니다.