Algorytmy zachłanne

Algorytm najbliższego sąsiada animacja (1) Algorytm najbliższego sąsiada – przykład algorytmu zachłannego
REKLAMA Thinking in Java. Edycja polska. Wydanie IV
149,00 zł
Czysty kod. Podręcznik dobrego programisty
69,00 zł
Skrypty powłoki systemu Linux. Zagadnienia zaawansowane. Wydanie II
−30%41,30 zł
English 4 IT. Praktyczny kurs języka angielskiego dla specjalistów IT i nie tylko
39,90 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. Matroid jest strukturą składającą się z określonego zbioru elementów oraz z rodziny podzbiorów tego zbioru, która spełnia pewne warunki:

  • Jeśli zbiór należy do rodziny, to wszystkie jego podzbiory również.
  • Jeśli dwa zbiory o różnej liczbie elementów należą do rodziny, to istnieje w tym większym zbiorze taki element, który po dodaniu do mniejszego zbioru utworzy zbiór również należący do rodziny.

Jeśli każdy z elementów ma przyporządkowaną pewną wagę, to matroid jest określany jako matroid ważony. 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: +1 Tak Nie
Liczba głosów: 3.

Dodano: 8 lipca 2017 14:53, ostatnia edycja: 26 stycznia 2019 17:47.

REKLAMA

Zobacz też

Wyznaczanie maksymalnego przepływu – problem obliczeniowy polegający na wyznaczeniu maksymalnego przepływu w sieci przepływowej.

Sieć przepływowa jest skierowanym grafem prostym. Każdy łuk (krawędź skierowana w grafie) ma swoją nieujemną wagę, która oznacza maksymalny dopuszczalny przepływ w tym łuku. Na potrzeby tego artykułu nazwijmy rzeczy przepływające przez sieć danymi. Jeden z wierzchołków sieci jest źródłem, z którego wypływają przesyłane dane. Inny z wierzchołków to ujście, do którego te dane wpływają. Zakłada się ponadto, że dla każdego z pozostałych wierzchołków istnieje ścieżka ze źródła do ujścia przechodząca przez ten wierzchołek.

Przepływem w sieci nazywamy przyporządkowanie każdemu łukowi pewnej wartości, która oznacza liczbę danych aktualnie przesyłanych przez ten łuk. Wartości te muszą spełniać następujące warunki:

  • Wartość przyporządkowana krawędzi musi być mniejsza lub równa jej wadze (warunek przepustowości).
  • Do każdego wierzchołka (poza źródłem i ujściem) musi wpływać tyle samo danych, ile z niego wypływa (warunek zachowania przepływu).

Omawiany problem polega na dobraniu takiego przepływu, aby liczba danych wypływających ze źródła (i zarazem wpływających do ujścia) była jak największa.

→ Czytaj całość

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ść
Algorytm najbliższego sąsiada (ang. nearest neighbour algorithm, w skrócie NN) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm wykorzystujący strategię zachłanną.
→ Czytaj całość
Polityka prywatnościKontakt