Algorytm najbliższego sąsiada
są to kroki algorytmu:
- Zainicjalizuj wszystkie wierzchołki jako nieodstawione.
- Wybierz dowolny wierzchołek, ustaw go jako bieżący wierzchołek u. zaznacz u jako odwiedzony.
- Znajdź najkrótszą krawędź łączącą aktualny wierzchołek u i nieodwiedziony wierzchołek v.
- Ustaw v jako bieżący wierzchołek u. Oznacz V jako odwiedzony.
- jeśli wszystkie wierzchołki w domenie są odwiedzane, Zakończ. W przeciwnym razie przejdź do kroku 3.
ciąg odwiedzanych wierzchołków jest wyjściem algorytmu.,
algorytm najbliższego sąsiada jest łatwy do zaimplementowania i szybko wykonuje, ale czasami może przegapić krótsze trasy, które są łatwo zauważalne z ludzkim wglądem, ze względu na swoją „chciwą” naturę. Jako ogólny przewodnik, jeśli kilka ostatnich etapów wycieczki są porównywalne pod względem długości do pierwszych etapów, to wycieczka jest rozsądna; jeśli są one znacznie większe, to jest prawdopodobne, że istnieją znacznie lepsze wycieczki. Innym sprawdzeniem jest użycie algorytmu, takiego jak algorytm dolnej granicy, aby oszacować, czy ta trasa jest wystarczająco dobra.,
w najgorszym przypadku algorytm powoduje, że trasa jest znacznie dłuższa niż trasa optymalna. Aby być precyzyjnym, dla każdej stałej r istnieje przykład problemu podróżującego sprzedawcy taki, że długość trasy obliczona przez algorytm najbliższego sąsiada jest większa niż r razy długość trasy optymalnej. Co więcej, dla każdej liczby miast istnieje przypisanie odległości między miastami, dla których najbliższy sąsiad heurystyczne produkuje unikalną najgorszą możliwą wycieczkę., (Jeśli algorytm zostanie zastosowany na każdym wierzchołku jako wierzchołek początkowy, najlepsza znaleziona ścieżka będzie lepsza niż co najmniej N / 2-1 innych TUR, gdzie N to liczba wierzchołków.)
algorytm najbliższego sąsiada może w ogóle nie znaleźć wykonalnej trasy, nawet jeśli taka istnieje.