Algorytm zachłanny

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Algorytm zachłanny (ang. greedy algorithm) to taki algorytm, który w celu wyznaczenia rozwiązania przechodzi przez wszystkie możliwe w danej sytuacji kroki. Innymi słowy algorytm zachłanny nie patrzy czy w kolejnych krokach jest sens wykonywać dane działanie, dokonuje decyzji lokalnie optymalnej. W dziedzinie sztucznej inteligencji zachłanna odmiana przeszukiwania lokalnego jest nazywana "podchodzeniem pod wzgórze".

Bardziej formalnie:

Dla wielu problemów Istnieją różne dobre rozwiązania, np. zadanie dojechania z Kołobrzegu do Wrocławia może być rozwiązane podróżą przez Piłę i Poznań. Ale można też pojechać przez Moskwę. Oba rozwiązania są poprawne - określają trasę między interesującymi nas punktami A i B. Jeżeli za kryterium optymalności uznamy długość trasy, trasa I okaże się lepszą, będzie optymalnym rozwiązanie problemu podróży.

Niech C będzie (abstrakcyjnym) skończonym zbiorem, takim, że wszystkie możliwe rozwiązania problemu P są podzbiorami C. Algorytm buduje rozwiązanie zadania, powiedzmy R, tworząc podzbiór zbioru C. Zbiór $R\in C$ ma być według kryterium optymalności najlepszym rozwiązaniem.

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 $R\cup c$ 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 przypaku innych problemów zachłanność się nie opłaca:

Problem wydawania reszt: Dane są dwa rodzaje monet: 2zł i 5zł. Obliczyć ile, i jakich monet należy wydać, by reszta wynosiła 6zł.

Gdy dobór pierwszej monety będzie zachłanny (tj. algorytm wybierze jedną "piątkę", bo $1\cdot5zl$ jest bliżej wyniku ostatecznego (jest lokalnie lepszym rozwiązaniem), niż $1\cdot2zl$ . Jenak 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.

Można jednak udowodnić, że algorytm zachłanny daje zawsze optymalny wynik, gdy każdy z nominałów dostępnych monet jest wielokrotnością nominałów mniejszych, tj.:

zbiór nominałów:
$m 1$
$m_2=k_2\cdot m_1$
$m_3=k_3\cdot m_2\cdot m_1$
$\cdots$
$m_n=k_n\cdot m_{n-1}\cdot m_{n-2}\cdots\cdot m_{2}\cdot m_{1}$