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

Из Википедије, слободне енциклопедије

Овај артикал је о “апроксимацији” алгоритма за решавање проблема трговачког путника.

За остале употребе погледајте “Најближи комшија”.

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


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

  1. Означимо један произвољан чвор као тренутни
  2. Нађемо најкраћи пут који повезује тренутни чвор са не посећеним чвором V
  3. Поставимо тренутни чвор као V
  4. Означимо V
  5. Ако су сви чворови у домену посећени, онда завршавамо
  6. Иди на корак 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.

  • 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.