Närmaste grannalgoritm
det här är stegen i algoritmen:
- initiera alla hörn som oönskade.
- Välj ett godtyckligt vertex, Ställ in det som det aktuella vertex u. Mark u som besökt.
- ta reda på den kortaste kanten som förbinder det aktuella vertex u och ett oönskat vertex v.
- Ställ in v som det aktuella vertex u. Mark v som besökt.
- om alla hörn i domänen besöks, avsluta sedan. Annars, gå till steg 3.
sekvensen för de besökta vertikalerna är utmatningen från algoritmen.,
den närmaste grannalgoritmen är lätt att implementera och utför snabbt, men den kan ibland sakna kortare rutter som lätt märks med mänsklig insikt på grund av sin ”giriga” natur. Som en allmän guide, om de sista etapperna av turnén är jämförbara i längd till de första etapperna, är turnén rimlig; om de är mycket större är det troligt att mycket bättre turer finns. En annan kontroll är att använda en algoritm som den lägre bundna algoritmen för att uppskatta om denna turné är tillräckligt bra.,
i värsta fall resulterar algoritmen i en turné som är mycket längre än den optimala turnén. För att vara exakt, för varje konstant r finns det en instans av resande säljare problem så att längden på turnén beräknas av närmaste granne algoritmen är större än r gånger längden på den optimala turnén. Dessutom finns det för varje antal städer ett uppdrag av avstånd mellan de städer för vilka närmaste granne heuristic producerar den unika värsta möjliga turnén., (Om algoritmen appliceras på varje vertex som startpunkt, kommer den bästa sökvägen att vara bättre än minst n / 2-1 andra turer, där n är antalet hörn.)
den närmaste grannalgoritmen kanske inte hittar någon genomförbar turné alls, även när en finns.