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

Задача коммивояжёра (англ. travelling salesman problem, TSP) — это классическая задача комбинаторной оптимизации, заключающаяся в поиске самого короткого замкнутого маршрута, проходящего через заданный набор городов (точек) ровно по одному разу и возвращающегося в исходный город. Относится к классу NP-трудных задач, что означает отсутствие известного эффективного (полиномиального) алгоритма для её точного решения в общем случае при большом числе городов. Формально задачу можно определить на полном взвешенном графе, где вершины — города, рёбра — пути между ними, а веса рёбер — расстояния или стоимость проезда. Цель — найти гамильтонов цикл минимального суммарного веса.

История

Первые упоминания задачи, сходной с задачей коммивояжёра, встречаются в математических трактатах XIX века. В 1832 году в немецком «Справочнике для коммивояжёров» описывались практические советы по построению маршрутов, однако формальная математическая постановка была предложена позднее. В 1930-х годах задача активно изучалась в Вене и Принстоне, в частности Карлом Менгером, который сформулировал её как поиск кратчайшего маршрута, проходящего через все заданные точки. В 1954 году Джордж Данциг, Рэй Фалкерсон и Селмер Джонсон впервые решили задачу для 49 городов (столиц штатов США) с помощью метода отсечений, что стало важным этапом в развитии методов целочисленного линейного программирования. С тех пор TSP остаётся одной из самых изучаемых задач в области оптимизации и теории алгоритмов.

Формальная постановка

Пусть задано множество городов \( V = \{v_1, v_2, \dots, v_n\} \) и матрица расстояний \( C = (c_{ij}) \), где \( c_{ij} \) — расстояние (или стоимость) между городами \( v_i \) и \( v_j \). Матрица может быть симметричной (если расстояния одинаковы в обоих направлениях) или асимметричной (например, при учёте одностороннего движения). Задача заключается в нахождении перестановки \( \pi \) городов, такой что суммарное расстояние \[ \sum_{i=1}^{n-1} c_{\pi(i), \pi(i+1)} + c_{\pi(n), \pi(1)} \] минимально.

Варианты задачи

• Симметричная TSP — матрица расстояний симметрична (\( c_{ij} = c_{ji} \)). Наиболее распространённый вариант.
• Асимметричная TSP — расстояния могут различаться в зависимости от направления (\( c_{ij} \neq c_{ji} \)).
• Метрическая TSP — расстояния удовлетворяют неравенству треугольника (\( c_{ij} \leq c_{ik} + c_{kj} \)). Для этого класса существуют приближённые алгоритмы с гарантированной точностью.
• Евклидова TSP — частный случай метрической, где города расположены на плоскости с евклидовым расстоянием.
• Задача с возвратом — классическая постановка, где маршрут должен быть замкнутым.
• Задача без возврата (англ. open TSP) — требуется найти кратчайший путь, проходящий через все города, без обязательного возврата в начальную точку.

Сложность и NP-трудность

Задача коммивояжёра является NP-трудной, что доказано сведением к ней задачи о гамильтоновом цикле. Это означает, что если бы существовал полиномиальный алгоритм для точного решения TSP, то все задачи класса NP решались бы за полиномиальное время, что маловероятно (гипотеза P ≠ NP). Для \( n \) городов число возможных маршрутов равно \( (n-1)!/2 \) для симметричной задачи, что делает полный перебор практически невозможным при \( n > 20 \). Например, для 50 городов число маршрутов превышает \( 3 \times 10^{62} \).

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

Точные алгоритмы

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

• Метод ветвей и границ — рекурсивный перебор с отсечением неперспективных подмножеств решений на основе нижних оценок длины маршрута.
• Метод отсечений (Гомори) — решение целочисленной линейной программы с последовательным добавлением ограничений, отсекающих нецелочисленные решения.
• Декомпозиция Данцига — Фалкерсона — Джонсона — классический подход с использованием линейного программирования и отсечений для подциклов.
• Динамическое программирование (алгоритм Хелда — Карпа) — решение за \( O(n^2 2^n) \), что является лучшим точным методом для малых \( n \) (до 20–25 городов).

Приближённые алгоритмы

Для метрической TSP существуют алгоритмы с гарантированной точностью:

• Алгоритм дважды вокруг дерева — строит минимальное остовное дерево, удваивает его рёбра и находит эйлеров цикл, затем преобразует его в гамильтонов. Гарантирует решение не хуже 2-кратного от оптимума.
• Алгоритм Кристофидеса — улучшенная версия, использующая паросочетание для вершин нечётной степени. Гарантирует решение не хуже 1.5-кратного от оптимума (для метрической TSP). Является лучшим известным приближением с гарантией.
• Жадные алгоритмы — например, метод ближайшего соседа: начиная с произвольного города, каждый раз переходить в ближайший непосещённый. Прост, но не имеет гарантии качества (в среднем даёт решение на 20–30% хуже оптимума).
• Эвристики улучшения — например, 2-opt, 3-opt: итеративно заменяют два или три ребра в текущем маршруте, если это уменьшает его длину.

Метаэвристики

Для больших размерностей (сотни и тысячи городов) применяют:

• Генетические алгоритмы — эволюционный поиск с операциями скрещивания и мутации маршрутов.
• Имитация отжига — вероятностный алгоритм, имитирующий процесс охлаждения металла.
• Муравьиные алгоритмы — моделирование поведения муравьёв, оставляющих феромоны на пройденных рёбрах.
• Роевой интеллект — коллективное поведение агентов для поиска оптимального маршрута.

Применение

Задача коммивояжёра имеет широкое практическое применение в различных областях:

• Логистика и транспорт — планирование маршрутов доставки товаров, сбор мусора, школьные автобусы, курьерские службы.
• Производство — оптимизация перемещения инструментов или заготовок на станках с ЧПУ (задача сверления печатных плат).
• Микроэлектроника — трассировка соединений на кристаллах и печатных платах.
• Генетика — секвенирование ДНК (задача сборки генома).
• Астрономия — планирование наблюдений телескопов.
• Туризм — составление маршрутов путешествий.

Рекорды и известные примеры

• Задача для 49 городов (столицы штатов США), решённая в 1954 году, имела оптимальную длину 699 миль.
• В 2006 году решена задача для 85 900 городов (микросхема VLSI), что стало рекордом для точного решения.
• Для 1000 городов точное решение может потребовать нескольких часов на современных суперкомпьютерах.
• В 2010 году решена задача для 1 904 711 городов (на основе данных о дорогах Швеции) с использованием приближённых методов и кластерных вычислений.

Критика и ограничения

Несмотря на обилие алгоритмов, точное решение TSP для больших размеров (более 1000 городов) остаётся вычислительно дорогим и часто непрактичным. Приближённые методы не гарантируют оптимальности, а их точность сильно зависит от структуры данных. Кроме того, в реальных задачах часто присутствуют дополнительные ограничения (временные окна, пропускная способность дорог, динамические изменения), которые превращают TSP в более сложные варианты (например, задача коммивояжёра с временными окнами — TSPTW). Критики отмечают, что классическая постановка редко встречается в чистом виде на практике, и её популярность во многом обусловлена математической красотой и фундаментальностью.

Источники

• М. Гэри, Д. Джонсон. «Вычислительные машины и труднорешаемые задачи». — М.: Мир, 1982.
• D. L. Applegate, R. E. Bixby, V. Chvátal, W. J. Cook. «The Traveling Salesman Problem: A Computational Study». — Princeton University Press, 2006.
• G. Gutin, A. P. Punnen (eds.). «The Traveling Salesman Problem and Its Variations». — Springer, 2002.
• E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys (eds.). «The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization». — Wiley, 1985.