Algorytmy zachłanne

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

Architektura API. Projektowanie, używanie i rozwijanie systemów opartych na API
−35%44,85 zł
Algorytmy bez tajemnic
54,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. 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: +21 Tak Nie
Liczba głosów: 31.

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

REKLAMA

Zobacz też

Minimalne drzewo rozpinające (ang. minimum spanning tree, w skrócie MST), inaczej drzewo rozpinające o minimalnej wadze – drzewo łączące wszystkie wierzchołki pewnego grafu spójnego mające najmniejszą możliwą sumę wag krawędzi.

Jeśli graf ma v wierzchołków, to jego drzewo rozpinające zawsze będzie miało v-1 krawędzi. Jeśli ten graf ma e krawędzi, aby utworzyć drzewo rozpinające, trzeba usunąć z grafu e-v+1 krawędzi. Liczba ta jest określana jako liczba cyklomatryczna.

→ Czytaj całość

Algorytm Edmondsa-Karpa – algorytm wyszukiwania maksymalnego przepływu w sieci przepływowej. Jest to przypadek szczególny algorytmu Forda-Fulkersona.

W algorytmie Edmondsa-Karpa ścieżka powiększająca wyznaczana jest za pomocą przeszukiwania grafu wszerz. Dzięki temu w każdej iteracji algorytmu dołączana jest zawsze najkrótsza (pod względem liczby krawędzi) ścieżka powiększająca. W metodzie Forda-Fulkersona sposób wyznaczania ścieżki powiększającej jest dowolny.

→ Czytaj całość

Problem komiwojażera (ang. travelling salesman problem, w skrócie TSP) – problem obliczeniowy polegający na poszukiwaniu w grafie takiego cyklu, który zawiera wszystkie wierzchołki (każdy dokładnie raz) i ma jak najmniejszy koszt. Bardziej formalnie, problem komiwojażera polega na poszukiwaniu w grafie cyklu Hammiltona o najmniejszej wadze.

Problem ma liczne zastosowania w życiu codziennym. Najlepszym przykładem jest praca kuriera, który musi wyjechać z magazynu, zawieźć przesyłki w różne miejsca i wrócić do magazynu.

Nie jest znany efektywny (tj. działający w czasie co najwyżej wielomianowym) algorytm dający gwarancję znalezienia optymalnego rozwiązania problemu komiwojażera. Problem ten jest bowiem zaliczany do klasy problemów NP-trudnych. W wersji decyzyjnej (czy istnieje cykl o długości mniejszej od x) problem jest zaliczany do klasy problemów NP-zupełnych. W grafie pełnym mającym n wierzchołków liczba możliwych cykli Hammiltona wynosi aż (n-1)!/2. W praktyce sprawdzenie wszystkich możliwości jest zatem wykonalne tylko dla niewielkiej liczby wierzchołków.

→ Czytaj całość
Polityka prywatnościKontakt