Algorytm zachłanny

W świecie Algorytm zachłanny istnieje nieskończona liczba aspektów i punktów widzenia, które można badać i omawiać. Od historii po wpływ na dzisiejsze społeczeństwo, Algorytm zachłanny to temat, który przez lata przyciągał uwagę i zainteresowanie wielu osób. Niezależnie od tego, czy chodzi o życie Algorytm zachłanny, jego znaczenie w określonym kontekście, czy też jego wpływ zawodowy, istnieje wiele perspektyw i podejść, które można przyjąć, podejmując ten temat. W tym artykule zbadamy różne aspekty Algorytm zachłanny i przeanalizujemy jego znaczenie w różnych kontekstach, prezentując głębsze zrozumienie jego znaczenia i wpływu.

Ten artykuł od 2014-06 zawiera treści, przy których brakuje odnośników do źródeł.
Należy dodać przypisy do treści niemających odnośników do źródeł. Dodanie listy źródeł bibliograficznych jest problematyczne, ponieważ nie wiadomo, które treści one uźródławiają.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Algorytm zachłanny (ang. greedy algorithm) – algorytm, który w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego, tj. najlepiej rokującego w danym momencie wyboru rozwiązania częściowego[1]. Innymi słowy algorytm zachłanny nie dokonuje oceny czy w kolejnych krokach jest sens wykonywać dane działanie, dokonuje decyzji lokalnie optymalnej, dokonuje on wyboru wydającego się w danej chwili najlepszym, kontynuując rozwiązanie podproblemu wynikającego z podjętej decyzji[1].

Typowe zadanie rozwiązywane metodą zachłanną ma charakter optymalizacyjny[1], jednak algorytm zachłanny nie zawsze odnajduje rozwiązanie optymalne[2].

Zbiór rozwiązań

Niech C będzie zbiorem skończonym, takim, że wszystkie możliwe rozwiązania problemu P są podzbiorami C.

Musi być znane kryterium pozwalające oceniać jakość rozwiązania.

Przykład

Dany jest problem znalezienia trasy podróży z Madrytu do Moskwy. Można na niego spojrzeć, jak na problem z dziedziny teorii grafów – jeżeli z wierzchołkami grafu utożsami się punkty podróży (miasta, lotniska, stacje kolejowe, skrzyżowania dróg itp.), a z krawędziami możliwe trasy przebiegu (autostrady, trasy przelotu samolotów, przejazdu pociągów itp.), z wagami odpowiadającymi kosztom podróży (odległości, ceny biletów itp.) to zadanie sprowadza się do odnalezienia minimalnej ścieżki łączącej wierzchołki opowiadające Madrytowi i Moskwie, a zbiór wszystkich rozwiązań C składa się z rozwiązań zarówno optymalnych, jak i propozycji tras typu Madryt – Rzym – Moskwa czy nawet tak nieoptymalnych jak Madryt – Rzym – Tel Awiw-Jafa – Hongkong – Moskwa.

Rozwiązanie zachłanne

Algorytm zachłanny buduje zadanie, dodając do zbioru R (najczęściej pustego na początku) elementy z C, tj. wybiera z C element, powiedzmy c, i sprawdza, czy według lokalnego (zachłannego) kryterium optymalności jest optymalnym rozwiązaniem. W obu przypadkach element c jest usuwany ze zbioru C.

Istnieje wiele problemów, dla których udowodnić można, że rozwiązanie zachłanne jest zawsze optymalne – między innymi znajdowanie minimalnego drzewa rozpinającego, czy znajdowanie najkrótszej ścieżki między dwoma punktami w grafie. W przypadku innych problemów zachłanność może opłacać się jedynie w szczególnych przypadkach.

Problem wydawania reszty

 Osobny artykuł: Problem wydawania reszty.

Algorytm wydawania reszty w przypadku niektórych zestawów monet jest rozwiązywalny na sposób zachłanny – między innymi w przypadku systemów europejskich (1/2/5 € lub zł), lub systemu amerykańskiego. W innych przypadkach jednak algorytm się nie sprawdzi.

Przykładowo, dane są dwa rodzaje monet: 2 zł i 5 zł. Należy obliczyć ile, i jakich monet należy wydać, by reszta wynosiła 6 zł.

Gdy dobór pierwszej monety będzie zachłanny, to algorytm wybierze jedną „piątkę”, bo zł jest bliżej wyniku ostatecznego (jest lokalnie lepszym rozwiązaniem), niż zł. Jednak już w następnym kroku okaże się, że droga zachłanna była w tym przypadku drogą ślepą. Postępując niezachłannie, dochodzimy ostatecznie do prawidłowego i optymalnego wyniku.

Poprawność rozwiązania zachłannego

Nie istnieje ogólna metoda dowodzenia, czy dla danego problemu rozwiązanie zachłanne (zawsze) odnajduje poprawny (i optymalny) wynik. Istnieją jednak stosujące się do samego problemu kryteria, pozwalające sądzić, iż dla owego problemu istnieje rozwiązanie zachłanne.

Własność zachłannego wyboru

za pomocą lokalnie optymalnych (zachłannych) wyborów można uzyskać optymalne rozwiązanie całego zadania.

Własność optymalnej podstruktury

 Osobny artykuł: Własność optymalnej podstruktury.
optymalne rozwiązanie całego problemu jest możliwe tylko przy optymalnym rozwiązaniu podproblemów[3].

Przykłady algorytmów zachłannych

Zobacz też

Przypisy

  1. ↑ a b c Cormen i in. 2007 ↓, s. 375.
  2. ↑ Cormen i in. 2007 ↓, s. 378.
  3. ↑ Cormen i in. 2007 ↓, s. 380.

Bibliografia

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007. ISBN 978-83-204-3328-9.