욕심 많은 접근 방식이 효과가 없다는 것을 증명하는 방법

Question

욕심 많은 접근 방식이 최적의 가치를 부여하지 못하는 문제에 대해서는 반대 사례를 찾아 볼 수 있습니다.

그러나 주어진 문제에 대해 일반적으로 욕심 많은 접근 방식이 작동하지 않는다는 것을 증명할 수 있습니까?

Answer 1

나는 가장 기본적인 대답은 어떤 욕심 많은 알고리즘이라도 로컬 최적화를 찾을 수 있다는 것입니다. 문제가 전역 최적화를 나타내는 여러 로컬 최적화를 가지고 있다면, 어떤 욕심 많은 알고리즘이 로컬 최적화 중 하나에 걸릴 수 있습니다.

카운터 예제를 찾으려면 로컬 최적화가있는 문제의 인스턴스를 찾아서 알고리즘을 "속여"로컬 최적으로 만들기 만하면됩니다.

나는 욕심 많은 접근 방식이 효과가 없다는 것을 보여주는 일반적인 방법이 있다고 생각하지 않습니다. 알고리즘을 반박하는 가장 좋은 방법은 올바른 결과를 내지 않는 반례를 찾는 것입니다.