В данной статье предлагаются алгоритмы приближенного решения задачи коммивояжера. Первый алгоритм развивает известную идею построения маршрута по остовному дереву минимального веса. Дерево дополняется ребрами, соответствующими вторым ближайшим расстояниям для висячих вершин. Затем циклы в графе ...