Задача коммивояжера

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

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

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

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

Простейшие

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

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

Задача коммивояжёра есть NP-полная задача. Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора.

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

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

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

Литература

• Ананий В. Левитин Глава 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

Примечания

1. ↑ Костевич Л.С. Математическое программирование: Информ. технологии оптимальных решений: Учеб. пособие / Л.С. Костевич. — Мн.: Новое знание, 2003. ил., стр. 150, ISBN 985-6516-83-8

См. также

• Граф (математика)
• Оптимизация
• Комбинаторика
• Исследование операций
• Математическое программирование
• Дискретная математика

Ссылки