Изменения

<tex> bit(i, pos) </tex> - <tex>i</tex>Пусть m -й бит последовательности множество не посещенных вершин. Первоначальной стартовой позицией примем вершину с индексом <tex>pos0 </tex>.

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

<tex> dp[posi][im] = 0 </tex>, если <tex> count(pos) = 1</tex> и <tex> bit(i, pos) m_i = 1</tex>;

<tex> dp[posi][im] = min_{bit(j, pos)m_i=1,(j, i)\in E} \begin{Bmatrix} d(j, i) + dp[pos \oplus j][m - 2^i][j]+d(j, i) \end{Bmatrix}</tex>, если <tex> count(pos) > 1 </tex> и <tex> bit(i, pos) = 1</tex>;

</tex>.  Если <tex> p_{min} = \mathcal {1} </tex>, то гамильтонова пути в графе, нет. Восстановить сам путь несложно. Пусть минимальный путь заканчивается в вершине <tex>i</tex>. Тогда <tex> j \neq i</tex>, для которого <tex> dp[2^n - 1][i] = dp[2^n - 1 \oplus 2^i][j] + d(j, i) </tex> , является предыдущей вершиной пути. Теперь удалим <tex>i</tex> из множества и только что описанным способом найдем вершину предыдущую к <tex>j</tex>. Продолжая процесс пока не останется одна вершина, мы найдем весь гамильтонов путь.