Algorytm zachłanny

Z Wikipedii

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. Innymi słowy algorytm zachłanny nie patrzy 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. Typowe zadanie rozwiązywane metodą zachłanną ma charakter optymalizacyjny. W dziedzinie sztucznej inteligencji zachłanna odmiana przeszukiwania lokalnego jest nazywana "podchodzeniem pod wzgórze".

Spis treści 1 Zbiór rozwiązań 1.1 Przykład 2 Rozwiązanie zachłanne 2.1 Problem wydawania reszty 3 Poprawność rozwiązania zachłannego 3.1 Własność zachłannego wyboru 3.2 Własność optymalnej podstruktury

[edytuj] 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

[edytuj] Przykład

Dany jest problem znalezienia trasy podróży z Madrytu do Moskwy. Można na niego spojrzeć jako 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, cenie biletu 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–Hongkong–Moskwa

[edytuj] 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. W przypadku innych problemów zachłanność się nie opłaca:

[edytuj] Problem wydawania reszty

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 (tj. algorytm wybierze jedną "piątkę", bo jest bliżej wyniku ostatecznego (jest lokalnie lepszym rozwiązaniem), niż . 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 ostatecznie dochodzimy do prawidłowego i optymalnego wyniku.

[edytuj] 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ązania zachłanne.

[edytuj] Własność zachłannego wyboru

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

[edytuj] Własność optymalnej podstruktury

optymalne rozwiązanie całego problemu jest możliwe tylko przy optymalnym rozwiązaniu podproblemów

Przykłady algorytmów zachłannych:

• Algorytm Kruskala
• Algorytm Dijkstry
• Algorytm szeregowania zadań

Zobacz też:

• bruteforce
• optymalizacja
• Programowanie dynamiczne