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