Algorytm najbliższego sąsiada

Ten artykuł dotyczy algorytmu aproksymacji do rozwiązania problemu komiwojażera . W przypadku innych zastosowań zobacz Najbliższy sąsiad .

Algorytm najbliższego sąsiada

Klasa	Algorytm aproksymacji
Struktura danych	Wykres
Wydajność w najgorszym przypadku	${\ Displaystyle \ Theta (N ^ {2})}$
Złożoność przestrzeni w najgorszym przypadku	${\ Displaystyle \ Theta (N)}$

Algorytm najbliższego sąsiada był jednym z pierwszych algorytmów stosowanych do przybliżonego rozwiązania problemu komiwojażera . W tym zadaniu sprzedawca zaczyna od losowego miasta i wielokrotnie odwiedza najbliższe miasto, aż wszystkie zostaną odwiedzone. Algorytm szybko daje krótką trasę, ale zwykle nie optymalną.

Algorytm

Oto kroki algorytmu:

1. Zainicjuj wszystkie wierzchołki jako nieodwiedzone.
2. Wybierz dowolny wierzchołek, ustaw go jako bieżący wierzchołek u . Oznacz Cię jako odwiedzonego.
3. Znajdź najkrótszą krawędź łączącą bieżący wierzchołek u i nieodwiedzony wierzchołek v .
4. Ustaw v jako bieżący wierzchołek u . Oznacz v jako odwiedzone.
5. Jeśli wszystkie wierzchołki w domenie zostaną odwiedzone, zakończ. W przeciwnym razie przejdź do kroku 3.

Sekwencja odwiedzonych wierzchołków jest wyjściem algorytmu.

Algorytm najbliższego sąsiada jest łatwy do zaimplementowania i szybko się wykonuje, ale czasami może pominąć krótsze trasy, które są łatwo zauważalne dzięki ludzkiemu wglądowi, ze względu na jego „chciwy” charakter. Ogólnie rzecz biorąc, jeśli kilka ostatnich etapów trasy jest porównywalnych pod względem długości z pierwszymi etapami, trasa jest rozsądna; jeśli są znacznie większe, prawdopodobnie istnieją znacznie lepsze wycieczki. Innym sprawdzeniem jest użycie algorytmu, takiego jak dolnej granicy , w celu oszacowania, czy ta trasa jest wystarczająco dobra.

W najgorszym przypadku algorytm daje trasę, która jest znacznie dłuższa niż trasa optymalna. Ściślej mówiąc, dla każdej stałej r istnieje taki przypadek problemu komiwojażera, że ​​długość trasy obliczona przez algorytm najbliższego sąsiada jest większa niż r razy długość trasy optymalnej. Ponadto dla każdej liczby miast istnieje przypisanie odległości między miastami, dla których heurystyka najbliższego sąsiedztwa tworzy unikalną najgorszą możliwą trasę. (Jeśli algorytm zostanie zastosowany do każdego wierzchołka jako wierzchołka początkowego, najlepsza znaleziona ścieżka będzie lepsza niż co najmniej N/2-1 innych tras, 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.

Notatki

• G. Gutin, A. Yeo i A. Zverovitch, Exponential Neighborhoods and Domination Analysis for the TSP, w The Traveling Salesman Problem and Its Variations, G. Gutin i AP Punnen (red.), Kluwer (2002) i Springer (2007) .
• G. Gutin, A. Yeo i A. Zverovich, Komiwojażer nie powinien być chciwy: analiza dominacji heurystyk typu chciwego dla TSP . Dyskretna matematyka stosowana 117 (2002), 81–86.
• J. Bang-Jensen, G. Gutin i A. Yeo, Kiedy algorytm zachłanny zawodzi . Optymalizacja dyskretna 1 (2004), 121–127.
• G. Bendall i F. Margot, Odporność na problemy kombinatoryczne typu chciwego , Discrete Optimization 3 (2006), 288–298.