Algorytmy zachłanne

Algorytmy zachłanne (ang. greedy algorithms) – algorytmy podejmujące w każdym kroku taką decyzję, która w danej chwili wydaje się najkorzystniejsza. Inaczej mówiąc, algorytmy zachłanne dokonują zawsze wyborów lokalnie optymalnych licząc, że doprowadzi to do znalezienia rozwiązania globalnie optymalnego. W ogólnym przypadku algorytmy zachłanne nie zawsze znajdują rozwiązanie optymalne. Są one zatem podzbiorem algorytmów heurystycznych. Jednocześnie są to algorytmy deterministyczne – nie ma w nich losowości.

Bardzo prostym przykładem algorytmu zachłannego może być szukanie najwyższego punktu na określonym obszarze poprzez przesuwanie się zawsze w kierunku największego nachylenia (nigdy się nie cofając ani nie rozpatrując kilku wariantów drogi). Jak widać, w ten sposób prawdopodobnie dojdziemy do wierzchołka położonego najbliżej od punktu początkowego, który niekoniecznie będzie najwyższym.

Przykłady algorytmów dokładnych

Choć generalnie algorytmy zachłanne nie zawsze znajdują rozwiązanie optymalne, to istnieją takie problemy obliczeniowe, dla których algorytmy te dają gwarancję znalezienia rozwiązania optymalnego. Przykładami takich algorytmów są:

• Algorytm Dijkstry poszukujący najkrótszych ścieżek,
• Algorytm Kruskala poszukujący minimalnego drzewa rozpinającego.

Ciekawym przypadkiem jest problem wydawania reszty, gdzie algorytm zachłanny w zależności od zbioru nominałów daje gwarancję znalezienia rozwiązania optymalnego albo nie.

Przykłady algorytmów niedokładnych

Algorytmy zachłanne są również wykorzystywane tam, gdzie nie dają gwarancji znalezienia rozwiązania optymalnego. Przykładami takich algorytmów są algorytmy rozwiązujące problem komiwojażera:

• Algorytm najbliższego sąsiada,
• Algorytm najmniejszej krawędzi.

Własności problemów

Aby algorytm zachłanny zawsze zwracał rozwiązanie optymalne, problem powinien mieć dwie własności:

• Własność optymalnej podstruktury – własność oznaczająca, że optymalne rozwiązanie problemu jest funkcją optymalnych rozwiązań podproblemów (czyli znając optymalne rozwiązania podproblemów można efektywnie wyznaczyć rozwiązanie problemu). Własność ta jest wspólna dla metody zachłannej i dla programowania dynamicznego.
• Własność wyboru zachłannego – własność oznaczająca, że za pomocą lokalnie optymalnych wyborów można znaleźć rozwiązanie globalnie optymalne. Mówiąc inaczej: wystarczy rozwiązać tylko ten podproblem, który można ocenić jako najbardziej obiecujący.

Matroidy a strategia zachłanna

W ocenianiu, czy dany problem można rozwiązać z wykorzystaniem metody zachłannej, przydatna jest teoria związana z matroidami. Matroid jest strukturą składającą się z określonego zbioru elementów oraz z rodziny podzbiorów tego zbioru, która spełnia pewne warunki:

• Jeśli zbiór należy do rodziny, to wszystkie jego podzbiory również.
• Jeśli dwa zbiory o różnej liczbie elementów należą do rodziny, to istnieje w tym większym zbiorze taki element, który po dodaniu do mniejszego zbioru utworzy zbiór również należący do rodziny.

Jeśli każdy z elementów ma przyporządkowaną pewną wagę, to matroid jest określany jako matroid ważony. Jeśli problem obliczeniowy można przedstawić jako poszukiwanie podzbioru o największej wadze w matroidzie ważonym, to problem ten można rozwiązać stosując metodę zachłanną (algorytm zachłanny będzie zwracał rozwiązanie optymalne).

Bibliografia

1. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012.