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

Задача о коммивояжере (англ. 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]-й бит последовательности pos

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

Пусть [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 xor 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 ≠ i[/math], для которого , является предыдущей вершиной пути. Теперь удалим [math]i[/math] из множества и только что описанным способом найдем вершину предыдущую к [math]j[/math]. Продолжая процесс пока не останется одна вершина, мы найдем весь гамильтонов путь.

Данное решение требует O(2nn) памяти и O(2nn2) времени.