Kwalifikacja: INF.03 - Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych
Zawód: Technik informatyk , Technik programista
Kategorie: Algorytmy i podstawy informatyki
Na czym polega zasada działania algorytmów zachłannych?
Odpowiedzi
Źle. To opis rekurencji.
Dobrze. Algorytm zachłanny w każdym kroku wybiera lokalnie najlepszą opcję.
Źle. To opis metody „dziel i zwyciężaj”.
Źle. To opis przeszukiwania (np. siłowego), nie strategii zachłannej.
Informacja zwrotna
Algorytm zachłanny (greedy) buduje rozwiązanie krok po kroku, w każdym etapie wybierając opcję, która w danym momencie wydaje się najkorzystniejsza (lokalnie optymalna), bez cofania wcześniejszych decyzji. Jest prosty i szybki, a dla niektórych problemów daje rozwiązanie optymalne (np. wydawanie reszty pewnymi zestawami monet, algorytm Dijkstry, kod Huffmana). Bywa jednak, że lokalnie najlepszy wybór nie prowadzi do globalnie najlepszego wyniku. Dlatego zasada zachłanna to wybieranie najkorzystniejszej opcji na danym etapie.