Задача о коммивояжере сводится к поиску кратчайшего гамильтонова пути в графе.
Смоделируем данную задачу при помощи графа. При этом вершины можно считать городамивершинам будут соответствовать города, а ребра ребрам - дорогамидороги. Пусть в графе <tex> P = (V, E)</tex> <tex> N </tex>вершин , пронумерованных от <tex>0</tex> до <tex>N-1</tex> и каждое ребро <tex>(i, j) \in E </tex> имеет некоторый вес <tex> d(i, j)</tex>. Необходимо найти гамильтонов путьцикл, сумма весов по ребрам которого минимальна.
Пусть множество элементов занумеровано Зафиксируем начальную вершину <tex>s</tex> и закодировано последовательностью битов длины будем искать гамильтонов цикл наименьшей стоимости - путь от <tex> N s</tex>до <tex>s</tex>, проходящий по всем вершинам(кроме первоначальной) один раз. Т. Элементами множества будут являться вершины графак. Для простоты мы искомый цикл проходит через вершину, то выбор <tex>s</tex> не имеет значения. Поэтому будем считать, что граф является неориентированным<tex>S = 0 </tex>.
Пусть m Подмножества вершин будем кодировать битовыми векторами, обозначим <tex>m_i</tex> значение <tex>i</tex>- множество не посещенных вершин. Первоначальной стартовой позицией примем вершину с индексом ого бита в векторе <tex> 0 m</tex>.
Пусть Обозначим <tex> dp[i][m] </tex> обозначает длину кратчайшего гамильтонова как наименьшую стоимость пути подмножества вершин из вершины <tex>i</tex> в вершину <tex>pos S</tex>, заканчивающегося в вершине проходящую (не считая вершины <tex> i </tex>) единожды по всем тем и только тем вершинам <tex>j</tex>, для которых <tex>m_j = 1</tex> (т.е. <tex>m</tex> - подмножество вершин исходного графа, которые осталось посетить).
Конечное состояние - когда находимся в 0-й вершине, все вершины посещены (т.е. <tex>i = 0</tex>, <tex>m = 0</tex>). Для остальных состояний перебираем все возможные переходы из i-й вершины в одну из непосещенных ранее и выбираем способ, дающий минимальный результат. Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>).
Динамика То есть, <tex>dp[i][m]</tex> считается по следующим соотношениям:
Начинаем с нулевой вершины:<tex>dp[i][m] = 0</tex>, если <tex>i = 0</tex> и <tex>m = 0</tex>
<tex> dp[0][0] = 0 </tex>Иначе
Если же маска равна <tex>dp[i][m] = min_{j: m_j=1, (i, j) \in E} \begin{Bmatrix} d(i, j) + dp[j][m - 2^j] \end{Bmatrix}</tex>, если <tex>i\neq 0</tex> и все вершины посещены, то ответ <tex>m \neq 0</tex>.
Иначе идем дальше<tex>dp[i][m] = \infty </tex>, если <tex>i \neq 0</tex>, <tex>m\neq0</tex> и множество возможных переходов пусто. Тогда:
Стоимостью минимального гамильтонова цикла в исходном графе будет значение <tex> dp[i0][m] = min_{m_j=2^n-1, (i, j) \in E} \begin{Bmatrix} d(i, j) + dp[j][m </tex> - стоимость пути из <tex>0</tex>- 2^j] \end{Bmatrix}й вершины в <tex>0</tex>-ю, при необходимости посетить все вершины.
Теперь искомая минимальная длина пути Восстановить сам цикл несложно. Для этого воспользуемся соотношением <tex> p_{min} dp[i][m] = d(i, j) + dp[0j][m - 2^j] </tex> . Начнем с состояния <tex> i = 0 </tex>,<tex> m = 2^n - 1] </tex>, найдем вершину <tex>j</tex>, для которой выполняется указанное соотношение, добавим <tex>j</tex> в ответ, пересчитаем текущее состояние как <tex>i = j</tex>, <tex> m = m - 2^j </tex>. Процесс заканчивается в состоянии <tex>i = 0</tex>, <tex> m = 0 </tex>.
Если <tex> p_{min} = 0 </tex>, то гамильтонова пути в графе, нет. Восстановить сам путь несложно. Пусть минимальный путь заканчивается в вершине <tex>i</tex>. Тогда <tex> j \neq i</tex>, для которого <tex> dp[0][2^n - 1] = d(i, j) + dp[j][m - 2^j] </tex> , является предыдущей вершиной пути. Теперь удалим <tex>i</tex> из множества и только что описанным способом найдем вершину предыдущую к <tex>j</tex>. Продолжая процесс пока не останется одна вершина, мы найдем весь гамильтонов путь.
Тогда <tex> j \neq i</tex>, для которого <tex> dp[0][2^n - 1] = d(i, j) + dp[j][m - 2^j] </tex> , является предыдущей вершиной пути. Теперь удалим <tex>i</tex> из множества и только что описанным способом найдем вершину предыдущую к <tex>j</tex>. Продолжая процесс пока не останется одна вершина, мы найдем весь гамильтонов путь.
Данное решение требует <tex>O(2n2^nnn)</tex> памяти и <tex>O(2^nn^2)</tex> времени.
== Источники ==
