Эффективный алгоритм приближенного решения метрической задачи коммивояжера

Предлагается новый алгоритм приближенного решения задачи коммивояжера. Алгоритм развивает известную идею построения маршрута по остовному дереву минимального веса. Дерево дополняется ребрами, соответствующими вторым ближайшим расстояниям для висячих вершин. Затем циклы в графе последовательно соединяются в единый маршрут. На промежуточных шагах используется локальный поиск. Рассмотрены два варианта реализации алгоритма – для двумерной евклидовой метрики за время $O(n\log n)$ и для произвольной метрики за время $O(n^2)$, где $n$ – число вершин графа. Приведены результаты численного эксперимента, подтверждающие хорошее качество получаемых решений. Ил. 2, табл. 6, библиогр. 5.