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 (), 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 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
Przypisy
Kategoria:Algorytmy aproksymacyjne Kategoria:Algorytmy grafowe