Метод на най-близкия съсед
Методът на най-близкия съсед (на английски: the nearest neighbour algorithm) е един от първите алгоритми за комбинаторна оптимизация[1][2], използвани за намиране на решение на задачата за търговския пътник. При този евристичен метод, търговският пътник започва от случайно избран град и итеративно посещава най-близкия непосетен съседен град, докато всички градове бъдат посетени. Алгоритъмът открива кратък път (последователност от градове), но не задължително този път да е оптималният.
Методът на най-близкия съсед е лесен за реализация и бързо се изпълнява, но поради характера си на „алчен“ („лаком“) алгоритъм (greedy algorithm) понякога може да пропусне много по-кратки пътища в графа, които могат да бъдат забелязани интуитивно с човешко око. Като общо правило, ако последните няколко стъпки от маршрута са сравними по дължина с първите стъпки, то избраният маршрут е рационален; ако са много по-големи, вероятно съществуват и по-кратки маршрути.
В най-лошия случай, алгоритъмът дава в резултат маршрут, който е много по-дълъг от оптималния, т.е. за всяка константа q съществува инстанция на задачата за търговския пътник такава, че дължината на пътя, изчислена по метода на най-близкия съсед, е по-голяма от q пъти дължината на оптималния маршрут. Нещо повече, за всеки брой градове, съществува такова назначение на разстоянията между градовете, за което методът на най-близкия съсед дава възможно най-лошото решение (решението с най-дълъг маршрут).[3]
Вижте също редактиране
Източници редактиране
- ↑ G. Bendall and F. Margot, Greedy Type Resistance of Combinatorial Problems, Discrete Optimization 3 (2006), 288 – 298.
- ↑ J. Bang-Jensen, G. Gutin and A. Yeo, When the greedy algorithm fails. Discrete Optimization 1 (2004), 121 – 127.
- ↑ 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 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.
ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни. |