Изменения
→Динамическое программирование по подмножествам
<tex>dp[pos][i] = \mathcal {1} </tex> во всех остальных случаях.
Теперь искомая минимальная длина пути <tex> p_{min} = min_{i \in [0...n-1]}\begin{bmatrixBmatrix}dp[2^n - 1][i] \end{bmatrixBmatrix}
</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>. Продолжая процесс пока не останется одна вершина, мы найдем весь гамильтонов путь.
