Back

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




                                     

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

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

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

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

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

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

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

                                     
  • нечијем суседству Комшије ТВ серија српска ТВ серија Моје драге комшије, шпанска ТВ серија Алгоритам најближег комшије Комшија вишезначна одредница
  • информатици, селекциони алгоритам је алгоритам који проналази k - ти најмањи елемент у повезаној листи или низу. Овај алгоритам укључује и случајеве тражења
  • BKD stablo. Mnogi od ovih načina su adaptacija K - D stabla. Algoritam traženja najbližeg komšije ima za cilj da pronade čvor u drvetu koji je najbliži datom