Задача коммивояжера, ДП по подмножествам

Задача о коммивояжере (англ. travelling - salesman problem) - это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из [math] N [/math] точек на плоскости.

Формулировка задачи

Коммивояжер должен посетить [math] N [/math] городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?

Представление

Чтобы использовать математические процессы для решения, реальная ситуация должна отображаться сначала простой моделью. Задачу коммивояжера можно смоделировать с помощью графа. При этом вершины можно считать городами, в то время как каждая дуга [math](i, j) [/math] описывает связь между этими 2 вершинами [math]i[/math] и [math]j[/math]. Каждая дуга имеет свой вес [math] с(i, j) [/math]. Поездка - это цикл в этом графе, который проходит через каждую вершину ровно один раз. Целью является найти более короткую поездку.

Варианты решения

Решение перебором

Можно предположить, что для решения задачи необходимо просто сгенерировать все [math] N! [/math] всевозможных перестановок вершин полного графа, подсчитать для перестановки длину маршрута и выбрать минимальный. Но тогда задача оказывается неосуществимой даже для достаточно небольших [math]N[/math].

Так же известно, что задача о коммивояжере относится к NP-полным задачам.

Динамическое программирование по подмножествам

Задача о коммивояжере сводится к поиску кратчайшего гамильтонова пути в графе.

Смоделируем данную задачу при помощи графа. При этом вершины можно считать городами, а ребра - дорогами. Пусть в графе [math] P = (V, E)[/math] [math] N [/math] вершин и каждое ребро [math](i, j) \in E [/math] имеет некоторый вес [math] d(i, j)[/math]. Необходимо найти гамильтонов путь, сумма весов по ребрам которого минимальна.

Пусть множество элементов занумеровано и закодировано последовательностью битов длины [math] N [/math]. Элементами множества будут являться вершины графа. Для простоты мы будем считать, что граф является неориентированным.

[math] bit(i, pos) [/math] - [math]i[/math]-й бит последовательности [math]pos[/math].

[math] count(pos)[/math] - количество битов [math]1[/math] в последовательности [math]pos[/math].

Если [math]i[/math]-й бит последовательности равен [math]1[/math], то [math]i[/math]-й элемент входит в подмножество, иначе - нет.

Пусть [math] dp[pos][i] [/math] обозначает длину кратчайшего гамильтонова пути подмножества вершин [math]pos [/math], заканчивающегося в вершине [math] i [/math].

Динамика считается по следующим соотношениям:

[math] dp[pos][i] = 0 [/math], если [math] count(pos) = 1[/math] и [math] bit(i, pos) = 1[/math];

[math] dp[pos][i] = min_{bit(j, pos)=1,(j, i)\in E} \begin{Bmatrix} dp[pos \oplus 2^i][j]+d(j, i) \end{Bmatrix}[/math], если [math] count(pos) \gt  1 [/math] и [math] bit(i, pos) = 1[/math];

[math]dp[pos][i] = \mathcal {1} [/math] во всех остальных случаях.

Теперь искомая минимальная длина пути [math] p_{min} = min_{i \in [0...n-1]}\begin{Bmatrix}dp[2^n - 1][i] \end{Bmatrix} [/math]. Если [math] p_{min} = \mathcal {1} [/math], то гамильтонова пути в графе, нет. Восстановить сам путь несложно. Пусть минимальный путь заканчивается в вершине [math]i[/math]. Тогда [math] j \neq i[/math], для которого [math] dp[2^n - 1][i] = dp[2^n - 1 \oplus 2^i][j] + d(j, i) [/math] , является предыдущей вершиной пути. Теперь удалим [math]i[/math] из множества и только что описанным способом найдем вершину предыдущую к [math]j[/math]. Продолжая процесс пока не останется одна вершина, мы найдем весь гамильтонов путь.

Данное решение требует [math]O(2n^n)[/math] памяти и [math]O(2^nn^2)[/math] времени.

Источники

И.В.Романовский - Дискретный анализ;

Корман, Риверст, Лейзерсон, Штайн - Алгоритмы: построение и анализ;

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

Problem_des_Handlungsreisenden;