Algorytm najbliższego sąsiada
![]() Przykładowe wykonanie algorytmu | |
Rodzaj | |
---|---|
Złożoność | |
Czasowa |
|
Niniejszy artykuł jest częścią cyklu teoria grafów.
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
Algorytm najbliższego sąsiada (ang. nearest neighbour algorithm, NN) – algorytm zachłanny służący do rozwiązywania problemu komiwojażera polegający na odwiedzaniu, począwszy od wybranego wierzchołka, wierzchołka znajdującego się najbliżej wierzchołka ostatnio odwiedzonego. Dla grafu pełnego o n wierzchołkach złożoność czasowa algorytmu wynosi[1].
Działanie[edytuj | edytuj kod]
Algorytm działa w następujący sposób[2]:
- Ustaw wybrany wierzchołek jako aktualny, oznacz go jako odwiedzony.
- Znajdź ten spośród nieodwiedzonych wierzchołków, który jest połączony z aktualnym krawędzią o najmniejszej wadze.
- Dołącz do rozwiązania krawędź łączącą aktualny wierzchołek z wierzchołkiem znalezionym w punkcie 2.
- Oznacz wierzchołek znaleziony w punkcie 2 jako odwiedzony i ustaw go jako aktualny.
- Jeśli pozostały jeszcze nieodwiedzone wierzchołki, przejdź do punktu 2.
- Dołącz do rozwiązania krawędź łączącą aktualny wierzchołek z wierzchołkiem wybranym w punkcie 1, aby zamknąć cykl.
Jakość otrzymanych rozwiązań[edytuj | edytuj kod]
Algorytm nie daje gwarancji znalezienia rozwiązania optymalnego (problem komiwojażera jest problemem NP-trudnym, zatem nie jest znany dokładny algorytm działający w czasie co najwyżej wielomianowym). Rozwiązania wyznaczone przez algorytm są średnio o około 25% gorsze od optymalnych[1].
Istnieją dane, dla których algorytm najbliższego sąsiada zwraca najgorsze możliwe rozwiązanie[3]. 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[edytuj | edytuj kod]
Istnieje ulepszona wersja tego algorytmu o nazwie powtarzalny algorytm najbliższego sąsiada (ang. repetitive nearest neighbour algorithm, RNN), 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[1].
Zobacz też[edytuj | edytuj kod]
Przypisy[edytuj | edytuj kod]
- ↑ a b c D.S. Johnson , L.A. McGeoch , The Traveling Salesman Problem: A Case Study in Local Optimization [dostęp 2016-10-12] (ang.).
- ↑ Algorytm najbliższego sąsiada – Encyklopedia Algorytmów (pol.). algorytmy.ency.pl. [dostęp 2016-10-12].
- ↑ G. Gutin , A. Yeo , A. Zverovich , Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP [dostęp 2016-10-12] (ang.).