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ż

Powtarzalny algorytm najbliższego sąsiada (ang. repetitive nearest neighbour algorithm, w skrócie RNN) – algorytm służący do rozwiązywania problemu komiwojażera korzystający z algorytmu najbliższego sąsiada.

Algorytm polega na wielokrotnym wykonaniu algorytmu najbliższego sąsiada w taki sposób, aby każdy wierzchołek raz był wierzchołkiem początkowym. Następnie algorytm zwraca najlepsze spośród otrzymanych rozwiązań.

Dla grafu pełnego algorytm ma złożoność O(n3), gdzie n jest liczbą wierzchołków. W trakcie wykonywania algorytmu RNN n razy zostanie wykonany algorytm najbliższego sąsiada, który ma złożoność czasową O(n2).

Algorytm RNN nie daje gwarancji znalezienia rozwiązania optymalnego. W odróżnieniu od algorytmu najbliższego sąsiada daje jednak gwarancję, że zwróci rozwiązanie co najmniej tak dobre, jak n/2-1 innych rozwiązań (dowód i więcej informacji na ten temat znajduje się w pracy podanej w bibliografii).

→ Czytaj całość

Metoda przyrostowa – technika projektowania algorytmów polegająca na dodawaniu do rozwiązania kolejnych elementów z danych wejściowych. Przykładem algorytmu opartego na tej metodzie jest sortowanie przez wstawianie, gdzie kolejne elementy są wstawiane do posortowanej części tablicy.

Jest to metoda prosta, jednak sprawdza się tylko dla niektórych problemów obliczeniowych.

→ Czytaj całość

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.

→ Czytaj całość
Polityka prywatnościKontakt