Podręcznik

2.1. Algorytmy zachłanne

Algorytmy zachłanne (ang. greedy algorithms) to klasa prostych, ale bardzo skutecznych algorytmów wykorzystywanych do rozwiązywania problemów optymalizacyjnych, zwłaszcza w przypadkach, gdy konieczne jest szybkie znalezienie przyzwoitego rozwiązania. Algorytmy te charakteryzują się tym, że w każdej iteracji podejmują decyzje, wybierając lokalnie najlepsze rozwiązanie, bez oglądania się na konsekwencje przyszłych wyborów.

Zasada działania

Algorytm zachłanny działa na podstawie następującej strategii:

1. W danym momencie algorytm wybiera ten krok, który wydaje się najbardziej obiecujący – jest to tzw. lokalnie optymalny wybór.
2. Decyzje podejmowane są sekwencyjnie, a każde kolejne rozwiązanie opiera się na wcześniej podjętych decyzjach.
3. Algorytm nie wraca do poprzednich wyborów, co oznacza, że raz podjęta decyzja jest ostateczna.

Algorytmy zachłanne często nie gwarantują znalezienia globalnie optymalnego rozwiązania, ale w wielu przypadkach mogą dać zadowalające wyniki w krótkim czasie.

Przykłady problemów i zastosowań

1. Problem plecakowy (Knapsack Problem)

W klasycznym problemie plecakowym mamy zbiór przedmiotów o określonej wadze i wartości, a celem jest wybranie podzbioru tych przedmiotów, aby maksymalizować wartość, nie przekraczając maksymalnej pojemności plecaka.

W wersji zachłannej algorytm wybiera przedmioty w kolejności malejącej wartości w stosunku do wagi (czyli w zależności od tego, które przedmioty mają największy stosunek wartości do wagi). Taka strategia może nie zawsze prowadzić do optymalnego rozwiązania, ale daje szybki i prosty sposób na uzyskanie dobrego wyniku.

2. Problem komiwojażera (Traveling Salesman Problem, TSP)

W problemie komiwojażera celem jest znalezienie najkrótszej trasy, która odwiedzi wszystkie miasta i wróci do punktu początkowego. W heurystyce zachłannej można zastosować strategię, w której algorytm w każdej iteracji wybiera najbliższe nieodwiedzone miasto.

Chociaż taka metoda może prowadzić do zadowalających rozwiązań w prostych przypadkach, w praktyce często prowadzi do tras znacznie dłuższych od optymalnych, zwłaszcza w przypadku bardziej złożonych problemów.

3. Problem pokrycia zbioru (Set Cover Problem)

W tym problemie mamy zbiór elementów oraz kolekcję podzbiorów, a celem jest wybranie jak najmniejszej liczby podzbiorów, które razem pokryją cały zbiór. Heurystyka zachłanna może działać w taki sposób, że w każdej iteracji wybiera podzbiór, który pokrywa największą liczbę niepokrytych jeszcze elementów. Takie podejście nie gwarantuje optymalnego wyniku, ale jest stosowane w praktyce, ponieważ jest proste i efektywne.

Zalety algorytmów zachłannych

1. Szybkość i prostota: Algorytmy zachłanne są łatwe do zrozumienia i implementacji, a także działają szybko, co czyni je atrakcyjnymi w sytuacjach, gdzie czas jest kluczowy.

2. Efektywność: Heurystyki zachłanne często znajdują rozwiązania wystarczająco dobre, nawet jeśli nie są one optymalne. Są szczególnie użyteczne w przypadkach, gdy dokładne rozwiązanie problemu byłoby zbyt kosztowne obliczeniowo.

3. Brak potrzeby pamięci o wcześniejszych decyzjach: Algorytmy zachłanne nie wymagają pamięci o poprzednich stanach, co czyni je mniej zasobochłonnymi w porównaniu do innych metod.

Wady

1. Brak gwarancji optymalności: Największym ograniczeniem heurystyk zachłannych jest brak gwarancji, że znajdą rozwiązanie optymalne. W rzeczywistości, ponieważ algorytm podejmuje decyzje na podstawie lokalnych informacji, może łatwo „utknąć” w suboptymalnym rozwiązaniu. W takich przypadkach inne podejścia heurystyczne, jak np. algorytmy metaheurystyczne (np. wyżarzanie symulowane, algorytmy ewolucyjne), mogą okazać się bardziej skuteczne.
   

2. Zależność od struktury problemu: Algorytmy zachłanne dobrze działają tylko w niektórych klasach problemów. W problemach, gdzie lokalne decyzje mogą prowadzić do złych globalnych wyników, heurystyki zachłanne nie są skuteczne.