Том 7, серия 2, номер 1, 2000 г., Стр. 65-74
УДК 519.854.2+681.142.2
Ю. Л. Костюк, С. А. Жихарев
Эффективный алгоритм приближённого решения метрической задачи коммивояжёра
Аннотация:
Предлагается новый алгоритм приближенного решения задачи коммивояжера. Алгоритм развивает известную идею построения маршрута по остовному дереву минимального веса. Дерево дополняется ребрами, соответствующими вторым ближайшим расстояниям для висячих вершин. Затем циклы в графе последовательно соединяются в единый маршрут. На промежуточных шагах используется локальный поиск. Рассмотрены два варианта реализации алгоритма – для двумерной евклидовой метрики за время$O(n\log n)$ и для произвольной метрики за время$O(n^2)$ , где$n$ – число вершин графа. Приведены результаты численного эксперимента, подтверждающие хорошее качество получаемых решений.
Ил. 2, табл. 6, библиогр. 5.
Костюк Ю. Л. 1
Жихарев С. А. 1
1. Томский государственный университет, факультет информатики,
пр. Ленина, 36, 634050 Томск, Россия
е-mail: kost@inf.tsu.ru
Статья поступила 6 января 2000 г.
