Algorytm najbliższego sąsiada

Algorytm najbliższego sąsiada animacja (1) Przykładowe wykonanie algorytmu
Algorytm najbliższego sąsiada animacja 2 (2) Przykładowe wykonanie algorytmu dla innego wierzchołka początkowego
Punkty w jednej linii (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
Algorytm najbliższego sąsiada (ang. nearest neighbour algorithm, w skrócie NN) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm wykorzystujący strategię zachłanną.

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:

  1. Wierzchołek początkowy oznaczamy jako odwiedzony i ustawiamy jako aktualny.
  2. Znajdujemy najkrótszą spośród krawędzi łączących aktualny wierzchołek z jeszcze nieodwiedzonymi wierzchołkami.
  3. Dołączamy do rozwiązania krawędź znalezioną w punkcie 2.
  4. Wierzchołek będący drugim końcem krawędzi znalezionej w punkcie 2 oznaczamy jako odwiedzony i ustawiamy jako aktualny.
  5. Jeśli są jeszcze nieodwiedzone wierzchołki, przechodzimy do punktu 2.
  6. 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

Ocena: +1 Tak Nie
Liczba głosów: 1.

Dodano: 26 września 2016 17:25, ostatnia edycja: 30 stycznia 2019 13:16.

REKLAMA

Zobacz też

Algorytm Dijkstry – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. Algorytm wymaga, aby wagi krawędzi grafu nie były ujemne. Autorem algorytmu jest holenderski naukowiec Edsger Dijkstra.

Algorytm realizuje podejście zachłanne. W każdej iteracji wybierany jest ten spośród nieodwiedzonych wierzchołków, do którego można dotrzeć najmniejszym kosztem. Po wyznaczeniu ścieżki do konkretnego wierzchołka nie zostanie ona zmodyfikowana w trakcie wykonywania dalszej części algorytmu.

→ Czytaj całość

Algorytmy zachłanne (ang. greedy algorithms) – algorytmy podejmujące w każdym kroku taką decyzję, która w danej chwili wydaje się najkorzystniejsza. Inaczej mówiąc, algorytmy zachłanne dokonują zawsze wyborów lokalnie optymalnych licząc, że doprowadzi to do znalezienia rozwiązania globalnie optymalnego. W ogólnym przypadku algorytmy zachłanne nie zawsze znajdują rozwiązanie optymalne. Są one zatem podzbiorem algorytmów heurystycznych. Jednocześnie są to algorytmy deterministyczne – nie ma w nich losowości.

Bardzo prostym przykładem algorytmu zachłannego może być szukanie najwyższego punktu na określonym obszarze poprzez przesuwanie się zawsze w kierunku największego nachylenia (nigdy się nie cofając ani nie rozpatrując kilku wariantów drogi). Jak widać, w ten sposób prawdopodobnie dojdziemy do wierzchołka położonego najbliżej od punktu początkowego, który niekoniecznie będzie najwyższym.

→ Czytaj całość

K-opt, algorytm k-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Algorytm ten nie służy do samego wyznaczania trasy, a jedynie do ulepszania jej. Najprostszą wersją tego algorytmu jest algorytm 2-optymalny.

→ Czytaj całość
Polityka prywatnościKontakt