Algorytmy zachłanne

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

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: +20 Tak Nie
Liczba głosów: 32.

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

REKLAMA

Zobacz też

Algorytm – przepis, zbiór poleceń, opis ciągu operacji prowadzących do rozwiązania konkretnego problemu. Algorytm możemy również rozumieć jako funkcję przekształcającą dane wejściowe w dane wyjściowe.

Algorytm musi być skończony, czyli jego zapis ma składać się ze skończonej liczby znaków. Musi również być poprawny, czyli dla wszystkich możliwych danych wejściowych powinien zwracać prawidłowy wynik (może być nim informacja o braku rozwiązania). Algorytm musi wykazywać również własność stopu – niezależnie od danych wejściowych obliczenia algorytmu powinny dochodzić do punktu końcowego, czyli po prostu kończyć się (nie mogą np. wpadać w nieskończoną iterację). Zapis algorytmu musi być precyzyjny, bez jakichkolwiek niejasności.

→ Czytaj całość

Przeszukiwanie w głąb (ang. depth-first search, w skrócie DFS) – jeden z dwóch podstawowych algorytmów przeszukiwania grafu. Polega na przechodzeniu zawsze do kolejnego nieodwiedzonego wierzchołka. Jeśli dany wierzchołek nie ma nieodwiedzonych sąsiadów, wracamy do poprzedniego wierzchołka i sprawdzamy jego sąsiadów. Mówiąc obrazowo, w algorytmie tym wchodzimy tak głęboko, jak to możliwe (przechodzimy dalej, dopóki się da).

Algorytm można zapisać w sposób rekurencyjny. Wywoływana rekurencyjnie procedura działa następująco: oznacz wierzchołek jako odwiedzony, a następnie wywołaj tę procedurę dla każdego sąsiada danego wierzchołka, jeśli nie został on wcześniej odwiedzony. Na początku wywołujemy procedurę dla wierzchołka początkowego.

→ Czytaj całość

Rekurencja (inaczej rekursja) – odwołanie się funkcji lub definicji do samej siebie. Mówiąc inaczej, podejście rekurencyjne polega na tym, że rozwiązanie problemu wyraża się za pomocą rozwiązania tego samego problemu dla mniejszych danych wejściowych. Stosowanie rekurencji jest charakterystyczne dla algorytmów projektowanych metodą dziel i zwyciężaj.

Typowym problemem, dla którego można zastosować rekurencję, jest obliczanie silni. Przypomnijmy, że silnia z n jest zdefiniowana jako n!=1×2×…×n. Funkcja ta może być równoważnie zapisana jako:

n!=(n−1)!×n, dla n>0,
n!=1, dla n=0.

W powyższym przykładzie górny wiersz jest ogólnym równaniem rekurencji, zaś dolny wiersz jest wartością brzegową. W języku C++ powyższa funkcja byłaby zapisana w poniższy sposób.

int silnia(int n)
{
    if (n > 0)
    {
        return n * silnia(n-1);
    }
    else
    {
        return 1;
    }
};

Przekształcenie postaci rekurencyjnej funkcji do postaci zwartej (tzn. takiej, która nie zawiera odwołania do samej siebie) jest określane jako rozwiązanie rekurencji. Metody rozwiązywania rekurencji są dostępne między innymi w książkach podanych w bibliografii.

Algorytmy stosujące rekurencję są zazwyczaj proste w implementacji. Jednocześnie wiążą się one z pewnymi problemami. Przy podejściu rekurencyjnym ta sama funkcja jest wywoływana wielokrotnie, co zużywa pamięć operacyjną (w skrajnych przypadkach może to spowodować przepełnienie stosu).

→ Czytaj całość
Polityka prywatnościKontakt