Lähin naapuri-algoritmi,
Nämä ovat vaiheet algoritmi:
- Alustaa kaikki pisteet kuin avaamaton.
- valitse mielivaltainen huippupiste, aseta se nykyiseksi huippupisteeksi u. Mark u kuten vieraili.
- selvittää lyhimmän reunan liittäminen nykyiseen vertex u ja avaamaton vertex v.
- Aseta v kuin nykyinen kärki u. Mark v: n niin käynyt.
- Jos kaikki kärkipisteet alalla ovat vierailleet, sitten lopettaa. Siirry vaiheeseen 3.
sarja vieraili vertices on lähtö algoritmi.,
lähin naapuri-algoritmi on helppo toteuttaa ja suorittaa nopeasti, mutta se voi joskus kaipaamaan lyhyempiä reittejä, jotka ovat helposti huomannut ihmisen tietoa, koska sen ”ahne” luonto. Yleisohjeena, jos viime vaiheissa tour ovat vertailukelpoisia pituus ensimmäisessä vaiheessa, sitten kiertue on kohtuullinen, jos ne ovat paljon suurempi, niin on todennäköistä, että paljon paremmin kierroksia olemassa. Toinen tarkistus on käyttää algoritmia, kuten alarajan algoritmia, arvioidakseen, onko tämä kierros tarpeeksi hyvä.,
pahimmassa tapauksessa algoritmi johtaa paljon optimikiertuetta pidempään kierrokseen. Olla tarkka, sillä jokainen jatkuva t on esimerkiksi kauppamatkustajan ongelma sellainen, että pituus kiertue lasketaan lähin naapuri-algoritmi on suurempi kuin r kertaa pituus optimaalinen kiertue. Lisäksi, kunkin määrä kaupungeissa on tehtävä etäisyydet kaupunkien välissä, joista lähin naapuri heuristinen tuottaa ainutlaatuinen pahin mahdollinen kiertue., (Jos algoritmia käytetään jokaisen huippupiste alkaen huippupiste, paras polku löytyi on parempi kuin ainakin N/2-1 muut matkat, missä N on solmujen lukumäärä.)
lähimmän naapurin algoritmi ei välttämättä löydä toteuttamiskelpoista kierrosta lainkaan, vaikka sellainen olisi olemassa.