Algoritmus nejbližšího souseda
jedná se o kroky algoritmu:
- inicializovat všechny vrcholy jako nenavštívené.
- Vyberte libovolný vrchol, nastavte jej jako aktuální vrchol u. označte u jako navštívený.
- Zjistit nejkratší hranu spojující aktuální vrchol u a nenavštívené vrcholy v.
- Nastavit v jako aktuální vrchol u. Mark v, jak navštívil.
- pokud jsou navštíveny všechny vrcholy v doméně, ukončete. Jinak přejděte ke kroku 3.
sekvence navštívených vrcholů je výstupem algoritmu.,
algoritmus nejbližšího souseda se snadno implementuje a provádí rychle, ale někdy může chybět kratší trasy, které jsou díky své „chamtivé“ povaze snadno zaznamenány s lidským vhledem. Jako obecný průvodce, pokud jsou poslední etapy turné srovnatelné s délkou prvních etap, pak je prohlídka rozumná; pokud jsou mnohem větší, pak je pravděpodobné, že existují mnohem lepší zájezdy. Další kontrolou je použití algoritmu, jako je algoritmus dolní hranice, aby se odhadlo, zda je tato prohlídka dostatečně dobrá.,
v nejhorším případě má algoritmus za následek prohlídku, která je mnohem delší než optimální prohlídka. Přesněji, pro každý konstantní r je instance problém obchodního cestujícího tak, že délka prohlídky vypočítává algoritmus nejbližšího souseda je větší než r, krát délka optimální turné. Navíc pro každý počet měst existuje přiřazení vzdáleností mezi městy, pro které nejbližší soused heuristic produkuje jedinečnou nejhorší možnou prohlídku., (Pokud je algoritmus aplikován na každý vrchol jako počáteční vrchol, nejlepší nalezená cesta bude lepší než alespoň n/2-1 ostatní prohlídky, kde N je počet vrcholů.)
algoritmus nejbližšího souseda nemusí najít proveditelnou prohlídku vůbec, i když existuje.