„Bierz najlepsze teraz” czasem daje optimum — a czasem wyraźnie przegrywa
Algorytm zachłanny podejmuje w każdym kroku lokalnie najlepszą decyzję i nie cofa się, by poprawić wcześniejsze wybory. Taka strategia potrafi być idealna, ale tylko wtedy, gdy struktura problemu gwarantuje, że lokalne decyzje można bezpiecznie wbudować w rozwiązanie globalne. Problem wydawania reszty pokazuje pułapkę. Dla niektórych systemów nominałów wybieranie zawsze największej możliwej monety daje minimalną liczbę monet, lecz dla innych nie. Princeton podaje przykład nominałów, przy których dla 140 zachłanna metoda wybiera 100+34+1+1+1+1+1+1, podczas gdy optimum to 70+70. Intuicja nie zastępuje więc dowodu własności zachłannego wyboru.
Zachłanność jest kusząca, bo decyzje są ostateczne
Algorytmy zachłanne mają niezwykle atrakcyjną konstrukcję: spójrz na bieżącą sytuację, wybierz najlepszą dostępną opcję i idź dalej. Nie przechowuj ogromnego drzewa alternatyw, nie cofaj się i nie analizuj wszystkich kombinacji. Jeśli strategia jest poprawna, często otrzymujemy algorytm prosty, szybki i pamięciowo oszczędny.
Problem polega na słowie „jeśli”. Lokalnie najlepszy ruch może zablokować późniejsze możliwości. To, że wybór wygląda rozsądnie w danym momencie, nie mówi jeszcze nic o globalnej optymalności. Dlatego w teorii algorytmów zachłanność nie jest zasadą typu „wybieraj największe i będzie dobrze”, lecz techniką wymagającą dowodu, że pewien lokalny wybór zawsze można znaleźć w jakimś rozwiązaniu optymalnym.
Monety ujawniają pułapkę w najbardziej namacalny sposób
W problemie wydawania reszty chcemy uzyskać kwotę przy użyciu minimalnej liczby monet. Naturalny algorytm kasjera bierze największy nominał, który nie przekracza pozostałej kwoty, i powtarza operację. Dla niektórych systemów monet działa optymalnie. Nie wynika jednak z tego, że zadziała dla dowolnego zestawu nominałów.
Materiały Princeton pokazują kontrprzykład dla zestawu obejmującego m.in. 1, 10, 21, 34, 70 i 100. Dla kwoty 140 zachłanny wybór zaczyna od 100, następnie bierze 34 i sześć jedynek — razem osiem sztuk. Rozwiązanie optymalne to dwie monety po 70. Pierwszy wybór wyglądał najlepiej lokalnie, ale właśnie on zamknął drogę do najlepszego wyniku globalnego.
Dlaczego dla jednych nominałów działa, a dla innych nie
Zestawy monet, dla których standardowy algorytm zachłanny zawsze daje minimalną liczbę monet, nazywa się kanonicznymi. Sama obecność monety o wartości 1 gwarantuje tylko, że rozwiązanie istnieje, nie że zachłanne jest najlepsze. Kozen i Zaks badali, kiedy można znaleźć kontrprzykład dla danego systemu nominałów i jak testować własność zachłannego rozwiązania.
To dobry przykład różnicy pomiędzy empirycznym zaufaniem a dowodem. Możemy sprawdzić tysiące kwot i nie znaleźć błędu, a mimo to algorytm może zawieść później. Dla konkretnej rodziny problemów potrzebna jest własność strukturalna albo formalny argument wskazujący, dlaczego bezpiecznie można podjąć lokalną decyzję bez patrzenia w przyszłość.
Zachłanny algorytm bywa poprawny z zaskakująco prostą regułą
Nie należy z tego wyciągać wniosku, że algorytmy zachłanne są podejrzane. Dla wielu problemów są dokładnie właściwym narzędziem. W klasycznym wyborze maksymalnej liczby niepokrywających się przedziałów strategia wybierania zadania kończącego się najwcześniej prowadzi do optimum. W minimalnym drzewie rozpinającym algorytmy Kruskala i Prima również podejmują lokalne wybory chronione przez własności grafu.
Prawdziwa lekcja brzmi więc: forma algorytmu nie wystarcza do oceny poprawności. Dwie niemal identycznie brzmiące strategie „wybieraj najlepsze dostępne” mogą mieć zupełnie różny status matematyczny. Jedna posiada dowód wymiany lub inną własność zachłannego wyboru; druga ma kontrprzykład o kilku elementach.
Kiedy intuicja jest sygnałem do szukania kontrprzykładu
Jeśli rozwiązanie zachłanne wydaje się „oczywiste”, warto zadać dwa pytania. Czy obecny wybór może ograniczyć przyszłe kombinacje? I czy z dowolnego rozwiązania optymalnego można skonstruować równie dobre rozwiązanie zawierające nasz zachłanny wybór? Drugie pytanie prowadzi do typowych dowodów wymiany: pokazujemy, że nawet jeśli optimum wybrało coś innego, można bez pogorszenia zamienić jego decyzję na naszą.
Jeżeli takiego argumentu nie ma, poszukiwanie małego kontrprzykładu jest często najlepszym testem. Właśnie dlatego problem monet jest tak dydaktyczny: pokazuje, że „największy dostępny nominał” jest przekonującą heurystyką, ale poprawność zależy od systemu nominałów, a nie od siły intuicji.
Poprawność zachłanności zwykle wymaga dowodu wymiany, nie intuicji
Gdy algorytm zachłanny rzeczywiście jest optymalny, typowy dowód pokazuje, że dowolne rozwiązanie optymalne można krok po kroku przekształcić tak, aby zgadzało się z wyborem zachłannym, nie pogarszając wyniku. To tak zwany exchange argument. W problemie wyboru niepokrywających się przedziałów można na przykład zastąpić pierwszy przedział rozwiązania optymalnego tym, który kończy się najwcześniej, i nie stracić miejsca na późniejsze zadania. Taki dowód wyjaśnia, dlaczego lokalna decyzja jest bezpieczna. W problemie monet dla dowolnych nominałów analogicznego argumentu może po prostu nie być, a kontrprzykład obala regułę. To cenna dyscyplina: „wydaje się rozsądne” jest dobrym źródłem pomysłu na algorytm, ale dopiero dowód lub kontrprzykład mówi, czy pomysł rozwiązuje cały problem.