Изменения
Нет описания правки
Задача о коммивояжере (англ. '''travelling - salesman problem''') - это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из <tex> N </tex> точек на плоскости.
== Формулировка задачи ==
Подмножества вершин будем кодировать битовыми векторами, обозначим <tex>m_i</tex> значение <tex>i</tex>-ого бита в векторе <tex>m</tex>.
Обозначим <tex>dp[i][m]</tex> как наименьшую стоимость пути из вершины <tex>i</tex> в вершину <tex>S0</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] = 0</tex>, если <tex>i = 0</tex> и <tex>m = 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] = d(i, j) + dp[j][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>O(2^nn)</tex> памяти и <tex>O(2^nn^2)</tex> времени.
