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: 4.
- 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ż
Dziel i zwyciężaj (ang. divide and conquer) – technika projektowania algorytmów polegająca na podejściu rekurencyjnym. W technice tej problem dzielony jest na mniejsze podproblemy, te podproblemy na jeszcze mniejsze podproblemy, aż dojdzie się do przypadków trywialnych (np. posortowanie jednoelementowej tablicy, obliczenie silni z 1).
Jeśli rozpatrywany problem wymaga podzielenia na podproblemy, jest on określany jako przypadek rekurencyjny. Jeśli mamy do czynienia z przypadkiem trywialnym, jest to przypadek bazowy. Tworząc algorytm wykorzystujący metodę dziel i zwyciężaj musimy ustalić:
- Jak rozwiązać przypadek bazowy (trywialny).
- Jak wyznaczyć rozwiązanie problemu, mając dostępne rozwiązania podproblemów.
Przykładem algorytmu opartego na tej metodzie jest sortowanie przez scalanie.
Algorytm Helda-Karpa (czasami określany jako algorytm Bellmana-Helda-Karpa) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm dokładny oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n22n) i złożoność pamięciową O(n2n). Jest to co prawda złożoność gorsza od wielomianowej, ale algorytm ten jest znacznie lepszy od algorytmu sprawdzającego wszystkie warianty (złożoność czasowa O(n!)).
Programowanie dynamiczne – technika projektowania algorytmów polegająca na rozwiązywaniu podproblemów i zapamiętywaniu ich wyników. W technice tej, podobnie jak w metodzie dziel i zwyciężaj, problem dzielony jest na mniejsze podproblemy. Wyniki rozwiązywania podproblemów są jednak zapisywane w tabeli, dzięki czemu w przypadku natrafienia na ten sam podproblem nie trzeba go ponownie rozwiązywać.
Wykorzystując programowanie dynamiczne można zastosować metodę zstępującą z zapamiętywaniem lub metodę wstępującą.
- Metoda zstępująca z zapamiętywaniem polega na rekurencyjnym wywoływaniu funkcji z zapamiętywaniem wyników. Metoda ta jest podobna do metody dziel i zwyciężaj – różni się od niej tym, że jeśli rozwiązanie danego problemu jest już w tabeli z wynikami, to należy je po prostu stamtąd odczytać.
- Metoda wstępująca polega na rozwiązywaniu wszystkich możliwych podproblemów, zaczynając od tych o najmniejszym rozmiarze. Wówczas w momencie rozwiązywania podproblemu na pewno są już dostępne rozwiązania jego podproblemów. W tym podejściu nie zużywa się pamięci na rekurencyjne wywołania funkcji. Może się jednak okazać, że część podproblemów została rozwiązana nadmiarowo (nie były one potrzebne do rozwiązania głównego problemu).