Algorytmy. Ćwiczenia
34,90 zł
Projektowanie systemów rozproszonych. Wzorce i paradygmaty dla skalowalnych, niezawodnych usług
−30%27,93 zł
PHP 7. Algorytmy i struktury danych
59,00 zł
Java. Kompendium programisty. Wydanie X
179,00 zł
Opus magnum C++11. Programowanie w języku C++ (komplet)
149,00 zł
Uczenie maszynowe z użyciem Scikit-Learn i TensorFlow
89,00 zł

Powtarzalny algorytm najbliższego sąsiada

Info
Nazwa tego artykułu jest autorskim tłumaczeniem. Prawdopodobnie nie jest to nazwa oficjalnie używana w polskiej literaturze.
REKLAMA

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).

Bibliografia

  1. G. Gutin, A. Yeo, A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP (link) [dostęp: 21 listopada 2017].
Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 10 października 2016 18:21, ostatnia edycja: 21 listopada 2017 19:09.

REKLAMA

Zobacz też

Metoda z zastosowaniem przepływu blokującego – algorytm wyznaczający maksymalny przepływ w sieci przepływowej. W algorytmie tym przepływ zwiększany jest iteracyjnie, w każdej iteracji wyznaczony przepływ jest powiększany o przepływ blokujący w warstwowej sieci residualnej.

→ Czytaj całość

2-opt, algorytm 2-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Jest to szczególny przypadek algorytmu k-optymalnego.

Algorytm 2-opt nie służy do wyznaczania trasy, a jedynie do ulepszania jej. Samą trasę można wyznaczyć np. za pomocą algorytmu najbliższego sąsiada. Algorytm może być wykorzystany do ulepszenia algorytmu genetycznego – w ten sposób powstanie algorytm memetyczny.

→ Czytaj całość

Algorytm Edmondsa-Karpa – algorytm wyszukiwania maksymalnego przepływu w sieci przepływowej. Jest to przypadek szczególny algorytmu Forda-Fulkersona.

W algorytmie Edmondsa-Karpa ścieżka powiększająca wyznaczana jest za pomocą przeszukiwania grafu wszerz. Dzięki temu w każdej iteracji algorytmu dołączana jest zawsze najkrótsza (pod względem liczby krawędzi) ścieżka powiększająca. W metodzie Forda-Fulkersona sposób wyznaczania ścieżki powiększającej jest dowolny.

→ Czytaj całość
Polityka prywatnościKontakt