Algorytm najbliższego sąsiada

Działanie algorytmu

Algorytm rozpoczyna działanie od wybranego wierzchołka (nazwijmy go wierzchołkiem początkowym) i polega na kolejnym przechodzeniu do najbliższego nieodwiedzonego sąsiada ostatnio dodanego wierzchołka. W bardziej formalnym zapisie algorytm działa w następujący sposób:

1. Wierzchołek początkowy oznaczamy jako odwiedzony i ustawiamy jako aktualny.
2. Znajdujemy najkrótszą spośród krawędzi łączących aktualny wierzchołek z jeszcze nieodwiedzonymi wierzchołkami.
3. Dołączamy do rozwiązania krawędź znalezioną w punkcie 2.
4. Wierzchołek będący drugim końcem krawędzi znalezionej w punkcie 2 oznaczamy jako odwiedzony i ustawiamy jako aktualny.
5. Jeśli są jeszcze nieodwiedzone wierzchołki, przechodzimy do punktu 2.
6. Dołączamy krawędź łączącą ostatnio dodany wierzchołek z wierzchołkiem początkowym. Zamykamy w ten sposób cykl.

Złożoność i ocena jakości

Dla grafu pełnego algorytm ma złożoność czasową rzędu kwadratowego. Złożoność pamięciowa algorytmu jest bardzo niewielka (warto pamiętać jedynie, które wierzchołki zostały już odwiedzone).

Dla problemu komiwojażera nie jest znany wydajny (tj. działający w czasie co najwyżej wielomianowym) algorytm dający gwarancję znalezienia rozwiązania optymalnego. Algorytm najbliższego sąsiada również nie daje zatem gwarancji znalezienia najlepszego z możliwych rozwiązań. Według pracy The Traveling Salesman Problem: A Case Study in Local Optimization (link w bibliografii) rozwiązania znalezione przez ten algorytm są średnio o ok. 25% gorsze od optymalnych. Istnieją nawet takie przypadki, w których algorytm najbliższego sąsiada daje najgorsze możliwe rozwiązanie.

Można łatwo zauważyć, że rozwiązania uzyskane za pomocą algorytmu najbliższego sąsiada mogą różnić się od siebie w zależności od wyboru wierzchołka początkowego. Zaprezentowano to na obrazkach znajdujących się po prawej stronie artykułu. W pierwszym przypadku wierzchołkiem początkowym jest ten znajdujący się najbliżej środka, w drugim ten znajdujący się w lewym dolnym rogu.

Algorytm RNN

Modyfikacją algorytmu najbliższego sąsiada jest algorytm funkcjonujący w anglojęzycznej literaturze jako repetitive NN. Polega on na wykonaniu algorytmu najbliższego sąsiada dla każdego wierzchołka początkowego i wybraniu najlepszego z uzyskanych rozwiązań.

Bibliografia

1. Z.J. Czech, S. Deorowicz, P. Fabian, Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Gliwice, 2010.
2. D.S. Johnson, L.A. McGeoch, The Traveling Salesman Problem: A Case Study in Local Optimization (link) [dostęp: 27 września 2016].
3. G. Gutin, A. Yeo, A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP (link) [dostęp: 8 października 2016].