W tym samouczku dowiesz się, czym jest algorytm chciwości. Znajdziesz również przykład zachłannego podejścia.
Chciwy algorytm to podejście do rozwiązania problemu poprzez wybranie najlepszej dostępnej w danym momencie opcji, bez martwienia się o przyszłe skutki, jakie przyniesie. Innymi słowy, najlepsze lokalne wybory mają na celu osiągnięcie najlepszych wyników na całym świecie.
Ten algorytm może nie być najlepszym rozwiązaniem dla wszystkich problemów. W niektórych przypadkach może dawać nieprawidłowe wyniki.
Ten algorytm nigdy nie cofa podjętej decyzji. Ten algorytm działa w podejściu odgórnym.
Główną zaletą tego algorytmu jest:
- Algorytm jest łatwiejszy do opisania .
- Ten algorytm może działać lepiej niż inne algorytmy (ale nie we wszystkich przypadkach).
Wykonalne rozwiązanie
Realne rozwiązanie to takie, które zapewnia optymalne rozwiązanie problemu.
Chciwy algorytm
- Po pierwsze, zestaw rozwiązań (zawierający odpowiedzi) jest pusty.
- Na każdym kroku element jest dodawany do zestawu rozwiązań.
- Jeśli zestaw rozwiązań jest wykonalny, bieżąca pozycja jest zachowywana.
- W przeciwnym razie przedmiot jest odrzucany i nigdy więcej nie jest brany pod uwagę.
Przykład - chciwe podejście
Problem: Musisz dokonać zmiany kwoty, używając jak najmniejszej liczby monet. Kwota: 28 $ Dostępne monety: 5 $ moneta 2 $ moneta 1 $ moneta
Rozwiązanie:
- Utwórz pusty zestaw rozwiązań = ().
- monety = (5, 2, 1)
- suma = 0
- Sumując ≠ 28, wykonaj następujące czynności.
- Wybierz monetę C z monet, których suma + C <28.
- Jeśli suma C +> 28, nie zwraca żadnego rozwiązania.
- W przeciwnym razie suma = suma + C.
- Dodaj C do zestawu rozwiązań.
Do pierwszych 5 iteracji zestaw rozwiązań zawiera 5 monet 5 $. Następnie otrzymujemy monetę 1 $ 2 i wreszcie monetę 1 $ 1.
Aplikacje algorytmów chciwych
- Sortowanie przez wybór
- Problem z plecakiem
- Minimalne drzewo rozpinające
- Problem najkrótszej ścieżki z jednego źródła
- Problem z planowaniem pracy
- Algorytm minimalnego drzewa opinającego Prim
- Algorytm minimalnego drzewa opinającego Kruskala
- Algorytm minimalnego drzewa rozpinającego Dijkstry
- Kodowanie Huffmana
- Algorytm Forda-Fulkersona