Задача коммивояжёра (поиск минимального гамильтонова цикла)

Алгоритмы   18 Январь 2012  Автор статьи:  

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

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

Алгоритм решения

Первая идея, которая приходит в голову при попытке решения данной задачи, – это перебирать все возможные пути, проходящие только по различным вершинам, и для каждого проверять соответствие определению гамильтонова пути (цикл получится из пути добавлением одного ребра). Асимптотическая сложность такого алгоритма – O(n! \cdot n), т.е. такой алгоритм будет работать неприемлемо долго даже на небольших графах. Второй возможный подход — это использование всевозможных эвристических алгоритмов. Они будут выдавать решение, близкое к правильному,  однако в некоторых случаях неоптимальное. В зависимости от сложности идеи такой алгоритм может работать достаточно хорошо, но не идеально. Простейший пример такого алгоритма — алгоритм, формирующий путь жадно: на каждой итерации в путь будет включаться дуга в ещё не посещённую вершину, имеющая минимальный вес. Для такого алгоритма несложно придумать контртест.

Оказывается, задача коммивояжёра относится к классу NP, т.е. к настоящему времени не найдено полиномиальных алгоритмов, позволяющих получить точное решение этой задачи. Самый эффективный из известных алгоритмов для поиска этого решения имеет асимптотическую сложность O(2^nn^2)  и основан на динамическом программировании. Именно этот алгоритм и будет рассмотрен в данной статье.

Сразу отметим, что неважно, из какой именно вершины начинать движение при обходе графа. Пусть это будет вершина 0 (нумерация от 0 до n-1). Кроме того, нужно сразу обратить внимание на следующую особенность рассматриваемого алгоритма: одним из параметров в подзадачах станет подмножество вершин графа. Задумываться о практической реализации работы с подмножествами мы пока не будем; этот вопрос будет освещён в дальнейшем.

Пусть D_{i,j} – длина дуги из вершины i в вершину j, V — множество вершин графа, а E — множество дуг. Обозначим за T_{i,j} минимальный вес некоторого пути, начинающегося в вершине 0, заканчивающегося в вершине j и проходящего только по вершинам из множества i (причём ровно по одному разу по каждой). Если такой путь отсутствует, положим T_{i,j}=\infty (при реализации в качестве бесконечности следует выбрать значение, которое заведомо превосходит все возможные длины путей). Случай, когда подмножество состоит из самой вершины 0, тривиален. Можно выделить также несколько случаев, когда искомого пути гарантированно не существует. Во-первых, в соответствии с выбранными подзадачами, вершины 0 и j должны принадлежать множеству i. Нарушение этого условия автоматически ведёт к тому, что решения у подзадачи нет. Во-вторых, если j=0, то путь должен состоять из одной вершины (в противном случае мы бы посетили вершину 0 дважды, что недопустимо). Но если при этом множество i помимо нулевой содержит и другие вершины, то подзадача решения не имеет. Рекуррентные соотношения основаны на том, что искомый путь должен состоять из оптимального пути из 0 в некоторую вершину k и ребра (k,j). При этом, поскольку вершина j является концевой вершиной текущего пути, то во вспомогательном пути она встречаться не должна. Имеем:

T_{i,j}=\begin{cases}& 0, \text{ if } i = \{0\}, j = 0 \\& min_{k \in i,(k,j)\in E,T_{i \setminus {j},k} \ne \infty}(T_{i \setminus{j},k}+D_{k,j}), \text{ if } j > 0, 0 \in i, j \in i \\ & \infty \text { otherwise } \end{cases}

Здесь i\setminus\{j\} – дополнение множества \{j\} до множества i.

Итак, для каждого j мы знаем вес минимального гамильтонова пути, начинающегося в 0 и заканчивающегося в j. Тогда, чтобы получить гамильтонов цикл, достаточно к пути добавить дугу (j,0) (если, конечно, она есть в графе). Из всех таких циклов нужно выбрать наименьший по весу. Более формально, вес искомого цикла равен \min_{j \in V\setminus \{0\},\,(j,0)\in E,\,T_{V,j}<\infty}(T_{V,j}+D_{j,0}) (если таких j не существует, то не существует и решения задачи). Для того чтобы иметь возможность восстановить сам цикл, необходимо при решении подзадач сохранять номер предпоследней вершины в оптимальном пути.

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

Кодирование множеств

Рассмотрим способ, при помощи которого можно организовать работу с множествами. Пусть у нас есть N объектов, пронумерованных от 0 до N-1 (неважно, какой природы эти объекты). Очевидно, что для каждого объекта нам нужно хранить ровно 1 бит информации – флаг его наличия в множестве. Запишем набор битов, задающих некоторое множество, слева направо в порядке убывания номера элемента. Полученная последовательность есть, по сути, двоичное число. Переведём его в десятичную систему счисления. Получили десятичное число, которое однозначно задаёт наше множество и может принимать значения от 0 до 2^N-1. Видно, что таким образом можно закодировать только множества, содержащие небольшое число элементов. Однако такой способ весьма удобен, поскольку позволяет использовать множества для, например, индексирования массивов и, кроме того, позволяет избежать неэффективного расходования памяти, которое имеет место при кодировании множеств булевыми массивами.

В задаче нам понадобится выполнять две основные операции над множествами: проверка принадлежности элемента множеству и удаление элемента из множества. Пусть мы работаем с множеством i и элементом j. Построим специальную битовую маску: число, j-ый бит которого – единица, а все остальные – нули. Это можно сделать, сдвинув единицу побитово на j позиций влево. Применим побитовую конъюнкцию к i и нашей битовой маске. Все биты результата, кроме j-ого, будут равны нулю, а j-ый бит сохранит то значение, которое имел в i. Соответственно, если j-ый бит в i был равен единице, то мы получим некоторый ненулевой результат, в противном случае – 0. Итак, чтобы проверить наличие элемента во множестве, достаточно сравнить число i&(1<<j) (синтаксис языков C/C++) с нулём. Аналогично можно убедиться в том, что если j-ый бит в i установлен в единицу, то установить его в ноль можно с использованием операции «исключающее или»: i=i^(1<<j) (второй вариант — конъюнкция с инвертированной маской: i=i&~(1<<j)). Видно, что каждая из операций над множествами имеет асимптотическую сложность O(1).

Автор статьи — Сухов Сергей

  • Артём

    ошибка: min — идентификатор не найден

Научиться программировать

  • на Delphi

  • на Java

  • на C++