Algorytm najbliższego sąsiada

Algorytm najbliższego sąsiada

Przykładowe wykonanie algorytmu
Rodzaj	algorytm zachłanny
Złożoność
Czasowa	$O(n^{2})$

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 więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... 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(n^{2})$.

Działanie

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

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ń

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.

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

Ulepszenie

Istnieje ulepszona wersja tego algorytmu o nazwie powtarzalny algorytm najbliższego sąsiada (ang. repetitive nearest neighbour algorithm, RNN), która polega na uruchomieniu algorytmu najbliższego sąsiada dla każdego możliwego wierzchołka startowego i wybraniu najmniejszego z rozwiązań. Złożoność takiego algorytmu to $O(n^{3})$. I ten algorytm nie daje gwarancji znalezienia optymalnego rozwiązania, ale rozwiązania wyznaczone przez algorytm RNN są średnio o około 15% gorsze od optymalnych.

Zobacz też

• Cykl Hamiltona