Czy słyszeliście kiedykolwiek o algorytmie "zachłannym"? Ktoś może sobie robić heheszki, że jak algorytm może być zachłanny ("pazerny, czy co?" ;)). Dowiedzcie się co oznacza termin "zachłanność", a przestanie to brzmieć bezsensownie.
| Tweet |
CO ZACHŁANNOŚĆ MA WSPÓLNEGO Z ALGORYTMIKĄ?!
Trochę może to bawić czytelnika, bo wystarczy że niektórzy ludzie są zachłanni, a tu jeszcze algorytm :D. Nie czas na tego typu polemiki, więc wytłumaczę już teraz o co chodzi "na serio".
Zachłanność (ang. "greed") w tym przypadku 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 macie 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). Zapiszcie sobie ten termin, to jeden z kluczowych w algorytmice! Przypomnę dla porządku, że aproksymacja stosowana jest w przypadkach, kiedy 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). A propos, po angielsku to brzmi "greedy algorithm".
Obejdzie się bez kodów źródłowych, bo już oblecieliście parę przykładów, w których występuje zachłanność i możecie tego nie być świadomi. 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.