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

Задача о коммивояжере (англ. 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]0[/math] до [math]N-1[/math] и каждое ребро [math](i, j) \in E [/math] имеет некоторый вес [math] d(i, j)[/math]. Необходимо найти гамильтонов цикл, сумма весов по ребрам которого минимальна.

Зафиксируем начальную вершину [math]s[/math] и будем искать гамильтонов цикл наименьшей стоимости - путь от [math]s[/math] до [math]s[/math], проходящий по всем вершинам(кроме первоначальной) один раз. Т.к. искомый цикл проходит через вершину, то выбор [math]s[/math] не имеет значения. Поэтому будем считать [math]S = 0 [/math].

Подмножества вершин будем кодировать битовыми векторами, обозначим [math]m_i[/math] значение [math]i[/math]-ого бита в векторе [math]m[/math].

Обозначим [math]dp[i][m][/math] как наименьшую стоимость пути из вершины [math]i[/math] в вершину [math]S[/math], проходящую (не считая вершины [math]i[/math]) единожды по всем тем и только тем вершинам [math]j[/math], для которых [math]m_j = 1[/math] (т.е. [math]m[/math] - подмножество вершин исходного графа, которые осталось посетить).

Конечное состояние - когда находимся в 0-й вершине, все вершины посещены (т.е. [math]i = 0[/math], [math]m = 0[/math]). Для остальных состояний перебираем все возможные переходы из i-й вершины в одну из непосещенных ранее и выбираем способ, дающий минимальный результат. Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как [math]\infty[/math]).

То есть, [math]dp[i][m][/math] считается по следующим соотношениям:

[math]dp[i][m] = 0[/math], если [math]i = 0[/math] и [math]m = 0[/math]

Иначе

[math]dp[i][m] = min_{j: m_j=1, (i, j) \in E} \begin{Bmatrix} d(i, j) + dp[j][m - 2^j] \end{Bmatrix}[/math], если [math]i\neq 0[/math] и [math] m \neq 0 [/math]

[math]dp[i][m] = \infty [/math], если [math]i \neq 0[/math], [math]m\neq0[/math] и множество возможных переходов пусто.

Стоимостью минимального гамильтонова цикла в исходном графе будет значение [math] dp[0][2^n-1][/math] - стоимость пути из [math]0[/math]-й вершины в [math]0[/math]-ю, при необходимости посетить все вершины.

Восстановить сам цикл несложно. Для этого воспользуемся соотношением [math] dp[i][m] = d(i, j) + dp[j][m - 2^j] [/math] . Начнем с состояния [math] i = 0 [/math],[math] m = 2^n - 1[/math], найдем вершину [math]j[/math], для которой выполняется указанное соотношение, добавим [math]j[/math] в ответ, пересчитаем текущее состояние как [math]i = j[/math], [math] m = m - 2^j [/math]. Процесс заканчивается в состоянии [math]i = 0[/math], [math] m = 0 [/math].

Тогда [math] j \neq i[/math], для которого [math] dp[0][2^n - 1] = d(i, j) + dp[j][m - 2^j] [/math] , является предыдущей вершиной пути. Теперь удалим [math]i[/math] из множества и только что описанным способом найдем вершину предыдущую к [math]j[/math]. Продолжая процесс пока не останется одна вершина, мы найдем весь гамильтонов путь.

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

Источники

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

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

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

Problem_des_Handlungsreisenden;