Изменения
Нет описания правки
Иначе идем дальше. Тогда:
<tex> dp[i][m] = min_{m_im_j=1,(j, i)\in E} \begin{Bmatrix} d(j, i) + dp[j][m - 2^j] \end{Bmatrix}</tex>
Теперь искомая минимальная длина пути <tex> p_{min} = min_{i \in dp[0...n-1]}\begin{Bmatrix}dp[2^n - 1][i] \end{Bmatrix} </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>. Продолжая процесс пока не останется одна вершина, мы найдем весь гамильтонов путь.
