Изменения

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

Пусть множество элементов занумеровано и закодировано последовательностью битов длины <tex> N </tex>.  <tex> bit(i, pos) </tex> - <tex>i</tex>-й бит последовательности pos <tex> count(pos)</tex> - количество битов 1 в последовательности pos Пусть <tex> dp[pos][i] </tex> обозначает длину кратчайшего гамильтонова пути подмножества вершин <tex>pos</tex>, заканчивающегося в вершине <tex> i</tex>. 

<tex> dp[pos][i] = 0 </tex>, если <tex> count(pos) = 1</tex> и <tex> bit(i, pos) = 1</tex>; <tex> dp[pos][i] = min_{bit(j, pos)=1,(j, i)\in E} \begin{Bmatrix} dp[pos xor 2^i][j]+d(j, i) \end{Bmatrix}</tex>, если <tex> count(pos) > 1 </tex> и <tex> bit(i, pos) = 1</tex>; <tex>dp[pos][i] = \mathcal {1} </tex> во всех остальных случаях. Теперь искомая минимальная длина пути<tex> p_{min} = min_{i \in [0...n-1]}\begin{bmatrix}dp[2^n - 1][i] \end{bmatrix} </tex>. Если pmin <tex> p_{min} = ∞ \mathcal {1} </tex>, то гамильтонова пути в графе, нет. Восстановить сам путь несложно. Пусть минимальный путь заканчивается в вершине <tex>i</tex>. Тогда <tex> j ≠ i</tex>, для которого , является предыдущей вершиной пути. Теперь удалим <tex>i </tex> из множества и только что описанным способом найдем вершину предыдущую к <tex>j</tex>. Продолжая процесс пока не останется одна вершина, мы найдем весь гамильтонов путь.