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

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

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

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

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

Задача о коммивояжере относится к классу NP-полных задач. Рассмотрим два варианта решения.

Перебор перестановок

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

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

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

Смоделируем данную задачу при помощи графа. При этом вершинам будут соответствовать города, а ребрам - дороги. Пусть в графе [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]0[/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]O(2^nn)[/math] памяти и [math]O(2^nn^2)[/math] времени.

Источники

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

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

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

• Задача коммивояжера в немецкой википедии;