Czy słyszałeś(-aś) kiedykolwiek o algorytmie "zachłannym"? Ktoś może sobie robić heheszki, że jak algorytm może być zachłanny ("pazerny, czy co?" 😁). Dowiedz się co oznacza termin "zachłanność", a przestanie to brzmieć bezsensownie 🧠.
CO ZACHŁANNOŚĆ MA WSPÓLNEGO Z ALGORYTMIKĄ?!
Trochę może to bawić, bo wystarczy, że niektórzy ludzie są zachłanni, a tu jeszcze algorytm 😆. Nie czas na tego typu polemiki, więc wytłumaczę już teraz o co chodzi "na serio".
Zachłanność (ang. greediness) oznacza działanie algorytmu starającego się wybrać optymalne rozwiązanie w danej iteracji. Jeszcze piękniej jest określić to "lokalnie optymalnym rozwiązaniem". "Lokalnie" w tym kontekście masz rozumieć jako "w danej iteracji" albo "w chwili obecnej" ℹ️. Są takie algorytmy (zwłaszcza te postępujące zgodnie z techniką "dziel i rządź"), które aby znaleźć rozwiązanie ostateczne ("rozwiązanie optymalne globalnie"), muszą do niego dojść krok po kroku znajdując rozwiązanie lokalne (najlepsze w aktualnej iteracji 💯). Nazywamy to "zachłannością", gdyż ujmując to kolokwialnie, algorytm "bierze" to, co teraz wydaje się najlepsze 💡.
SKĄD MAM WIEDZIEĆ KIEDY ALGORYTM JEST "ZACHŁANNY"?
Wystarczy jedno spostrzeżenie: zachłanność pojawia się głównie w algorytmach aproksymacyjnych, czyli uzyskujących rozwiązanie przybliżone uzyskane przy pomocy metodyki poszukiwania rozwiązań zwaną "heurystyką" (algorytmy zachłanne są jednym z rodzajów algorytmów aproksymacyjnych) ❗. Zapisz sobie ten termin, to jeden z kluczowych w algorytmice 🫵! Przypomnę dla porządku, że aproksymacja stosowana jest w przypadkach, gdy algorytm rozwiązujący problem w sposób dokładny, posiada zbyt mocno rosnącą złożoność obliczeniową (jest tzw. "problemem NP-zupełnym"), a konkretniej, jest ona wykładnicza i której nie można zastosować w praktyce dla dużych zbiorów danych (np. problem wędrującego komiwojażera). Kiedy algorytm przechowuje wyniki swoich ustaleń "na uboczu" i sugeruje się nimi podczas dalszych iteracji, to też jest "zachłanny" (programowanie dynamiczne stosuje takie podejście). Określamy taki algorytm po angielsku "greedy algorithm" ℹ️.
Obejdzie się bez kodów źródłowych, bo już było parę przykładów, w których występuje zachłanność i możesz tego nie być świadomy(-a) 👀. Był problem wędrującego komiwojażera (jako rozwiązanie aproksymacyjne) i algorytm Dijkstry - to są przykłady algorytmów zachłannych, bo "zadowalają się" wynikami jakie wydają się optymalne w bieżącej sytuacji, a algorytm jeszcze nie dotarł do rozwiązania globalnego 🌐.