Algorytm najbliższego sąsiada

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Ten artykuł dotyczy algorytmu rozwiązującego problem komiwojażera. Zobacz też: algorytm k najbliższych sąsiadów.
Algorytm najbliższego sąsiada
Nearestneighbor.gif
Przykładowe wykonanie algorytmu
Rodzaj algorytm zachłanny
Złożoność
Czasowa O(n2)
Niniejszy artykuł jest częścią cyklu teoria grafów.




Najważniejsze pojęcia
graf
drzewo
podgraf
cykl
klika
stopień wierzchołka
stopień grafu
dopełnienie grafu
obwód grafu
pokrycie wierzchołkowe
liczba chromatyczna
indeks chromatyczny
izomorfizm grafów
homeomorfizm grafów


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


Algorytmy grafowe
A*
Bellmana-Forda
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
wszerz
w głąb
najbliższego sąsiada


Zagadnienia przedstawiane jako problemy grafowe
problem komiwojażera
problem chińskiego listonosza
problem marszrutyzacji
problem kojarzenia małżeństw


Inne zagadnienia
kod Graya
diagram Hassego
kod Prüfera


Algorytm najbliższego sąsiada (ang. nearest neighbour algorithm, NN) – algorytm zachłanny służący do rozwiązywania problemu komiwojażera polegający na odwiedzaniu, począwszy od wybranego wierzchołka, wierzchołka znajdującego się najbliżej wierzchołka ostatnio odwiedzonego. Dla grafu pełnego o n wierzchołkach złożoność czasowa algorytmu wynosi O(n2)[1].

Działanie[edytuj]

Algorytm działa w następujący sposób[2]:

  1. Ustaw wybrany wierzchołek jako aktualny, oznacz go jako odwiedzony.
  2. Znajdź ten spośród nieodwiedzonych wierzchołków, który jest połączony z aktualnym krawędzią o najmniejszej wadze.
  3. Dołącz do rozwiązania krawędź łączącą aktualny wierzchołek z wierzchołkiem znalezionym w punkcie 2.
  4. Oznacz wierzchołek znaleziony w punkcie 2 jako odwiedzony i ustaw go jako aktualny.
  5. Jeśli pozostały jeszcze nieodwiedzone wierzchołki, przejdź do punktu 2.
  6. Dołącz do rozwiązania krawędź łączącą aktualny wierzchołek z wierzchołkiem wybranym w punkcie 1, aby zamknąć cykl.

Jakość otrzymanych rozwiązań[edytuj]

Algorytm nie daje gwarancji znalezienia rozwiązania optymalnego (problem komiwojażera jest problemem NP-trudnym, zatem nie jest znany dokładny algorytm działający w czasie co najwyżej wielomianowym). Rozwiązania wyznaczone przez algorytm są średnio o około 25% gorsze od optymalnych[1].

Istnieją dane, dla których algorytm najbliższego sąsiada zwraca najgorsze możliwe rozwiązanie[3]. Wynik działania algorytmu może różnić się w zależności od wyboru wierzchołka, od którego rozpoczyna się wyznaczanie cyklu.

Zobacz też[edytuj]

Przypisy

  1. a b D.S.D. Johnson D.S.D., L.A.L. McGeoch L.A.L., The Traveling Salesman Problem: A Case Study in Local Optimization [dostęp 2016-10-12] (ang.).
  2. Algorytm najbliższego sąsiada – Encyklopedia Algorytmów (pol.). algorytmy.ency.pl. [dostęp 2016-10-12].
  3. G.G. Gutin G.G., A.A. Yeo A.A., A.A. Zverovich A.A., Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP [dostęp 2016-10-12] (ang.).