Metoda zachłanna

Metoda ta dobrze działa w sytuacjach, gdy maksymalizujemy lub minimalizujemy pewną wartość. Algorytm w każdej iteracji ma do wyboru pewną liczbę "lokalnych" akcji. W przypadku maksymalizacji wybiera tę, która lokalnie maksymalizuje wartość docelową. W przypadku minimalizacji wybiera akcję o minimalnej wartości. Przedyskutujemy tę metodę na następujących dwóch przykładach.

Wieże na szachownicy

Przypuśćmy, że mamy szachownicę \( n \) na \( n \), na polu \( (i,j) \)-tym leży \( x(i,j) \) monet. Chcemy umieścić \( n \) wież na szachownicy tak, aby żadne dwie się nie atakowały. Zyskiem jest suma monet na wybranych pozycjach. Lokalna akcja to wybranie jednej dopuszczalnej pozycji. Zysk akcji to liczba monet na pozycji. Algorytm zachłanny działa trywialnie: wybieramy pozycję z maksymalnym \( x(i,j) \). Można łatwo zobaczyć, że ten algorytm niekoniecznie da optymalny zysk - da jednak co najmniej połowę optymalnego zysku. Pozostawiamy to jako ćwiczenie. Bardziej formalnie można wyrazić ten problem w terminach skojarzeń w grafach. Najciekawszym przypadkiem jest sytuacja, gdy tablica \( x(i,j) \) jest zerojedynkowa.

Minimalne Sklejanie Par

Przypuśćmy, że mamy ciąg \( n \) nieujemnych liczb \( p_1,p_2,\ldots,p_n \). Lokalna akcja sklejania polega na pobraniu dwóch elementów z ciągu i zastąpieniu ich przez sumę ich wartości. Kosztem akcji jest suma wartości "sklejanych" elementów. Ciąg operacji sklejania kończy się, gdy skleiliśmy wszystko do jednej wartości.
Interesuje nas obliczenie minimalnego sumarycznego kosztu sklejania \( n \) elementów w jeden element. Metoda zachłanna zawsze wybiera akcję o minimalnej wartości.

Algorytm Schemat-Zachłanny

while zbiór możliwych lokalnych akcji jest niepusty do
  wykonaj akcję o minimalnym koszcie; 
return suma kosztów wykonanych akcji;

Można to zapisać bardziej formalnie:
Algorytm Optymalne-Sklejanie-Par

wynik:= 0; 
while mamy co najmniej dwa elementy do 
    zastąp dwa najmniejsze elementy a,b przez a+b  
    wynik:= wynik + a+b;

Pozostawiamy jako ćwiczenie dowód tego, że algorytm ten wyznacza ciąg sklejeń o najmniejszym koszcie. Co będzie, jeśli zamiast obliczać minimalny koszt chcielibyśmy wyznaczyć ciąg, który maksymalizuje sumaryczny koszt? Pozostawiamy to jako ćwiczenie. Algorytm ten jest "szkieletem" efektywnego konstruowania tzw. "drzewa Huffmana".

W naszym przykładzie mogliśmy sklejać elementy, które niekoniecznie są sąsiednie, kolejność elementów w ciągu nie odgrywała roli. Zastanówmy się, co będzie, gdy wprowadzimy do gry kolejność elementów. Załóżmy teraz, że możemy sklejać tylko elementy sąsiednie. Tak zmodyfikowany problem nazwijmy problemem Minimalnego Sklejania Sąsiadów. Możemy w poprzednim algorytmie zastąpić zwrot "dwa najmniejsze elementy" przez "dwa sąsiednie elementy o minimalnej sumie".

Niespodziewanie, nasz algorytm nie zawsze oblicza minimalną wartość, czyli nie jest poprawny. Kontrprzykładem jest ciąg
\( (p1,p2,p3,p4) = (100,99,99,100). \)