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

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

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

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

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

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

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

Можно предположить, что для решения задачи необходимо просто сгенерировать все [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]. Необходимо найти гамильтонов путь, сумма весов по ребрам которого минимальна.

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

Динамика считается по следующим соотношениям: dp[pos][i] = 0, если count(pos) = 1 и bit(i, pos) = 1; , если count(pos) > 1 и bit(i, pos) = 1; dp[pos][i] = ∞ во всех остальных случаях.

Теперь искомая минимальная длина пути. Если pmin = ∞, то гамильтонова пути в графе, нет. Восстановить сам путь несложно. Пусть минимальный путь заканчивается в вершине i. Тогда j ≠ i, для которого , является предыдущей вершиной пути. Теперь удалим i из множества и только что описанным способом найдем вершину предыдущую к j. Продолжая процесс пока не останется одна вершина, мы найдем весь гамильтонов путь.

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