Algoritmul cel mai apropiat vecin
acestea sunt pașii algoritmului:
- inițializează toate nodurile ca nevizitate.
- selectați un nod arbitrar, setați-l ca nod curent u. marcați u ca vizitat.
- aflați marginea cea mai scurtă care conectează nodul curent u și un nod v nevizitat.
- setați v ca nod curent u.marcați v ca vizitat.
- dacă toate vârfurile din domeniu sunt vizitate, atunci terminați. Altfel, treci la Pasul 3.
secvența vârfurilor vizitate este rezultatul algoritmului.,
algoritmul celui mai apropiat vecin este ușor de implementat și se execută rapid, dar uneori poate lipsi rute mai scurte, care sunt ușor de observat cu perspicacitate umană, datorită naturii sale „lacome”. Ca ghid general, dacă ultimele etape ale turului sunt comparabile în lungime cu primele etape, atunci Turul este rezonabil; dacă sunt mult mai mari, atunci este probabil să existe tururi mult mai bune. O altă verificare este să folosiți un algoritm, cum ar fi algoritmul inferior pentru a estima dacă acest tur este suficient de bun.,în cel mai rău caz, algoritmul are ca rezultat un tur care este mult mai lung decât turul optim. Pentru a fi mai precis, pentru fiecare R constant există o instanță a problemei vânzătorului călător, astfel încât lungimea turului calculată de algoritmul celui mai apropiat vecin este mai mare decât r ori lungimea turului optim. Mai mult, pentru fiecare număr de orașe există o repartizare a distanțelor între orașele pentru care cel mai apropiat vecin euristic produce cel mai rău tur posibil., (Daca algoritmul este aplicat pe fiecare nod ca nod de pornire, cea mai buna cale gasita va fi mai buna decat cel putin n/2-1 alte tururi, unde N este Numarul de noduri.)
algoritmul celui mai apropiat vecin poate să nu găsească deloc un tur fezabil, chiar și atunci când există unul.