Czy słyszałeś(-aś) kiedykolwiek o algorytmie "zachłannym" 🤔? Można sobie robić jajca, że jak algorytm może być "zachłanny" (pazerny, czy jak 😁?). Dowiedz się co oznacza w algorytmice termin "zachłanność", a przestanie to brzmieć bezsensownie 🧠.
CO ZACHŁANNOŚĆ MA WSPÓLNEGO Z ALGORYTMIKĄ?!
Zdaję sobie sprawę, że zetknięcie się z tym słowem może bawić i kojarzyć się bardziej z cechą charakteru, niż nauką (bo wystarczy, że niektórzy ludzie są zachłanni, a tu jeszcze algorytm 😆) 😏. To nie ma nic wspólnego ze znanym wszystkim skojarzeniem, więc wytłumaczę o co chodzi w tym kontekście 😊.
Zachłanność (ang. greediness) oznacza działanie algorytmu starającego się wybrać optymalne rozwiązanie w danej iteracji. Istnieją takie sytuacje, w których algorytm, aby mógł wyznaczyć rozwiązanie ostateczne, musi do niego dojść krok po kroku dysponując tym, co "widzi" w chwili obecnej (co jest "najlepsze" w aktualnej iteracji) 👀.
Przykładowo, żeby wyznaczyć najkrótszą ścieżkę w grafie ważonym (np. algorytmem Dijkstry), to algorytm bada te węzły, które są sąsiadami tego, na którym "stoi". Analizuje ich wagi krawędzi, oblicza odległości i na tej podstawie "wybiera" ten węzeł, któremu wydaje się, że jest "lokalnie optymalny" (zaraz przejdziemy do tego terminu) ✅.
Natomiast może okazać się w dalszej części badania grafu (np. po kilkunastu iteracjach), że wcześniej podjęta decyzja przez algorytm (w oparciu o tamte dane) nie była właściwa ❌! Bo na przykład odkryto inne węzły, które mają o wiele niższy koszt, niż zakładało się na początku. A wtedy nie mieliśmy takiej wiedzy 💡!
To, co Ci chcę pokazać to to, że zachłanność w algorytmice naraża nas na błędne rozwiązania ⛔. Algorytm zachłanny podejmuje decyzje na podstawie swojej obecnej wiedzy (w danej iteracji), tak jak ludzie 📖. W wyniku takiego funkcjonowania, może popełnić błąd i zwrócić ostateczne rozwiązanie, które nie będzie optymalne. Nazywamy to "zachłannością", gdyż ujmując to kolokwialnie, algorytm "bierze" to, co teraz wydaje mu się najlepsze 💡 - co oznacza, że nie każdy wybór w każdej iteracji może być dobry 😦!
 |
Zachłanność w algorytmice polega na podejmowaniu decyzji przez algorytm, które w danej iteracji (wśród dostępnych opcji) wydają mu się "najlepsze" na podstawie jego obecnej wiedzy (w postaci danych).
GLOBALNIE I LOKALNIE OPTYMALNE ROZWIĄZANIE
Teraz skupimy się na 2 ważnych terminach dotyczących zachłanności w algorytmice. Wyróżniamy 2 "rodzaje" rozwiązań optymalnych 👇:
- lokalnie optymalne rozwiązanie,
- globalnie optymalne rozwiązanie.
Lokalnie optymalne rozwiązanie (ang. local optimum) oznacza takie rozwiązanie, które jest optymalne w tzw. przestrzeni lokalnej. Przestrzeń lokalna, najprościej rzecz ujmując, to jest cały zakres tego, co "widzimy" w danej iteracji ℹ️.
Jak na przykład przebywasz w swoim pokoju i widzisz tylko swoje pomieszczenie, to to co widzisz w swoim pokoju, jest Twoją przestrzenią lokalną 😉. "Lokalnie" w kontekście algorytmów, należy interpretować jako "w danej iteracji" albo "w chwili obecnej" ℹ️. Czyli jak algorytm dobiera sobie węzeł o najniższym koszcie spośród dostępnych, to ten węzeł będzie lokalnie optymalny (co nie jest powiedziane, że jest optymalny na całym grafie ⚠️!).
Globalnie optymalne rozwiązanie (ang. global optimum) z kolei, jest rozwiązaniem "definitywnym", ostatecznym. Oznacza, że nie ma lepszego rozwiązania dla podanych danych (nieważne czego dotyczy problem ani algorytm) ✅. I jak się domyślasz, dotyczy przestrzeni globalnej 🌐.
Przywołując znowu przykład z pokojem, Twoją "przestrzenią globalną" będzie cały dom 🏡, czyli wiedza obejmuje wszystkie pomieszczenia, taras, działkę, garaż i wszystko inne 😁. W języku algorytmicznym, "globalnie" oznacza "ostatni przystanek", czyli moment przekazania wyznaczonego rozwiązania na wyjściu (np. z funkcji) ⭐. Gdy algorytm dojdzie do węzła docelowego i po przeanalizowaniu wszystkich kosztów okaże się, że ścieżka jest optymalna (tj. najkrótsza i najtańsza ze wszystkich), to ta ścieżka będzie globalnie optymalnym rozwiązaniem (nie ma lepszej w całym grafie) 😎.
KIEDY ALGORYTM JEST ZACHŁANNY?
Skoro wyjaśniliśmy sobie czym jest sama zachłanność w algorytmice oraz jak odróżniać optymalność rozwiązań w przestrzeniach lokalnej i globalnej, ostatnia ważna rzecz to dowiedzieć się, jak stwierdzić czy dany algorytm jest zachłanny 🤔.
Wystarczy mieć na względzie kluczową rzecz: algorytmy zachłanne (ang. greedy algorithms) podejmują decyzje w oparciu o wiedzę "tu i teraz", nie robiąc żadnych kroków wstecz ↩️. Jeżeli dany algorytm postępuje w taki sposób, to jest algorytmem zachłannym ℹ️!
Przykłady algorytmów zachłannych, to między innymi 👇:
- algorytm aproksymacyjny rozwiązujący problem komiwojażera,
- algorytm Dijkstry,
- algorytm aproksymacyjny rozwiązujący problem pokrycia zbioru.
To są algorytmy zachłanne, bo "zadowalają się" wynikami jakie wydają się optymalne w bieżącej sytuacji, a podejmowane decyzje "prowadzą" algorytm do wyznaczenia rozwiązania, które niekoniecznie może przyjąć optymalną formę 💥.
To wszystko co chciałem przekazać 😄.