Метод на най-близкия съсед

от Уикипедия, свободната енциклопедия
Направо към навигацията Направо към търсенето

Методът на най-близкия съсед (на английски: the nearest neighbour algorithm) е един от първите алгоритми за комбинаторна оптимизация[1][2], използвани за намиране на решение на задачата за търговския пътник. При този евристичен метод, търговският пътник започва от случайно избран град и итеративно посещава най-близкия непосетен съседен град, докато всички градове бъдат посетени. Алгоритъмът открива кратък път (последователност от градове), но не задължително този път да е оптималният.

Методът на най-близкия съсед е лесен за реализация и бързо се изпълнява, но поради характера си на „алчен“ („лаком“) алгоритъм (greedy algorithm) понякога може да пропусне много по-кратки пътища в графа, които могат да бъдат забелязани интуитивно с човешко око. Като общо правило, ако последните няколко стъпки от маршрута са сравними по дължина с първите стъпки, то избраният маршрут е рационален; ако са много по-големи, вероятно съществуват и по-кратки маршрути.

В най-лошия случай, алгоритъмът дава в резултат маршрут, който е много по-дълъг от оптималния, т.е. за всяка константа q съществува инстанция на задачата за търговския пътник такава, че дължината на пътя, изчислена по метода на най-близкия съсед, е по-голяма от q пъти дължината на оптималния маршрут. Нещо повече, за всеки брой градове, съществува такова назначение на разстоянията между градовете, за което методът на най-близкия съсед дава възможно най-лошото решение (решението с най-дълъг маршрут).[3]

Вижте също[редактиране | редактиране на кода]

Източници[редактиране | редактиране на кода]

  1. G. Bendall and F. Margot, Greedy Type Resistance of Combinatorial Problems, Discrete Optimization 3 (2006), 288 – 298.
  2. J. Bang-Jensen, G. Gutin and A. Yeo, When the greedy algorithm fails. Discrete Optimization 1 (2004), 121 – 127.
  3. 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.
Криейтив Комънс - Признание - Споделяне на споделеното Лиценз за свободна документация на ГНУ Тази страница частично или изцяло представлява превод на страницата „Nearest neighbour algorithm“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс - Признание - Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница. Вижте източниците на оригиналната статия, състоянието ѝ при превода, и списъка на съавторите.