Об эффективности одного локального алгоритма решения задачи коммивояжера

Приводится теоретическое сравнение известных локальных алгоритмов наискорейшего спуска решения задачи коммивояжера с алгоритмом, предложенным Сарвановым и Дорошко [1]. Показано, что при случайном выборе исходного гамильтонова контура алгоритм Сарванова — Дорошко находит в окрестности этого контура гамильтонов контур меньшей длины, нежели известные локальные алгоритмы наискорейшего спуска для почти всех полных симметрических орграфов с некоторыми дискретными весами дуг.