Nærmeste nabo algoritme
Dette er de trinnene i algoritmen:
- Initialisere alle noder som unvisited.
- Velg en vilkårlig toppunkt, sette det som gjeldende vertex u. Mark u som besøkte.
- Finn ut den korteste kanten koble den nåværende vertex u og en ubenyttede vertex v.
- Angi v som gjeldende vertex u. Mark v som besøkte.
- Hvis alle hjørnene i domenet er besøkt, og deretter avslutte. Ellers går du til trinn 3.
Den rekkefølge som besøkte noder er resultatet av algoritmen.,
nærmeste nabo algoritmen er enkel å implementere og kjører fort, men det kan noen ganger gå glipp av kortere ruter som er lett å merke med menneskelig innsikt, på grunn av sin «grådige» natur. Som en generell veiledning, hvis de siste etappene i tour er sammenlignbare i lengden til de første stadiene, så turen er rimelig; hvis de er mye større, da det er sannsynlig at mye bedre turer eksisterer. En annen se på, er å bruke en algoritme som nedre grense algoritme for å beregne om denne turen er god nok.,
I verste fall, algoritmen resulterer i en tur som er mye lenger enn den optimale turen. For å være nøyaktig, for hver konstant r det er en forekomst av traveling salesman problemet slik at lengden på turen er beregnet på grunnlag av de nærmeste nabo algoritmen er større enn r ganger lengden av den optimale turen. Videre, for hver rekke byer det er et oppdrag av avstander mellom byer som nærmeste nabo heuristisk produserer unike verste mulig tur., (Hvis algoritmen er brukt på hver toppunktet som starter toppunkt, den beste veien funnet, vil være bedre enn minst N/2-1 andre turer, der N er antall noder.)
nærmeste nabo algoritmen kan ikke finne en mulig tur på alle, selv når det finnes.