Na podstawie podręcznika Wprowadzenie do algorytmów poprawność zachłannego algorytmu wymaga problemu z dwiema właściwościami:
Łatwo jest wymyślić przeciwne przykłady, dla których chciwe rozwiązanie zawodzi z powodu braku właściwości chciwego wyboru, np. Problem plecaka 0/1. Ale trudno mi sobie wyobrazić inną możliwość. Czy ktoś może mi dać problem i odpowiadający mu chciwy algorytm, który spełnia pierwszą właściwość, ale nie drugą?
Odpowiedzi:
Jednym ze standardowych estymatorów w solidnych statystykach jest rodzaj przyciętej średniej, w której wybiera się większość podzbiorów zbioru liczb wejściowych w taki sposób, aby zminimalizować maksymalną różnicę między dowolnymi dwoma wybranymi liczbami, a następnie przyjąć średnią z wybranej podzbiór. Pierwszy krok jest łatwy do wyboru - wybierz medianę jako część swojego podzbioru. Ale kiedy już dokonasz wyboru, pozostały problem nie jest tego samego typu (tj. Nie mamy optymalnych podbudów), więc nie ma oczywistej metody kontynuacji tego algorytmu chciwie. W szczególności nie działa wybieranie median pozostałych punktów. (Powtarzająca się chciwa strategia mediany, wykonana z niewielką ostrożnością, daje środek międzykwartylowy, który jest również solidny, ale nie rozwiązuje tego samego problemu i ma niższy punkt podziału.)