Algorytm najbliższego sąsiada: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m kat. |
Pozdrawiam (dyskusja | edycje) Znaczna rozbudowa |
||
Linia 1:
{{Inne znaczenia|
{{Algorytm infobox
▲{{Inne znaczenia|grafów|[[K-najbliższych sąsiadów|algorytm 1nn (wersja knn)]]}}
|grafika = Nearestneighbor.gif
|wielkość grafika =
|opis = Przykładowe wykonanie algorytmu
|rodzaj = [[algorytm zachłanny]]
|struktura =
|czas = O(n<sup>2</sup>)
|pamiec =
}}
{{Teoria grafów}}
'''Algorytm najbliższego sąsiada''' ({{ang.|nearest neighbour algorithm, NN}}) – [[algorytm zachłanny]] służący do rozwiązywania [[problem komiwojażera|problemu komiwojażera]] polegający na odwiedzaniu, począwszy od wybranego [[Wierzchołek (teoria grafów)|wierzchołka]], wierzchołka znajdującego się najbliżej wierzchołka ostatnio odwiedzonego. Dla [[graf pełny|grafu pełnego]] złożoność czasowa algorytmu wynosi O(n<sup>2</sup>)<ref name="tsp1">{{Cytuj | autor = D.S. Johnson, L.A. McGeoch | tytuł = The Traveling Salesman Problem: A Case Study in Local Optimization | url = https://www.cs.ubc.ca/~hutter/previous-earg/EmpAlgReadingGroup/TSP-JohMcg97.pdf | język = en | data dostępu = 2016-10-12}}</ref>.
== Działanie ==
Algorytm działa w następujący sposób<ref>{{Cytuj stronę | url = http://algorytmy.ency.pl/artykul/algorytm_najblizszego_sasiada | tytuł = Algorytm najbliższego sąsiada – Encyklopedia Algorytmów | autor = | opublikowany = algorytmy.ency.pl | praca = | data = | język = pl | data dostępu = 2016-10-12}}</ref>:
# Ustaw wybrany wierzchołek jako aktualny, oznacz go jako odwiedzony.
# Znajdź ten spośród nieodwiedzonych wierzchołków, który jest połączony z aktualnym krawędzią o najmniejszej wadze.
# Dołącz do rozwiązania krawędź łączącą aktualny wierzchołek z wierzchołkiem znalezionym w punkcie 2.
# Oznacz wierzchołek znaleziony w punkcie 2 jako odwiedzony i ustaw go jako aktualny.
# Jeśli pozostały jeszcze nieodwiedzone wierzchołki, przejdź do punktu 2.
# Dołącz do rozwiązania krawędź łączącą aktualny wierzchołek z wierzchołkiem wybranym w punkcie 1, aby zamknąć cykl.
== Jakość otrzymanych rozwiązań ==
Algorytm nie daje gwarancji znalezienia rozwiązania optymalnego (problem komiwojażera jest problemem [[Problem NP-trudny|NP-trudnym]], zatem nie jest znany dokładny algorytm działający w czasie co najwyżej wielomianowym). Rozwiązania wyznaczone przez algorytm są średnio o około 25% gorsze od optymalnych<ref name="tsp1" />.
Istnieją dane, dla których algorytm najbliższego sąsiada zwraca najgorsze możliwe rozwiązanie<ref>{{Cytuj | autor = G. Gutin, A. Yeo, A. Zverovich | tytuł = Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP | url = http://www.sciencedirect.com/science/article/pii/S0166218X01001950 | język = en | data dostępu = 2016-10-12}}</ref>. Wynik działania algorytmu może różnić się w zależności od wyboru wierzchołka, od którego rozpoczyna się wyznaczanie cyklu.
== Zobacz też ==
* [[
{{Przypisy}}
[[Kategoria:Algorytmy grafowe|
| |||