Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр — разъездной сбытовой посредник) - одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.

Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.

Общая постановка задачи, впрочем как и большинство её частных случаев, относится к классу NP-полных задач.

Методы решения

Простейшие

• полный перебор
• случайный перебор
• жадные алгоритмы
  • метод ближайшего соседа
  • метод включения ближайшего города
  • метод самого дешёвого включения
• метод минимального остовного дерева
• метод имитации отжига

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

Существует также постановки, в которых задача коммивояжера становится NP-полной. Обычно такие постановки выглядят следующим образом: существует ли на заданном графе G такой обход, что его стоимость не превышает x. Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора.

На практике применяются различные модификации более эффективных методов: метод ветвей и границ и метод генетических алгоритмов, а также алгоритм муравьиной колонии.

Метод ветвей и границ

Для решения задачи коммивояжёра предложен в 1963 году группой авторов (Дж. Литл, К. Мурти, Д. Суини, К.Кэрол). ^[1]

Метод эластичной сети

См. также Упругая карта, Выпуклая оболочка

История

В 1987 году его использовали Дурбин (Durbin) и Уиллшоу (Willshaw), указавшие аналогию с механизмами установления упорядоченных нейронных связей^[2].

Каждый из маршрутов коммивояжера рассматривался как отображение окружности на плоскость (в каждый город на плоскости отображается некоторая точка этой окружности). Соседние точки на окружности должны отображаться в точки, по возможности ближайшие и на плоскости.

Алгоритм

Начинается с установки на плоскость небольшой окружности. Оно неравномерно расширяющейся, становясь кольцом, проходящим практически около всех городов и устанавливая т.о. искомый маршрут. На каждую движущуюся точку кольца оказывает действие две составляющие: перемещение точки в сторону ближайшего города и смещение в сторону соседей точки на кольце так, чтобы уменьшить его длину. Город в итоге связывается с определенным участком кольца по мере расширения.

Литература

• Ананий В. Левитин Глава 3. Метод грубой силы: Задача коммивояжера // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 159-160. — ISBN 0-201-74395-7
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
• В.И. Мудров Задача о коммивояжере. — М.: «Знание», 1969. — С. 62.

Примечания