Nærmeste naboalgoritme - Nearest neighbour algorithm

Nærmeste naboalgoritme

Klasse	Tilnærmelsesalgoritme
Datastruktur	Kurve
Worst-case ydeevne	${\ displaystyle \ Theta (N ^ {2})}$
Værste tilfælde af kompleksitet i rummet	${\ displaystyle \ Theta (N)}$

Den nærmeste naboalgoritme var en af ​​de første algoritmer, der blev brugt til at løse problemet med den rejsende sælger . I dette problem starter sælgeren i en tilfældig by og besøger gentagne gange den nærmeste by, indtil alle er blevet besøgt. Algoritmen giver hurtigt en kort tur, men normalt ikke den optimale.

Algoritme

Dette er trinnene i algoritmen:

1. Initialiser alle hjørner som ubesøgte.
2. Vælg et vilkårligt toppunkt, indstil det som det aktuelle toppunkt u . Markér u som besøgt.
3. Find ud af den korteste kant, der forbinder det aktuelle toppunkt u og et ubesøgt toppunkt v .
4. Indstil v som det aktuelle toppunkt u . Marker v som besøgt.
5. Hvis alle hjørner i domænet er besøgt, skal du afslutte. Ellers, gå til trin 3.

Sekvensen af ​​de besøgte hjørner er output fra algoritmen.

Den nærmeste naboalgoritme er let at implementere og udføres hurtigt, men den kan undertiden gå glip af kortere ruter, som let bemærkes med menneskelig indsigt på grund af dens "grådige" natur. Som en generel guide, hvis turens sidste par faser er sammenlignelige i længde med de første faser, er turen rimelig; hvis de er meget større, er det sandsynligt, at der findes meget bedre ture. En anden kontrol er at bruge en algoritme som den nedre grænse algoritme til at estimere, om denne tur er god nok.

I værste fald resulterer algoritmen i en tur, der er meget længere end den optimale tur. For at være præcis er der for hver konstant r en forekomst af det rejsende sælgerproblem, således at turens længde beregnet af den nærmeste naboalgoritme er større end r gange længden af ​​den optimale tur. Desuden er der for hvert antal byer en tildeling af afstande mellem de byer, hvor den nærmeste naboheurist producerer den enestående værste mulige tur. (Hvis algoritmen anvendes på hvert toppunkt som startpunktet, vil den bedste vej, der findes, være bedre end mindst N / 2-1 andre ture, hvor N er antallet af hjørner.)

Den nærmeste naboalgoritme finder muligvis slet ikke en mulig tur, selv når en findes.

Bemærkninger

Referencer

• G. Gutin, A. Yeo og A. Zverovitch, eksponentielle kvarterer og dominansanalyse for TSP i The Travelling Salesman Problem and Its Variations, G. Gutin og AP Punnen (red.), Kluwer (2002) og Springer (2007) .
• G. Gutin, A. Yeo og A. Zverovich, Rejsende sælger bør ikke være grådig: dominansanalyse af grådige heuristikker til TSP . Diskret anvendt matematik 117 (2002), 81–86.
• J. Bang-Jensen, G. Gutin og A. Yeo, når den grådige algoritme mislykkes . Diskret optimering 1 (2004), 121–127.
• G. Bendall og F. Margot, Greedy Type Resistance of Combinatorial Problems , Discrete Optimization 3 (2006), 288-298.