Algoritm för närmaste granne

Den här artikeln handlar om en approximationsalgoritm för att lösa problemet med resande säljare . För annan användning, se Närmaste granne .

Algoritm för närmaste granne

Klass	Approximationsalgoritm
Datastruktur	Graf
Prestanda i värsta fall	$\Theta (N^{2})$
Värsta tänkbara utrymmeskomplexitet	$\Theta (N)$

för närmaste granne var en av de första algoritmerna som användes för att ungefär lösa problemet med resandeförsäljare . I det problemet börjar säljaren på en slumpmässig stad och besöker flera gånger den närmaste staden tills alla har besökts. Algoritmen ger snabbt en kort tur, men vanligtvis inte den optimala.

Algoritm

Dessa är stegen i algoritmen:

1. Initiera alla hörn som obesökta.
2. Välj ett godtyckligt hörn, ställ in det som det aktuella hörnet u . Markera dig som besökt.
3. Ta reda på den kortaste kanten som förbinder den aktuella vertex u och en obesökt vertex v .
4. Ställ in v som aktuell vertex u . Markera v som besökt.
5. Om alla hörn i domänen besöks, avsluta sedan. Annars, gå till steg 3.

Sekvensen av de besökta hörnen är resultatet av algoritmen.

Algoritmen för närmaste granne är lätt att implementera och exekveras snabbt, men den kan ibland missa kortare vägar som lätt uppmärksammas med mänsklig insikt, på grund av dess "giriga" natur. Som en allmän guide, om de sista etapperna av turnén är jämförbara i längd med de första etapperna, då är turen rimlig; om de är mycket större, är det troligt att det finns mycket bättre turer. En annan kontroll är att använda en algoritm som den nedre gränsalgoritmen för att uppskatta om denna tur är tillräckligt bra.

I värsta fall resulterar algoritmen i en tur som är mycket längre än den optimala turen. För att vara exakt, för varje konstant r finns det en instans av resandeförsäljarproblemet så att längden på turen beräknad av närmaste grannealgoritm är större än r gånger längden på den optimala turen. Dessutom finns det för varje antal städer en tilldelning av avstånd mellan städerna där den närmaste grannheuristiken ger den unika sämsta möjliga turen. (Om algoritmen tillämpas på varje vertex som startpunkt, kommer den bästa sökvägen som hittas att vara bättre än åtminstone N/2-1 andra turer, där N är antalet hörn.)

Algoritmen för närmaste granne kanske inte hittar en genomförbar tur alls, även när en sådan finns.

Anteckningar

• G. Gutin, A. Yeo och A. Zverovitch, Exponential Neighborhoods and Domination Analysis for TSP, i The Travelling Salesman Problem and Its Variations, G. Gutin och AP Punnen (red.), Kluwer (2002) och Springer (2007) .
• G. Gutin, A. Yeo och A. Zverovich, Resande säljare bör inte vara girig: dominansanalys av heuristik av girig typ för TSP . Diskret tillämpad matematik 117 (2002), 81–86.
• J. Bang-Jensen, G. Gutin och A. Yeo, När den giriga algoritmen misslyckas . Diskret optimering 1 (2004), 121–127.
• G. Bendall och F. Margot, Greedy Type Resistance of Combinatorial Problems , Discrete Optimization 3 (2006), 288–298.