Algorytm zachłanny

Algorytm zachłanny

Algorytm zachłanny (ang. greedy algorithm) to metoda rozwiązywania problemów, która w każdym kroku dokonuje lokalnie optymalnego wyboru. Oznacza to, że podejmuje decyzje, które wydają się najlepsze w danej chwili, bez oceny dalszych konsekwencji tych wyborów. Choć algorytmy zachłanne są często stosowane w zadaniach optymalizacyjnych, nie zawsze prowadzą do rozwiązania optymalnego.

Zbiór rozwiązań

Problem rozwiązywany przez algorytm zachłanny oparty jest na zbiorze możliwych rozwiązań, oznaczanym jako C. Kluczowe jest posiadanie kryterium, które pozwala ocenić jakość danego rozwiązania.

Przykład zastosowania

Rozważmy problem znalezienia trasy z Madrytu do Moskwy. Możemy go przedstawić jako problem z teorii grafów, gdzie wierzchołkami są punkty podróży, a krawędziami możliwe trasy. W tym przypadku celem jest znalezienie minimalnej ścieżki między dwoma wierzchołkami, a zbiór rozwiązań C obejmuje zarówno trasy optymalne, jak i nieoptymalne.

Rozwiązanie zachłanne

Algorytm zachłanny buduje rozwiązanie, dodając elementy z C do zbioru R. Wybiera element c i sprawdza, czy $Rcup\; c$ jest optymalnym rozwiązaniem według lokalnego kryterium. Element c jest następnie usuwany z C. Dla niektórych problemów, takich jak znajdowanie minimalnego drzewa rozpinającego, algorytm zachłanny zawsze dostarcza rozwiązanie optymalne. W innych przypadkach jego skuteczność może być ograniczona.

Problem wydawania reszty

Algorytm wydawania reszty może być zastosowany w niektórych systemach monetarnych, jak europejski czy amerykański. Jednak w innych przypadkach może prowadzić do błędnych wyników. Przykład z monetami 2 zł i 5 zł pokazuje, że zachłanny wybór nie zawsze prowadzi do optymalnego rozwiązania, a lepsze wyniki można uzyskać poprzez bardziej przemyślane podejście.

Poprawność rozwiązania zachłannego

Brakuje ogólnej metody dowodzenia poprawności algorytmu zachłannego. Istnieją jednak kryteria, które mogą wskazywać, że dla danego problemu rozwiązanie zachłanne będzie poprawne.

Własności algorytmu zachłannego

• Własność zachłannego wyboru: Lokalnie optymalne wybory mogą prowadzić do optymalnego rozwiązania całości problemu.
• Własność optymalnej podstruktury: Optymalne rozwiązanie całego problemu zależy od optymalnych rozwiązań jego podproblemów.

Przykłady algorytmów zachłannych

• Algorytm Dijkstry
• Algorytm Kruskala
• Algorytm Prima
• Algorytm szeregowania zadań