Chciwy algorytm

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:

  1. Algorytm jest łatwiejszy do opisania .
  2. 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

  1. Po pierwsze, zestaw rozwiązań (zawierający odpowiedzi) jest pusty.
  2. Na każdym kroku element jest dodawany do zestawu rozwiązań.
  3. Jeśli zestaw rozwiązań jest wykonalny, bieżąca pozycja jest zachowywana.
  4. 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:

  1. Utwórz pusty zestaw rozwiązań = ().
  2. monety = (5, 2, 1)
  3. suma = 0
  4. Sumując ≠ 28, wykonaj następujące czynności.
  5. Wybierz monetę C z monet, których suma + C <28.
  6. Jeśli suma C +> 28, nie zwraca żadnego rozwiązania.
  7. W przeciwnym razie suma = suma + C.
  8. 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

Interesujące artykuły...