Technika konstrukcji algorytmu polegająca na tym, że danej chwili wykonujemy to działanie, które prowadzi do najlepszego wyniku w tej chwili, nosi nazwę zachłannej (ang. greedy algorithms). Jest zdumiewające, że takie postępowanie często prowadzi do dobrych rozwiązań i do algorytmów optymalnych.

ZASADA W każdym kroku, w którym trzeba dokonać wyboru dalszego działania, zawsze wybieramy rozwiązanie lokalnie optymalne, takie które w danym momencie działania algorytmu, wydaje się być najlepsze.

Niech będzie dana tablica A i niech zadanie polega na znalezieniu takiego podzbioru zbioru elementów w tablicy, by ich suma była największa i w każdej kolumnie znajdował się co najwyżej jeden wybrany element. Na rysunku 11.1 przedstawiono tablicę A oraz trzy możliwe wybory. W pierwszym suma elementów wynosi 15, a w drugim 12. Postępowanie polegające na wybraniu z każdej kolumny elementu największego, prowadzi do najlepszego wyniku końcowego (por. rysunek 11.1(b)). Jest to typowy przykład algorytmu zachłannego: optymalne rozwiązanie dla każdej kolumny prowadzi do optymalnego rozwiązania dla całej tablicy A.

Algorytmy zachłanne stosujemy zwykle wtedy, gdy mamy do czynienia z problemami optymalizacyjnymi i, gdy dochodzenie do rozwiązania optymalnego wymaga podejmowania szeregu decyzji. Zaletą algorytmów zachłannych jest zwykle to, że nie tracimy czasu na zastanawianie się jakie będą konsekwencje przyjętego postępowania w przyszłości, staramy się tylko, by aktualne rozwiązanie było optymalne (mówimy o nim, że jest lokalnie optymalne).

W następnych punktach tego wykładu i w wykładzie 12tym omówimy trzy przykłady problemów, w których zastosowanie zachłannego postępowania prowadzi do bardzo dobrych algorytmów. Algorytmami zachłannymi, o których będziemy tu mówić będą: algorytm Huffmana znajdowania optymalnego kodu prefiksowego, algorytm Dijkstry znajdowania najkrótszej ścieżki i algorytm Kruskala znajdowania minimalnego drzewa rozpinającego grafu.

Nie zawsze, jednak, postępowanie zachłanne prowadzi do poprawnych rozwiązań i dlatego trzeba ostrożnie stosować tę technikę konstrukcji algorytmów.

Rozważmy teraz nieco zmodyfikowany problem z przykładu 11.1: znaleźć taki podzbiór zbioru elementów danej tablicy, by suma była największa i by żadne dwa wybrane elementy nie należały do tego samego wiersza, ani do tej samej kolumny. Algorytm zachłanny, zastosowany do rozwiązania tego zadnia, prowadzi w przykładzie przedstawionym na rysunku 11.1 do zbioru {7,4,1}, jeśli postępowanie zaczynamy od pierwszej kolumny, lub do zbioru {3,5,2}, jeśli zaczynam od ostatniej kolumny. Nie są to jednak dobre rozwiązania, bo zbiór {7,3,3} ma największą z możliwych sumę i spełnia kryterium zadania. Wynika stąd, że nie zawsze możemy, z dobrym skutkiem, stosować algorytmy zachłanne. J

Pytanie 1: Przypuśćmy, że mamy wydać resztę w wysokości 78 złotych. Załóżmy, że mamy dostępne dowolne potrzebne banknoty i monety. Jak będzie wyglądało postępowanie zachłanne?


	7	5	1	7	5	1	7	5	1	7	5	1
A=	3	4	3	3	4	3	3	4	3	3	4	3
	2	3	1	2	3	1	2	3	1	2	3	1
		(a)			(b)			(c)			(d)

					Rysunek 11.1