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