Algorytm najbliższego sąsiada
(3) Przykład grafu, dla którego algorytm najbliższego sąsiada zwróci najgorsze możliwe rozwiązanie. Jeśli B będzie wierzchołkiem początkowym, to algorytm zwróci cykl B-C-A-D-B o długości 16. Tymczasem pozostałe rozwiązania (B-A-C-D-B i B-C-D-A-B) mają długość 12
Działanie algorytmu
Algorytm rozpoczyna działanie od wybranego wierzchołka (nazwijmy go wierzchołkiem początkowym) i polega na kolejnym przechodzeniu do najbliższego nieodwiedzonego sąsiada ostatnio dodanego wierzchołka. W bardziej formalnym zapisie algorytm działa w następujący sposób:
- Wierzchołek początkowy oznaczamy jako odwiedzony i ustawiamy jako aktualny.
- Znajdujemy najkrótszą spośród krawędzi łączących aktualny wierzchołek z jeszcze nieodwiedzonymi wierzchołkami.
- Dołączamy do rozwiązania krawędź znalezioną w punkcie 2.
- Wierzchołek będący drugim końcem krawędzi znalezionej w punkcie 2 oznaczamy jako odwiedzony i ustawiamy jako aktualny.
- Jeśli są jeszcze nieodwiedzone wierzchołki, przechodzimy do punktu 2.
- Dołączamy krawędź łączącą ostatnio dodany wierzchołek z wierzchołkiem początkowym. Zamykamy w ten sposób cykl.
Złożoność i ocena jakości
Dla grafu pełnego algorytm ma złożoność czasową rzędu kwadratowego. Złożoność pamięciowa algorytmu jest bardzo niewielka (warto pamiętać jedynie, które wierzchołki zostały już odwiedzone).
Dla problemu komiwojażera nie jest znany wydajny (tj. działający w czasie co najwyżej wielomianowym) algorytm dający gwarancję znalezienia rozwiązania optymalnego. Algorytm najbliższego sąsiada również nie daje zatem gwarancji znalezienia najlepszego z możliwych rozwiązań. Według pracy [2] rozwiązania znalezione przez ten algorytm są średnio o ok. 25% gorsze od optymalnych. Istnieją nawet takie przypadki, w których algorytm najbliższego sąsiada daje najgorsze możliwe rozwiązanie – przykład takiej sytuacji przedstawiono na ilustracji (3).
Można łatwo zauważyć, że rozwiązania uzyskane za pomocą algorytmu najbliższego sąsiada mogą różnić się od siebie w zależności od wyboru wierzchołka początkowego. Zaprezentowano to w animacjach (1) i (2). W pierwszym przypadku wierzchołkiem początkowym jest ten znajdujący się najbliżej środka, w drugim ten znajdujący się w lewym dolnym rogu.
Algorytm RNN
Modyfikacją algorytmu najbliższego sąsiada jest algorytm funkcjonujący w anglojęzycznej literaturze jako repetitive NN. Polega on na wykonaniu algorytmu najbliższego sąsiada dla każdego wierzchołka początkowego i wybraniu najlepszego z uzyskanych rozwiązań.
Bibliografia
- Z.J. Czech, S. Deorowicz, P. Fabian, Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Gliwice, 2010, ISBN 9788373356689.
- D.S. Johnson, L.A. McGeoch, The Traveling Salesman Problem: A Case Study in Local Optimization, 1995 [Dostęp 2019-01-26].
- G. Gutin, A. Yeo, A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP, Discrete Applied Mathematics, Volume 117, Issues 1–3, 2002, s. 81-86, DOI: 10.1016/S0166-218X(01)00195-0.
Liczba głosów: 1.
- 2-opt
- Algorytm Helda-Karpa
- Algorytm najbliższego sąsiada
- Algorytm najmniejszej krawędzi
- K-opt
- Powtarzalny algorytm najbliższego sąsiada
Dodano: 26 września 2016 17:25, ostatnia edycja: 30 stycznia 2019 13:16.
Zobacz też
Sortowanie – zagadnienie polegające na uporządkowaniu elementów zbioru rosnąco lub malejąco według pewnego klucza. Zagadnienie to, ze względu na częstość występowania, jest bardzo istotne dla informatyki. Istnieje wiele różnych algorytmów realizujących sortowanie.
Algorytm Kruskala – algorytm wyznaczający minimalne drzewo rozpinające. Algorytm ten wykorzystuje strategię zachłanną, zawsze zwraca rozwiązanie optymalne.
Rekurencja (inaczej rekursja) – odwołanie się funkcji lub definicji do samej siebie. Mówiąc inaczej, podejście rekurencyjne polega na tym, że rozwiązanie problemu wyraża się za pomocą rozwiązania tego samego problemu dla mniejszych danych wejściowych. Stosowanie rekurencji jest charakterystyczne dla algorytmów projektowanych metodą dziel i zwyciężaj.
Typowym problemem, dla którego można zastosować rekurencję, jest obliczanie silni. Przypomnijmy, że silnia z n jest zdefiniowana jako n!=1×2×…×n. Funkcja ta może być równoważnie zapisana jako:
n!=(n−1)!×n, dla n>0,
n!=1, dla n=0.
W powyższym przykładzie górny wiersz jest ogólnym równaniem rekurencji, zaś dolny wiersz jest wartością brzegową. W języku C++ powyższa funkcja byłaby zapisana w poniższy sposób.
int silnia(int n)
{
if (n > 0)
{
return n * silnia(n-1);
}
else
{
return 1;
}
};
Przekształcenie postaci rekurencyjnej funkcji do postaci zwartej (tzn. takiej, która nie zawiera odwołania do samej siebie) jest określane jako rozwiązanie rekurencji. Metody rozwiązywania rekurencji są dostępne między innymi w książkach podanych w bibliografii.
Algorytmy stosujące rekurencję są zazwyczaj proste w implementacji. Jednocześnie wiążą się one z pewnymi problemami. Przy podejściu rekurencyjnym ta sama funkcja jest wywoływana wielokrotnie, co zużywa pamięć operacyjną (w skrajnych przypadkach może to spowodować przepełnienie stosu).