Алгоритам најближег комшије

Алгоритам најближег комшије је био један од првих алгоритама коришћен за одређивање решења проблема трговачког путника.^[1] У њему путник креће из насумичног града и изнова посећује најближи град, све док сви градови не буду посећени. Алгоритмом се брзо долази до кратког низа градова, али то обично није оптимално решење.^[2]

Ово су кораци алгоритма:

Означимо један произвољан чвор као тренутни
Нађемо најкраћи пут који повезује тренутни чвор са не посећеним чвором V
Поставимо тренутни чвор као V
Означимо V
Ако су сви чворови у домену посећени, онда завршавамо
Иди на корак 2

Низ посећених чворова је излаз алгоритма.

Алгоритам најближег комшије је лако имплементирати и извршава се брзо, али некад уме да промаши најкраћу путању која се лакше примети људским схватањем, због његове “похлепне” пририде. Као опште упутство, ако је последњих неколико фаза упоредиво по дужини са првим фазама, онда је путања разумна; ако су много веће, онда је вероватније да постоје много боље путање. У најгорем случају, алгоритам даје путању која је много дужа од оптималне.

Да будемо прецизни, за сваку константу r постоји инстанца проблема трговачког путника таква да је дужина путање израчуната алгоритмом “Најближег комшије” r пута већа од дужине оптималне путање. Шта више, за сваки од градова додељена је дистанца између градова за коју алгоритам најближег комшије хеуристички производи јединствену најгору могућу путању.

Референце

^ G. Gutin, A. Yeo and A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP. Discrete Applied Mathematics 117 (2002), 81-86.
^ María Luisa Micó; Oncina, José (1994). „A new version of the nearest-neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements”. 15 (1): 9—17. doi:10.1016/0167-8655(94)90095-7.

Литература

J. Bang-Jensen, G. Gutin and A. Yeo, When the greedy algorithm fails. Discrete Optimization 1 (2004), 121-127.
G. Bendall and F. Margot, Greedy Type Resistance of Combinatorial Problems, Discrete Optimization 3 (2006), 288-298.

[1] G. Gutin, A. Yeo and A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP. Discrete Applied Mathematics 117 (2002), 81-86.

[2] María Luisa Micó; Oncina, José (1994). „A new version of the nearest-neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements”. 15 (1): 9—17. doi:10.1016/0167-8655(94)90095-7.

[1]

[2]