Algorytmy zachłanne

Algorytm najbliższego sąsiada animacja (1) Algorytm najbliższego sąsiada – przykład algorytmu zachłannego
REKLAMA

English 4 IT. Praktyczny kurs języka angielskiego dla specjalistów IT i nie tylko
−40%29,94 zł
Algorytmy, struktury danych i techniki programowania. Wydanie VI
−40%35,40 zł

Algorytmy zachłanne (ang. greedy algorithms) – algorytmy podejmujące w każdym kroku taką decyzję, która w danej chwili wydaje się najkorzystniejsza. Inaczej mówiąc, algorytmy zachłanne dokonują zawsze wyborów lokalnie optymalnych licząc, że doprowadzi to do znalezienia rozwiązania globalnie optymalnego. W ogólnym przypadku algorytmy zachłanne nie zawsze znajdują rozwiązanie optymalne. Są one zatem podzbiorem algorytmów heurystycznych. Jednocześnie są to algorytmy deterministyczne – nie ma w nich losowości.

Bardzo prostym przykładem algorytmu zachłannego może być szukanie najwyższego punktu na określonym obszarze poprzez przesuwanie się zawsze w kierunku największego nachylenia (nigdy się nie cofając ani nie rozpatrując kilku wariantów drogi). Jak widać, w ten sposób prawdopodobnie dojdziemy do wierzchołka położonego najbliżej od punktu początkowego, który niekoniecznie będzie najwyższym.

Przykłady algorytmów dokładnych

Choć generalnie algorytmy zachłanne nie zawsze znajdują rozwiązanie optymalne, to istnieją takie problemy obliczeniowe, dla których algorytmy te dają gwarancję znalezienia rozwiązania optymalnego. Przykładami takich algorytmów są:

Ciekawym przypadkiem jest problem wydawania reszty, gdzie algorytm zachłanny w zależności od zbioru nominałów daje gwarancję znalezienia rozwiązania optymalnego albo nie.

Przykłady algorytmów niedokładnych

Algorytmy zachłanne są również wykorzystywane tam, gdzie nie dają gwarancji znalezienia rozwiązania optymalnego. Przykładami takich algorytmów są algorytmy rozwiązujące problem komiwojażera:

Własności problemów

Aby algorytm zachłanny zawsze zwracał rozwiązanie optymalne, problem powinien mieć dwie własności:

  • Własność optymalnej podstruktury – własność oznaczająca, że optymalne rozwiązanie problemu jest funkcją optymalnych rozwiązań podproblemów (czyli znając optymalne rozwiązania podproblemów można efektywnie wyznaczyć rozwiązanie problemu). Własność ta jest wspólna dla metody zachłannej i dla programowania dynamicznego.
  • Własność wyboru zachłannego – własność oznaczająca, że za pomocą lokalnie optymalnych wyborów można znaleźć rozwiązanie globalnie optymalne. Mówiąc inaczej: wystarczy rozwiązać tylko ten podproblem, który można ocenić jako najbardziej obiecujący.

Matroidy a strategia zachłanna

W ocenianiu, czy dany problem można rozwiązać z wykorzystaniem metody zachłannej, przydatna jest teoria związana z matroidami. Jeśli problem obliczeniowy można przedstawić jako poszukiwanie podzbioru o największej wadze w matroidzie ważonym, to problem ten można rozwiązać stosując metodę zachłanną (algorytm zachłanny będzie zwracał rozwiązanie optymalne).

Bibliografia

  • T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301169114.
Ocena: +13 Tak Nie
Liczba głosów: 19.

Dodano: 8 lipca 2017 14:53, ostatnia edycja: 24 kwietnia 2020 19:17.

REKLAMA

Zobacz też

Dziel i zwyciężaj (ang. divide and conquer) – technika projektowania algorytmów polegająca na podejściu rekurencyjnym. W technice tej problem dzielony jest na mniejsze podproblemy, te podproblemy na jeszcze mniejsze podproblemy, aż dojdzie się do przypadków trywialnych (np. posortowanie jednoelementowej tablicy, obliczenie silni z 1).

Jeśli rozpatrywany problem wymaga podzielenia na podproblemy, jest on określany jako przypadek rekurencyjny. Jeśli mamy do czynienia z przypadkiem trywialnym, jest to przypadek bazowy. Tworząc algorytm wykorzystujący metodę dziel i zwyciężaj musimy ustalić:

  • Jak rozwiązać przypadek bazowy (trywialny).
  • Jak wyznaczyć rozwiązanie problemu, mając dostępne rozwiązania podproblemów.

Przykładem algorytmu opartego na tej metodzie jest sortowanie przez scalanie.

→ Czytaj całość

Algorytm heurystyczny, heurystyka – algorytm niedający (w ogólnym przypadku) gwarancji znalezienia rozwiązania optymalnego, umożliwiający jednak znalezienie rozwiązania dość dobrego w rozsądnym czasie. Algorytmy tego typu używane są w takich problemach obliczeniowych, gdzie znalezienie rozwiązania optymalnego ma zbyt dużą złożoność obliczeniową (w szczególności są to problemy NP-trudne) lub w ogóle nie jest możliwe. Metody heurystyczne zaliczają się do sztucznej inteligencji.

Pojęcie algorytmów heurystycznych jest bardzo szerokie, dotyczy ono różnych technik projektowania algorytmów. Wiele heurystyk wykorzystuje losowość, inne zaś są deterministyczne (wówczas dla takich samych danych wejściowych algorytm zawsze zwróci ten sam wynik).

Ogólny algorytm heurystyczny (opisujący samą ideę poszukiwań) bywa określany w literaturze jako metaheurystyka. Zgodnie z tym nazewnictwem, metaheurystyką jest np. algorytm zachłanny (jako ogólna idea), zaś heurystyką jest np. algorytm najbliższego sąsiada (jako zastosowanie idei algorytmu zachłannego do konkretnego problemu).

Przykładowe techniki konstruowania algorytmów heurystycznych to:

→ Czytaj całość
Algorytm najmniejszej krawędzi – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm wykorzystujący strategię zachłanną, jednak w inny sposób, niż algorytm najbliższego sąsiada. W anglojęzycznej literaturze algorytm jest najczęściej określany po prostu jako greedy algorithm (algorytm zachłanny), w skrócie GR.
→ Czytaj całość
Polityka prywatnościKontakt