Algorytm zachłanny
Algorytm zachłanny (ang. greedy algorithm) to metoda, która w każdym kroku przy wyznaczaniu rozwiązania dokonuje wyboru, który na dany moment wydaje się najkorzystniejszy, nie analizując dalszych konsekwencji tego działania. W praktyce oznacza to, że algorytm ten podejmuje decyzje lokalnie optymalne, wybierając rozwiązanie, które w danej chwili wydaje się najlepsze, kontynuując rozwiązywanie podproblemu wynikającego z tej decyzji.
Typowe zadania rozwiązywane przy użyciu metody zachłannej mają charakter optymalizacyjny, jednak nie zawsze prowadzą do uzyskania optymalnego rozwiązania.
Zbiór rozwiązań
Niech C będzie skończonym zbiorem, w którym wszystkie możliwe rozwiązania problemu P są podzbiorami zbioru C.
Ważne jest, aby istniało kryterium oceny jakości rozwiązania.
Przykład
Rozważmy problem znalezienia trasy podróży z Madrytu do Moskwy. Można go przedstawić jako problem z zakresu teorii grafów, gdzie wierzchołki grafu reprezentują punkty podróży (np. miasta, lotniska, stacje kolejowe, skrzyżowania dróg), a krawędzie odpowiadają możliwym trasom (autostrady, trasy przelotów, przejazdy pociągów itp.). Wagi krawędzi odpowiadają kosztom podróży (np. odległości, ceny biletów). Celem jest odnalezienie minimalnej ścieżki łączącej wierzchołki reprezentujące Madryt i Moskwę. Zbiór wszystkich rozwiązań C składa się zarówno z rozwiązań optymalnych, jak i nieoptymalnych tras, takich jak Madryt – Rzym – Moskwa czy Madryt – Rzym – Tel Awiw-Jafa – Hongkong – Moskwa.
Rozwiązanie zachłanne
Algorytm zachłanny konstruuje rozwiązanie, dodając do zbioru R (zazwyczaj początkowo pustego) elementy ze zbioru C. Wybiera z C element, nazwijmy go c, i sprawdza, czy dodanie go do zbioru R zgodnie z lokalnym kryterium optymalności jest optymalnym rozwiązaniem.
W obu przypadkach element c jest usuwany ze zbioru C.
Istnieje wiele problemów, w których można udowodnić, że rozwiązania zachłanne zawsze są optymalne, np. podczas znajdowania minimalnego drzewa rozpinającego czy najkrótszej ścieżki między dwoma punktami w grafie. W innych przypadkach algorytm zachłanny może przynieść dobre rezultaty jedynie w specyficznych sytuacjach.
Problem wydawania reszty
Algorytm wydawania reszty jest rozwiązaniem zachłannym w przypadku niektórych zestawów monet, takich jak systemy europejskie (1/2/5 € lub zł) czy amerykański. W innych sytuacjach algorytm nie działa poprawnie.
Na przykład, mając dwa rodzaje monet: 2 zł i 5 zł, musimy obliczyć, jaką ilość oraz jakie monety należy wydać, aby reszta wynosiła 6 zł.
Jeżeli algorytm za pierwszą monetę wybierze „piątkę”, to:
1 ⋅ 5 zł jest bliżej osiągnięcia wyniku końcowego (jest to lokalnie lepsze rozwiązanie) niż 1 ⋅ 2 zł. Jednak w kolejnym kroku okaże się, że droga zachłanna była błędna. Wybierając inne monety, docieramy do prawidłowego i optymalnego rozwiązania.
Poprawność rozwiązania zachłannego
Nie ma uniwersalnej metody dowodzenia, czy dla danego problemu rozwiązanie zachłanne zawsze prowadzi do poprawnego (i optymalnego) wyniku. Istnieją jednak kryteria, które mogą wskazywać, że dla danego problemu zastosowanie metody zachłannej jest możliwe.
Własność zachłannego wyboru
Dzięki lokalnie optymalnym wyborom można uzyskać optymalne rozwiązanie całego zadania.
Własność optymalnej podstruktury
Optymalne rozwiązanie całego problemu można osiągnąć jedynie przy założeniu, że podproblemy również mają optymalne rozwiązania.
Przykłady algorytmów zachłannych
- Algorytm Dijkstry
- Algorytm Kruskala
- Algorytm Prima
- Algorytm szeregowania zadań
Zobacz też
Przypisy
Bibliografia
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007. ISBN 978-83-204-3328-9.
