Algorytm najbliższego sąsiada

Algorytm najbliższego sąsiada (ang. nearest neighbour algorithm, NN) to algorytm zachłanny, który ma na celu rozwiązanie problemu komiwojażera. Jego zasada działania polega na odwiedzaniu, począwszy od wybranego wierzchołka, wierzchołka, który znajduje się najbliżej ostatnio odwiedzonego. Dla pełnego grafu z n wierzchołkami złożoność czasowa tego algorytmu wynosi O(n²).

Działanie

Algorytm funkcjonuje w następujący sposób:

Ustaw wybrany wierzchołek jako aktualny i oznacz go jako odwiedzony.
Znajdź spośród nieodwiedzonych wierzchołków ten, który jest połączony z aktualnym krawędzią o najmniejszej wadze.
Dołącz do rozwiązania krawędź łączącą aktualny wierzchołek z wierzchołkiem znalezionym w punkcie 2.
Oznacz wierzchołek z punktu 2 jako odwiedzony i ustaw go jako aktualny.
Jeśli pozostają jeszcze nieodwiedzone wierzchołki, wróć do punktu 2.
Na koniec 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 gwarantuje znalezienia optymalnego rozwiązania (problem komiwojażera to problem NP-trudny, co oznacza, że nie istnieje znany algorytm działający w czasie co najwyżej wielomianowym). Rozwiązania, które generuje ten algorytm, są średnio o około 25% gorsze od rozwiązań optymalnych.

Istnieją przypadki, w których algorytm najbliższego sąsiada może zwrócić najgorsze możliwe rozwiązanie. Wynik działania algorytmu może się różnić w zależności od wyboru wierzchołka startowego.

Ulepszenie

Istnieje ulepszona wersja tego algorytmu, znana jako powtarzalny algorytm najbliższego sąsiada (ang. repetitive nearest neighbour algorithm, RNN). Polega ona na uruchomieniu algorytmu najbliższego sąsiada dla każdego możliwego wierzchołka startowego i wybraniu najmniejszego z uzyskanych rozwiązań. Złożoność tego algorytmu to O(n³). Podobnie jak w przypadku NN, algorytm RNN nie gwarantuje optymalnego rozwiązania, ale rozwiązania, które generuje, są średnio o około 15% gorsze od optymalnych.