Два алгоритма приближённого решения задачи коммивояжёра

Abstract

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