Algorytm najbliższego sąsiada: Różnice pomiędzy wersjami

Istnieje ulepszona wersja tego algorytmu o nazwie ''powtarzalny algorytm najbliższego sąsiada'' (RNN{{ang.|repetitive nearest neighbour algorithm, NN}}), 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 <math>O(n^3)</math>. 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<ref name="tsp1" />.