ALG#4

234 Rozdział 9. Zaawansowane techniki programowania

problemu. Mimo iź wersje iteracyjne i rekurencyjne są tej samej klasy, to prostota zapisu rekurencyjnego jest najlepszym argumentem za jego zastosowaniem.

Procedura przeszukiwaniu binarnego również może być zaklasyfikowana do metody ,.dziel-i-rządź”, choć „filozoficznie” różni się nieco od schematu ze strony 225. Jest ona dobrym przykładem na to, jak dobry algorytm może przyspieszyć rozwiązanie postawionego problemu, dla którego znana jest prosta, ale nieefektywna metoda (przeszukiwanie liniowe).

9.2.Algorytmy „żarłoczne”, czyli przekąsić coś nadszedł już czas...

Nazwa nowej metody jest bardzo intrygująca, ale w literaturze przedmiotu przyjęło się nazywać pewną klasę metod jako „żarłoczne” (ang. greedy, franc. glouton). Algorytmy te służą do odnajdywania rozwiązań, które mają zastosowanie w odszukiwaniu przepisu na rozwiązanie danego problemu. Przepis ten jest obarczony pewnymi założeniami (ograniczeniami), które mogą na przykład żądać podania rozwiązania optymalnego wg pewnych kryteriów. Chcąc skonstruować ów przepis, mamy do czynienia z szeregiem opcji tworzących zbiór danych wejściowych. Cechą szczególną algorytmu „żarłocznego” jest to, że w każdym etapie poszukiwania rozwiązania wybiera on opcję lokalnie optymalną. W zależności od lego doboru, rozwiązanie globalne może być również optymalne, ale nie jest to gwarantowane. Omawiana metoda najlepiej odpowiada pewnej klasie zadań natury optymalizacyjnej: podać najkrótszą drogę w grafie, określić optymalną kolejność wykonywania pewnych zadań przez komputer etc.

Metoda algorytmów „żarłocznych” odpowiada ludzkiej naturze, gdyż bardzo często otrzymując jakieś zadanie zadowalamy się jego szybkim i w miarę poprawnym rozwiązaniem, choć niekoniecznie optymalnym.

Schemat generalny algorytmu jest następujący:

żarłok(W)

(

ROZW =0; // zbiór pusty

dopóki(nie Znalezione (ROZW) i W *<j>) wykonuj:

I

X-Kybór(W);

jeśli Odpowiada (X) to ROZW=ROZWU (X) ;

)

]eśii Znaleziono(ROZW) zwróć ROZW;