Методът на най-близкия съсед () е един от първите алгоритми за комбинаторна оптимизация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., използвани за намиране на решение на задачата за търговския пътник. При този евристичен метод, търговският пътник започва от случайно избран град и итеративно посещава най-близкия непосетен съседен град, докато всички градове бъдат посетени. Алгоритъмът открива кратък път (последователност от градове), но не задължително този път да е оптималният.
Методът на най-близкия съсед е лесен за реализация и бързо се изпълнява, но поради характера си на „алчен“ („лаком“) алгоритъм (greedy algorithm) понякога може да пропусне много по-кратки пътища в графа, които могат да бъдат забелязани интуитивно с човешко око. Като общо правило, ако последните няколко стъпки от маршрута са сравними по дължина с първите стъпки, то избраният маршрут е рационален; ако са много по-големи, вероятно съществуват и по-кратки маршрути.
В най-лошия случай, алгоритъмът дава в резултат маршрут, който е много по-дълъг от оптималния, т.е. за всяка константа q съществува инстанция на задачата за търговския пътник такава, че дължината на пътя, изчислена по метода на най-близкия съсед, е по-голяма от q пъти дължината на оптималния маршрут. Нещо повече, за всеки брой градове, съществува такова назначение на разстоянията между градовете, за което методът на най-близкия съсед дава възможно най-лошото решение (решението с най-дълъг маршрут).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.
Вижте също Метод на k-най-близките съседи Локално търсене
Източници
Категория:Математическо оптимиране Категория:Алгоритми Категория:Алгоритми за граф