Legközelebbi szomszéd algoritmus
Ezek az algoritmus lépései:
- inicializálja az összes csúcsot látogatatlanként.
- válasszon ki egy tetszőleges csúcsot, állítsa be jelenlegi csúcsként u. jelölje meg az u-t látogatottnak.
- Ismerje meg a legrövidebb él, amely összeköti az aktuális csúcs u és egy nem látogatott vertex v.
- állítsa v, mint a jelenlegi vertex u.Mark v meglátogatott.
- ha a tartomány összes csúcsát meglátogatják, akkor fejezze be. Más, menj a 3. lépésre.
a meglátogatott csúcsok sorrendje az algoritmus kimenete.,
a legközelebbi szomszéd algoritmus könnyen végrehajtható, gyorsan végrehajtható, de néha rövidebb útvonalakat is kihagyhat, amelyeket emberi betekintéssel könnyen észrevehet, “kapzsi” jellege miatt. Általános útmutatóként, ha a túra utolsó néhány szakasza hosszúságban összehasonlítható az első szakaszokkal, akkor a túra ésszerű; ha sokkal nagyobbak, akkor valószínű, hogy sokkal jobb túrák léteznek. Egy másik ellenőrzés egy olyan algoritmus használata, mint például az alsó kötésű algoritmus, annak becslésére, hogy ez a túra elég jó-e.,
a legrosszabb esetben az algoritmus olyan túrát eredményez, amely sokkal hosszabb, mint az optimális túra. Pontosabban, minden állandó r esetében van egy példány az utazó ügynök problémájáról, hogy a legközelebbi szomszéd algoritmus által kiszámított túra hossza nagyobb, mint az optimális túra hosszának r-szerese. Sőt, minden egyes város esetében olyan távolságok vannak kijelölve a városok között, amelyekre a legközelebbi szomszéd heurisztikus a lehető legrosszabb túrát hozza létre., (Ha az algoritmust minden csúcson kiindulási csúcsként alkalmazzák, akkor a legjobb elérési út jobb lesz, mint legalább N/2-1 más túra, ahol N A csúcsok száma.)
a legközelebbi szomszéd algoritmus egyáltalán nem talál megvalósítható túrát, még akkor sem, ha létezik.