Algoritmen för närmaste granne i problemet med resande säljare

Algoritmen för närmaste granne  är en av de enklaste heuristiska algoritmerna för att lösa problemet med resande säljare . Tillhör kategorin "giriga" algoritmer .

Formulerad enligt följande:

Plan förbikopplingspunkter inkluderas sekventiellt i rutten, och varje nästa inkluderade punkt måste vara närmast den senast valda punkten bland alla andra som ännu inte ingår i rutten.

Algoritmen är lätt att implementera, snabb att exekvera, men, precis som andra "giriga" algoritmer, kan den producera suboptimala lösningar. Ett av de heuristiska kriterierna för att utvärdera en lösning är regeln: om vägen som färdades vid de sista stegen i algoritmen är jämförbar med vägen som färdades vid de inledande stegen, då kan den hittade rutten anses vara acceptabel, annars mer optimala lösningar finns förmodligen. Ett annat alternativ för att utvärdera lösningen är att använda den nedre gränsalgoritmen.

För ett valfritt antal städer som är större än tre, i resandeförsäljarproblemet, kan du välja ett sådant arrangemang av städer (värdet på avstånden mellan grafens hörn och indikeringen av det initiala hörnet) som den närmaste grannalgoritmen kommer att producera den sämsta lösningen. [ett]

Algoritm

Algoritmsteg:

1. Ställ in alla hörn som obesökta.
2. Välj en startpunkt v och markera den som besökt.
3. Välj det närmast obesökta intilliggande hörnet u till vertex v .
4. Ställ in u som aktuell vertex och markera som besökt.
5. Om alla hörn har besökts, avsluta då algoritmen. Annars går du tillbaka till steg 3.

Vid utgången kommer vi att ha en sekvens av hörn, en förmodat optimal lösning.

Anteckningar

1. ↑ G. Gutin, A. Yeo, A. Zverovich. Resande säljare bör inte vara girig: dominansanalys av heuristik av girig typ för TSP Arkiverad 29 juli 2007 på Wayback Machine // Discrete Applied Mathematics 117 (2002)

Länkar

• Algoritm för närmaste granne på Mathcad Calculation Server