Алгоритам најближег комшије је био један од првих алгоритама коришћен за одређивање решења проблема трговачког путника.[1] У њему путник креће из насумичног града и изнова посећује најближи град, све док сви градови не буду посећени. Алгоритмом се брзо долази до кратког низа градова, али то обично није оптимално решење.[2]
Ово су кораци алгоритма:
Низ посећених чворова је излаз алгоритма.
Алгоритам најближег комшије је лако имплементирати и извршава се брзо, али некад уме да промаши најкраћу путању која се лакше примети људским схватањем, због његове “похлепне” пририде. Као опште упутство, ако је последњих неколико фаза упоредиво по дужини са првим фазама, онда је путања разумна; ако су много веће, онда је вероватније да постоје много боље путање. У најгорем случају, алгоритам даје путању која је много дужа од оптималне.
Да будемо прецизни, за сваку константу r постоји инстанца проблема трговачког путника таква да је дужина путање израчуната алгоритмом “Најближег комшије” r пута већа од дужине оптималне путање. Шта више, за сваки од градова додељена је дистанца између градова за коју алгоритам најближег комшије хеуристички производи јединствену најгору могућу путању.