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

Постановка задачи

При обсуждении метода "грубой силы" (последовательный перебор) была сформулирована задача коммивояжёра:

Eсть N городов, соединённых между собой дорогами. Необходимо проложить между ними кратчайший замкнутый маршрут, проходящий через каждый город только один раз.
Расстояние из города j в город i считается неотрицательным числом: Dji ≥ 0. Это не обязательно "физическая длина" дороги. "Расстоянием" может быть время перемещения, стоимость билета или произвольное неотрицательное число. Часто Dji называют стоимостью ребра (edge costs), так как дороги можно представить рёбрами (edges), соединяющими города-вершины (vertices) некоторого графа.

Приведём небольшую классификацию вариантов задачи:

В TSP (симметричной задаче коммивояжёра) путь замкнут и стартовать можно с любого города (и в любую сторону). Поэтому для N городов существует (N-1)!/2 различных путей. Факториал растёт очень быстро: N! ~ NN и пространство в котором ищется оптимальное решение оказывается огромным. Именно поэтому задача коммивояжёра интересна для тестирования различных алгоритмов.

Евклидова задача коммивояжёра

Если Dji = Dij и расстояния между любыми городами i, j, k удовлетворяют неравенству треугольника: Dij + Djk ≥ Dik, то задачу коммивояжёра называют метрической. Её частным случаем является задача соединения кратчайшей замкнутой ломаной линией точек на плоскости (расстояние равно обычному евклидовому расстоянию). Ниже приведены решения такой задачи для 20 и 50 городов:

Несложно видеть, что в евклидовой задача коммивояжёра (ETSP) оптимальный путь не должен иметь пересечений. Действительно, пусть есть некоторый путь, изображённый ниже на первом рисунке. Пунктиром обозначены остальные его участки (т.е. приведены только 4-е города). Если перебросить два участка пути (как на второй картинке), то общий путь вырастет (сумма диагоналей 4-угольника всегда длиннее суммы двух противоположных сторон):

С ETSP связаны интересные вопросы статистического характера. Рассмотрим, например, квадрат в котором случайно, с равномерным распределением размещено N городов. Оказывается, что в большинстве случаев такие "карты городов" имеют кратчайшие пути примерно одной длины, пропорциональной квадратному корню из N.

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

Задача коммивояжёра относится к классу NP-трудных и не известен алгоритм, который позволет гарантировано её решить за полиномиальное по числу городов N время T ~ Nk, k=const. Тем не менее, для "обозримого" количества городов существует множество способов решения:

1. Точные методы не только находят некоторое решение, но и при окончании своей работы доказывают, что это решение - наилучшее. Отметим следующие из них:

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

3. Вероятностные методы фактически ни когда не останавливаются, совершая случайные изменения пути, в ожидании получения более короткого. Из этого класса методов отметим:

Немного истории

По-видимому первая задача, связанная с проблемой коммивояжёра была поставлена и решена Леонардом Эйлером в 1757 г. Он предложил найти замкнутый путь для коня на шахматной доске. Соответствующее решение, найденное самим Эйлером, приведено ниже, слева:

425744 9402146 7
5510415845 83920
124356612259 647
6354113025281938
32136227602348 5
5364312429263718
1433 2511635 449
1521534 3501736
В этом случае речь идёт не о поиске кратчайшего пути, а о факте установления возможности существования такого пути, проходящего через все вершины графа один и только один раз. Для произвольного графа соответствующую проблему сформулировал Уильям Гамильтон в 1859 г. Он придумал головоломку «Путешествие вокруг света», связанную с обходом вершин додекаэдра (выше, справа) и даже выпустил её в продажу.

Полезные ресурсы

> Класс Salesman