Nærmeste naboalgoritme
Dette er trinnene i algoritmen:
- Initialiser alle hjørner som ikke-besøgt.
- Vælg et vilkårligt toppunkt, indstil det som det aktuelle toppunkt u. Marker u som besøgt.
- Find ud af den korteste kant, der forbinder det aktuelle Verte. u og et ikke-besøgt Verte.v.
- Indstil v som det aktuelle Verte. u. Mark v som besøgt.
- 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 udgangen af algoritmen.,
den nærmeste naboalgoritme er let at implementere og udfører hurtigt, men den kan undertiden gå glip af kortere ruter, der let bemærkes med menneskelig indsigt på grund af dens “grådige” natur. Som en generel vejledning, hvis de sidste par faser af turen er sammenlignelige i længden til de første faser, så er turen rimelig; hvis de er meget større, så 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, for hver konstant r der er en instans af traveling salesman problem, sådan at længden af turen beregnes ved at nærmeste nabo algoritmen 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, som den nærmeste nabo heuristiske producerer den unikke værst mulige tur., (Hvis algoritmen anvendes på hvert toppunkt som start toppunkt, den bedste sti fundet vil være bedre end mindst n/2-1 andre ture, hvor N er antallet af knudepunkter.)
den nærmeste nabo algoritme kan ikke finde en mulig tour på alle, selv når en findes.