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

Введение

Этот документ продолжает тему задачи коммивояжёра.
Мы обсудим различные эвристические алгоритмы, которые не гарантируют получения точного решения,
однако, иногда дают кратчайший путь или близкий к нему.
Первые два метода (жадный алгоритм и метод шнурка), обычно, используются для получения
первого приближения к решению задачи.
Затем его можно улучшить остальными эвристиками, описанными в документе.

Вообще, эффективность эвристических методов повышается при их комбинировании.
Если первые два метода не зависят от «предыстории» поиска,
то последовательность остальных методов важна и при удачном их сочетании
результат может существенно улучшиться.

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

История

Точно неизвестно, когда проблему коммивояжера исследовали впервые. Однако, известна изданная в 1832 году книга с названием «Коммивояжёр — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера» (нем. Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur), в которой описана проблема, но математический аппарат для её решения не применяется. Зато в ней предложены примеры маршрутов для некоторых регионов Германии и Швейцарии.

Ранним вариантом задачи может рассматриваться англ. Icosian Game Уильяма Гамильтона 19 века, которая заключалась в том, чтобы найти маршруты на графе с 20 узлами. Первые упоминания в качестве математической задачи на оптимизацию принадлежат Карлу Менгеру (нем. Karl Menger), который сформулировал её на математическом коллоквиуме в 1930 году так:

Гамильтон Уильям Роуэн.

Вскоре появилось известное сейчас название задача странствующего торговца (англ. Traveling Salesman Problem), которую предложил Хасслер Уитни (англ. Hassler Whitney) из Принстонского университета.

Вместе с простотой определения и сравнительной простотой нахождения хороших решений задача коммивояжёра отличается тем, что нахождение действительно оптимального пути является достаточно сложной задачей. Учитывая эти свойства, начиная со второй половины XX века исследование задачи коммивояжёра имеет не столько практический смысл, сколько теоретический в качестве модели для разработки новых алгоритмов оптимизации.

Многие современные распространенные методы дискретной оптимизации, такие как метод отсечений, ветвей и границ и различные варианты эвристических алгоритмов, были разработаны на примере задачи коммивояжёра.

В 1950-е и 1960-е годы задача коммивояжёра привлекла внимание ученых в США и Европе. Важный вклад в исследование задачи принадлежит Джорджу Данцигу, Делберту Рею Фалкерсону (англ. Delbert Ray Fulkerson) и Селмеру Джонсону (англ. Selmer M

Johnson), которые в 1954 году в институте RAND Corporation сформулировали задачу в виде задачи дискретной оптимизации и применили для её решения метод отсечений. Используя этот метод, они построили путь коммивояжёра для одной частной постановки задачи с 49 городами и обосновали его оптимальность. В 1960-е и 1970-е годы задача изучалась многими учеными как теоретически, так и с точки зрения её приложений в информатике, экономике, химии и биологии.

Ричард Карп в 1972 году доказал NP-полноту задачи поиска гамильтоновых путей, из чего, благодаря полиномиальной сводимости, вытекала NP-трудность задачи коммивояжёра. На основе этих свойств им было приведено теоретическое обоснование сложности поиска решений задачи на практике.

Больших успехов удалось достичь в конце 1970-х и 1980-х годах, когда Мартин Грётчел (нем. Martin Grötschel), Манфред Падберг (нем. Manfred Padberg) и Джованни Ринальди (итал. Giovanni Rinaldi) и другие, с применением новых методов деления плоскостью, ветвей и границ вычислили решение для отдельного случая задачи с 2393 городами.

В 1990-е годы Дэвид Аплгейт (англ. David Applegate), Роберт Биксби (англ. Robert Bixby), Вашека Шватал (англ. Vašek Chvátal) и Уильям Кук (англ. William Cook) установили рекорды по программе Конкорд. Герхард Райнельт (нем. Gerhard Reinelt) создал TSPLIB — набор стандартизованных экземпляров задачи коммивояжёра различной степени сложности для сравнения результатов работы различных групп исследователей. В марте 2005 года задача с 33 810 узлами была решена программой Конкорд: был вычислен путь длиной в 66 048 945 и доказано отсутствие более коротких путей. В апреле было найдено решение для экземпляра с 85 900 узлами. Используя методы декомпозиции, можно вычислить решения для случаев задачи с миллионами узлов, длина которых менее, чем на 1 % больше оптимальной.

Реализация

Расчет коэффициентов.

Поиск всех нулевых элементов и вычисление их коэффициентов.

Шаг 6

Переход к множеству, не содержащему ребро с максимальным штрафом.

Сравнение МВиГ с полным перебором

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

Ниже представлены графики сравнения МВиГ с полным перебором и среднее время работы реализованного мной алгоритма на различном количестве городов. Тестировалось на матрицах для случайно сгенерированных точек.

Сравнение метода ветвей и границ с полным перебором.

Начиная с 9 городов полный перебор заметно проигрывает МВиГ. Начиная с 13 городов полный перебор занимает больше минуты.

Время работы МВиГ на различном количестве городов.

Графическое приложение

Также был сделан графический интерфейс на Qt с возможностью динамически смотреть на процесс решения. Как раз его рабочая область на гифке в шапке статьи. Итересующиеся могут скомпилировать и потрогать прогу руками.

Желтым цветом обозначен наилучший найденный путь и его длина находится в поле «Tour length».

Черным обозначены ребра, находящиеся в последнем просмотренном наборе.

Для динамического отображения задача должна решаться либо пошагово, либо в параллельном с графическим интерфейсом потоке. Т.к. основная функция решения рекурсивна, был выбран второй вариант, из-за чего в решающий класс пришлось добавить мьютекс, а переменную рекорда сделать атомарной и в некоторых методах позаботиться о потокобезопасности.

Вместо заключения

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

→ Исходный код

Метод шнурка

Метод шнурка разработан для евклидовой версии задачи коммивояжёра и основан
на «человеческом» подходе к решению задачи.
На первом этапе все города окружаются охватывающим полигоном, так как это сделано на картинке ниже:

Нажми на кнопку

Для охватывания точек на плоскости выпуклым полигоном, воспользуемся алгоритмом Джарвиса.
Сначала найдём самую верхнюю из самых левых точек cur
(верхний левый угол — ось y вниз!). Выше это город номер 18,
и он, очевидно, лежит на охватывающем полигоне. Затем ищем ближайшую к cur точку nxt,
такую, что вектор в остальные точки i лежит слева
от вектора проходящего через nxt — cur (если смотреть из точки cur).
Это проверяется знаком векторного произведения (nxt — cur) x (i — cur).
Если оно равно нулю, это значит, что точки лежат на одной прямой.
После этого, точку nxt (выше 59)
делаем cur и повторяем вычисления, формируя охватывающий контур против часовой стрелки.
Алгоритм останавливается, когда возвращается к исходной точке beg:

Алгоритмическое описание

Имеется матрица расстояний M. Диагональ заполняется бесконечными значениями, т.к. не должно возникать преждевременных циклов. Также имеется переменная, хранящая нижнюю границу.

Стоит оговориться, что нужно вести учет двух видов бесконечностей — одна добавляется после удаления строки и столбца из матрицы, чтобы не возникало преждевременных циклов, другая — при отбрасывании ребер. Случаи будут рассмотрены чуть позже. Первую бесконечность обозначим как inf1, вторую — inf2. Диагональ заполнена inf1.

Из каждого элемента каждой строки вычитается минимальный элемент данной строки. При этом минимальный элемент строки прибавляется к нижней границе
Из каждого столбца аналогично вычитается минимальный элемент и прибавляется к нижней границе.
Для каждого нулевого элемента M(i, j) вычисляется коэффициент, равный сумме минимальных элементов строки i и столбца j, исключая сам элемент (i, j). Этот коэффициент показывает, насколько гарантированно увеличится нижняя граница решения, если исключить из него ребро (i, j)
Ищется элемент с максимальным коэффициентом. Если их несколько, можно выбрать любой (все равно оставшиеся будут рассмотрены на следующих шагах рекурсии)
Рассматриваются 2 матрицы — M1 и M2. M1 равна M с удаленными строкой i и столбцом j. В ней находится столбец k и строка l, в которых не содержится inf1 и элемент M(k, l) приравнивается inf1. Как было сказано ранее, это необходимо во избежание преждевременных циклов (т.е. на первых этапах (k, l) == (j, i)). Матрица M1 соответствует множеству, сожержащему ребро (i, j). Вместе с удалением столбца и строки ребро (i, j) включается в путь.
M2 равна матрице M, у которой элемент (i, j) равен inf2

Матрица соответствует множетсву путей, не сожержащих ребро (i, j) (важно понимать, что ребро (j, i) при этом не исключается).
Переход к п.1 для матриц M1 и M2.

Эвристика состоит в том, что у матрицы M1 нижняя граница не больше, чем у матрицы M2 и в первую очередь рассматривается ветвь, содержащая ребро (i, j).

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

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

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

• Полный перебор перестановок N-1
  чисел (стартовый город фиксирован). Практически бесполезен при N > 15.
• Направленный поиск с возвратами —
  перебор вариантов «вокруг» некоторого решения с отсечением путей, имеющих длину большую, чем лучший к текущему моменту путь.
• Метод ветвей и границ — наиболее эффективный из известных метод отсечения «неперспективных» узлов, за счёт анализа матрицы расстояний.
  При поиске оптимального решения строится бинарное дерево (в каждом узле порождаются 2 ветви: коммивояжёр
  идёт в некоторый город или не идёт в него).
• Линейное программирование применяется для минимизации (с ограничениями)
  линейной формы d·x, где
  x
  — искомый бинарный вектор размерности

N(N-1)/2, компоненты которого x_i
равны 1 или , в зависимости от того, входит i-е ребро в путь или нет.
Вектор d (той же размерности) равен длинам рёбер.

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

• Жадный алгоритм при выборе очередного города берёт ближайший не посещённый до этого город.
• Метод шнурка — геометрическая вариация жадного алгоритма, в которой города охватываются
  замкнутым контуром. Он постепенно растягивается, стараясь пройти через все города, минимальным образов увеличив свою
  длину.
• Скользящий перебор переставляет местами города из небольшой части пути.
  Затем такое «окно перебора» скользит вдоль всего пути. Метод имеет различные вариации и оказывается эффективным
  способом улучшения решения, найденного предыдущими двумя эвристическими методами.

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

• Метод отжига в котором происходят перестановки городов
  с постепенно «затухающей» интенсивностью. При этом постоянно сохраняется наилучшее найденное решение.
• Генетический алгоритм — более «продвинутый» вариант, при котором
  создаётся большое количество различных путей. Они постоянно «мутируют» и «скрещиваются» друг с другом,
  обмениваясь отдельным участками.

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

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

jiD_ji ≥ 0D_jiстоимостью ребраграфа

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

• Симметричная проблема коммивояжёра (TSP = traveling salesman problem) в которой расстояния заданы
  между любыми двумя городами и матрица расстояний симметрична: D_ji = D_ij.
• Асимметричная проблема коммивояжёра (ATSP) допускает несимметричность матрицы D_ji ≠ D_ij.
  В ещё более общем случае, пути между некоторыми городами могут отсутствать (== иметь бесконечную длину).
• Задача с частичным упорядочиванием (SOP = sequential ordering problem)
  требующая, чтобы определённый город i был посещён до города j
  (таких условий может быть несколько).
• Поиск цикла Гамильтона (HCP = нamiltonian cycle problem) — обнаружение
  в произвольном графе замкнутых путей, проходящих через каждую вершину в точности один раз.

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

Замкнутый и незамкнутый варианты задачи

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

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

Чтобы свести замкнутый вариант к незамкнутому, нужно определить число K{\displaystyle K}, строго превосходящее вес любого маршрута коммивояжёра в заданном графе (например, в качестве K{\displaystyle K} можно взять сумму максимальных по весу дуг, выходящих из каждой вершины, увеличенную на 1). Затем нужно добавить к графу новую вершину vn{\displaystyle v_{n}} (предполагаем, что вершины исходного графа пронумерованы числами от 0 до n−1{\displaystyle n-1}, при этом стартовая вершина имеет номер 0). Стоимости дуг, выходящих и входящих в вершину vn{\displaystyle v_{n}}, определяются следующим образом:

• cn,i=3K{\displaystyle c_{n,i}=3K}
• c,n=3K{\displaystyle c_{0,n}=3K}
• ci,n=ci,+2K{\displaystyle c_{i,n}=c_{i,0}+2K} при i{\displaystyle i} от 1{\displaystyle 1} до n−1{\displaystyle n-1}

Оптимальный незамкнутый маршрут коммивояжёра в таком графе соответствует оптимальному замкнутому маршруту коммивояжёра в исходном графе и имеет стоимость на 2K{\displaystyle 2K} больше.

Жадный алгоритм

Идея этого алгоритма очень проста. При выборе очередного города берётся ближайший город
в котором мы ещё не были. Такой подход, по понятным причинам называется «жадным».
К сожалению, если в начале путь получается коротким, то в конце часто
возникает очень большой прирост его длины.

В жадном алгоритме принципиально какой город выбирается в качестве стартового.
Чтобы улучшить результат, будем по очереди делать стартовым каждый город,
выбирая тот вариант, который даст кратчайший путь.
В начале следующей итерации вспомогательный массив way
заполняется номерами городов: way =
и на первое место ставится город j=0,1,2,…N-1.
Для этого он меняется местами с нулевым элементом массива.
Затем ищется ближайший к нему город и ставится на первое место (снова при помощи перестановки
элементов массива функцией swap). Эти действия продолжаются,
пока не сформируется полный путь:

Salesman.prototype.greedy = function ()
{
   this.minLen = Infinity;
   for(var j=0; j  d){                        // если длина пути лучшая,
         this.minLen = d;                         // запоминаем её и путь:
         this.minWay = Salesman.copy(this.minWay, this.way);
      }
   }
}

Приведём длину пути, сам путь и карту городов в конце каждого цикла по стартовому городу j
для карты городов, созданной функцией create(100,100, 7, lcg, true) (картинки увеличены в scale = 2.2 раза):

1673053378

Жадный алгоритм (с перебором стартового города) имеет кубическое время работы T ~ N3.
Поэтому для большого числа городов N стоит переписать функцию greed
для вызова её в таймере. Соответствующий код
(функции greedInit и greedTimer)
можно найти в исходниках класса salesman.js.

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

Алгоритм Литтла является частным случаем МВиГ, т.е. в худшем случае его сложность равна сложности полного перебора. Теоретическое описание выглядит следующим образом:

Имеется множетво S всех гамильтоновых циклов рафа. На каждом шаге в S ищется ребро (i, j), исключение которого из маршрута максимально увеличит оценку снизу. Далее происходит разбиение множества на два непересекающихся S1 и S2. S1 — все циклы, содержащие ребро (i, j) и не содержащие (j, i). S2 — все циклы, не содержащие (i, j). Далее вычисляется оценка снизу для длины пути каждого множества и, если она превышает длину уже найденного решения, множество отбрасывается. Если нет — множества S1 и S2 обрабатываются так же, как и S.

Алгоритм решения задачи коммивояжера

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

Данная курсовая работа рассматривает один из хорошо известных алгоритмов – жадный алгоритм,
который будет использован при решении задачи коммивояжера. А еще мы напишем
в среде разработки Delphi несложную программу,
которая будет использовать этот алгоритм. Хотя среда разработки и язык программирования значения не имеют.
Задачу коммивояжёра можно решить и спомощью других средств, например, Excel.

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

Постановка задачи коммивояжера

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по одному
разу в неизвестном порядке города 2,3,4..n и вернуться в первый город. Расстояния
между городами известны. В каком порядке следует обходить города, чтобы замкнутый
путь (тур) коммивояжера был кратчайшим?

Жадный алгоритм

Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого,
ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами.
«Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться
за жадность.

Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь он превратится
в стратегию «иди в ближайший (в который еще не входил) город». Жадный алгоритм, очевидно,
бессилен в этой задаче. Рассмотрим для примера сеть на рис. 2, представляющую узкий ромб.
Пусть коммивояжер стартует из города 1. Алгоритм «иди в ближайший город» выведет его в город 2,
затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной
диагонали ромба. В результате получится не кратчайший, а длиннейший тур. Однако в некоторых
ситуациях «жадный» алгоритм определяет-таки кратчайший путь.

Полный перебор

Метод полного перебора (иногда говорят Метод перебора, подразумевая
при этом полный перебор — это не совсем правильно, так как перебор может быть и не полным)
заключается в том, что выполняется перебор всех возможных
комбинаций точек (пунктов назначения). Как известно из математики, число таких перестановок
равно n!, где n – количество точек. Так как в задаче коммивояжера исходный пункт обычно
принимается одним и тем же (первая точка), то нам достаточно перебрать оставшиеся,
т.е. количество перестановок будет равно (n–1)!. Этот алгоритм почти всегда дает точное
решение задачи коммивояжера, однако продолжительность таких вычислений может занять
непозволительно много времени. Известно, что при значениях n > 12, современный компьютер
не смог бы решить задачу коммивояжера даже за все время существования вселенной.

Как уже упоминалось, существуют и другие алгоритмы для решения задачи коммивояжера,
которые значительно точнее жадного алгоритма и значительно быстрее метода полного перебора.
Однако дисциплина называется «Программирование и основы алгоритмизации», из чего следует,
что на первом месте у нас все-таки программирование, а уж потом можно и с алгоритмами разбираться.
Поэтому в данной курсовой работе другие алгоритмы не рассматриваются в виду относительной
сложности. Да и пора бы нам уже написать какую-нибудь программу в любимой нами Delphi.