ALGORTYMY ZACHŁANNE
Algorytm zachłanny (ang. greedy algorithm) wykonuje działanie, które wydaje się najlepsze w danej chwili, nie uwzględniając tego, co może dziać się w przyszłości. Wybiera zatem lokalnie optymalną możliwość w nadziei, że doprowadzi ona do globalnie optymalnego rozwiązania. Podstawową zaletą algorytmu zachłannego jest to, że nie traci się czasu na rozważanie, co może zdarzyć się później. Zadziwiające jest , że w wielu sytuacjach daje on optymalne rozwiązanie problemu.
Przykład:
Rozpatrzmy dla przykładu problem kasjera, który ma wydać resztę, będącą dowolną kwotą między 0.01 $ a 0.99 $, przy użyciu minimalnej liczby monet. Jednym z możliwych rozwiązań jest najpierw użycie monety o największej dopuszczalnej wartości, redukując w ten sposób problem do wypłacenia mniejszej kwoty.
Aby na przykład wydać 0.94 $,
1) kasjer wypłaci półdolarówkę (zostawiając do wypłacenia 0.44 $)
2) następnie ćwierćdolarówkę (zostaje 0.19 $)
3) dziesięciocentówkę (zostanie 0.09 $)
4) pięciocentówkę (zostanie 0.04 $)
5) i w końcu cztery jednocentówki - w sumie 8 monet
Jest to minimalna liczba i faktycznie algorytm zachłanny jest optymalny dla monet amerykańskich (chociaż niekoniecznie dla innych systemów monetarnych).
Jak przekonać się, czy algorytm zachłanny poprawnie rozwiązuje dany problem optymalizacyjny? Nie ma niestety żadnej ogólnej metody, lecz istnieją cechy charakterystyczne dla większości problemów poddających się strategii zachłannej: własność wyboru zachłannego oraz optymalna podstruktura.
Własność wyboru zachłannego- za pomocą lokalnie optymalnych (zachłannych) wyborów można uzyskać globalnie najlepsze rozwiązanie. W algorytmie zachłannym dokonujemy wyboru, który wydaje się być najlepszy w danej chwili, a następnie rozwiązujemy podproblemy, które wynikają z podjętej decyzji. Wybory podejmowane w algorytmie zachłannym mogą zależeć od dotychczasowych decyzji, lecz nie mogą być uzależnione od przyszłych wyborów lub od rozwiązań podproblemów. Sprawia to, że w przeciwieństwie do algorytmów opartych na programowaniu dynamicznym, rozwiązujących problem w sposób wstępujący, algorytmy zachłanne znajdują rozwiązanie w sposób zstępujący, podejmując kolejno decyzje zachłanne, stopniowo redukując podproblemy do coraz mniejszych. Musimy oczywiście udowodnić, że wybór zachłanny w każdym kroku prowadzi do globalnie optymalnego rozwiązania, niezbędna jest więc ludzka intuicja i pomysłowość. Wykazuje się zwykle, że można sprowadzić go do rozwiązania, którego początkiem jest podjęcie decyzji zachłannej w pierwszym kroku, oraz wykazuje się, że ten wybór redukuje problem do podobnego, ale o mniejszym rozmiarze. Aby następnie uzasadnić, że strategię zachłanną można stosować w każdym następnym kroku, wystarczy użyć indukcji. Jeśli wykażemy, że wybór zachłanny sprowadza problem do podobnego o mniejszym rozmiarze, to dowód poprawności algorytmu sprowadza się do uzasadnienia optymalnej podstruktury optymalnego rozwiązania.
Problem wykazuje optymalną podstrukturę, jeśli najlepsze rozwiązanie jest funkcją optymalnych rozwiązań podproblemów.
Kolejny przykład dotyczy problemu przydzielania dostępu do zasobu wykorzystywanego podczas wykonywania pewnych zajęć. Przekonamy się, że algorytm zachłanny stanowi prostą a zarazem elegancka metodę znajdowania największego zbioru wzajemnie zgodnych (nie zakłócających się) czynności.
Niech będzie dany zbiór S = {1, 2, ..., n} składający się z n proponowanych zajęć, do których mają być przydzielone zasoby, takie jak na przykład sala wykładowa, w której może się odbywać w danej chwili tylko jedno z tych zajęć. Każde zajęcie ma swój czas rozpoczęcia si oraz czas zakończenia fi, takie że si <= fi.Jeśli zajęcie o numerze i zostanie wytypowane, to zajmuje zasób przez prawostronnie otwarty przedział czasu [si, fi). Zajęcia o numerach i oraz j są zgodne (nie zakłócają się), jeżeli przedziały [si, fi) oraz [sj, fj ) nie zachodzą na siebie (tzn. i oraz j są zgodne, jeśli si >= fj lub sj >= fi). Problem wyboru zajęć polega na wyborze największego podzbioru parami zgodnych zajęć. Bez utraty ogólności zakładamy, że zajęcia są uporządkowane ze względu na czas zakończenia: f1 <= f2 <= ... <= fn
n = = ilość zajęć
A = {1} - jednoelementowy zbiór {1} staje się wartością zmiennej A
j = 1 - zmiennej j zostaje przypisany numer tego zajęcia
for i = 2 to n
do if si >= fj
then A = A ∪ {i}
j = i
return A
Ponieważ zajęcia są rozpatrywane w porządku rosnącego czasu zakończenia, fi jest zawsze największym czasem zakończenia zajęcia należącego do A, tj. fj = max{fk: k
A}
W wierszach 2-3 wybierane jest zajęcie 1, jednoelementowy zbiór {1} staje się wartością zmiennej A, a zmiennej j zostaje przypisany numer tego zajęcia. W wierszach 4-7 są kolejno rozpatrywane wszystkie zajęcia i; każde z nich zostaje dołączone, jeżeli jest zgodne ze wszystkimi dotychczas dołączonymi zajęciami. Aby stwierdzić, czy zajęcie i jest zgodne z każdym zajęciem ze zbioru A, wystarczy sprawdzić (wiersz 5), czy jego czas rozpoczęcia si nie jest wcześniejszy niż czas zakończenia fj zajęcia ostatnio dodanego do zbioru A. Jeśli zajęcie jest zgodne, to w wierszach 6-7 zostaje ono dodane do zbioru A oraz aktualizowana jest zawartość zmiennej j.
Algorytm ten zwany jest GREEDY-ACTIVITY-SELECTOR i udowodnione jest, że zawsze generuje on optymalny wybór zajęć.