DAA - metoda chciwa
Spośród wszystkich podejść algorytmicznych najprostszym i najprostszym podejściem jest metoda Greedy. W tym podejściu decyzja jest podejmowana na podstawie aktualnie dostępnych informacji bez obawy o skutki bieżącej decyzji w przyszłości.
Chciwe algorytmy budują rozwiązanie część po części, wybierając kolejną część w taki sposób, aby dawało natychmiastowe korzyści. Takie podejście nigdy nie powoduje ponownego rozważenia wcześniej dokonanych wyborów. To podejście jest używane głównie do rozwiązywania problemów optymalizacyjnych. Metoda Greedy jest łatwa do wdrożenia i dość skuteczna w większości przypadków. Dlatego możemy powiedzieć, że algorytm Greedy'ego jest paradygmatem algorytmicznym opartym na heurystyce, który śledzi lokalny optymalny wybór na każdym kroku z nadzieją na znalezienie globalnego optymalnego rozwiązania.
W przypadku wielu problemów nie daje optymalnego rozwiązania, chociaż daje przybliżone (prawie optymalne) rozwiązanie w rozsądnym czasie.
Składniki algorytmu zachłannego
Chciwe algorytmy składają się z pięciu następujących elementów -
A candidate set - Rozwiązanie jest tworzone z tego zestawu.
A selection function - Służy do wybierania najlepszego kandydata do dodania do rozwiązania.
A feasibility function - Służy do określania, czy kandydat może przyczynić się do rozwiązania.
An objective function - Służy do przypisywania wartości do rozwiązania lub częściowego rozwiązania.
A solution function - Służy do wskazania, czy osiągnięto pełne rozwiązanie.
Obszary zastosowań
Chciwe podejście służy do rozwiązywania wielu problemów, takich jak
Znalezienie najkrótszej ścieżki między dwoma wierzchołkami za pomocą algorytmu Dijkstry.
Znalezienie minimalnego drzewa rozpinającego na wykresie za pomocą algorytmu Prima / Kruskala itp.
Tam, gdzie chciwe podejście zawodzi
W wielu problemach algorytm Greedy'ego nie znajduje optymalnego rozwiązania, co więcej, może dać najgorsze rozwiązanie. Takim podejściem nie da się rozwiązać problemów takich jak komiwojażer czy plecak.