Изменения
→Динамическое программирование по подмножествам (по маскам)
Обозначим <tex>d[i][mask]</tex> как наименьшую стоимость пути из вершины <tex>i</tex> в вершину <tex>0</tex>, проходящую (не считая вершины <tex>i</tex>) единожды по всем тем и только тем вершинам <tex>j</tex>, для которых <tex>mask_j = 1</tex> (т.е. <tex>d[i][mask]</tex> уже найденный оптимальный путь от <tex>i</tex>-ой вершины до <tex>0</tex>-ой, проходящий через те вершины, где <tex>mask_j=1</tex>. Если <tex>mask_j=0</tex>,то эти вершины еще не посещены).
*Начальное состояние - когда находимся в 0-й вершине, ни одна вершина не посещена, а пройденный путь равен <tex>0</tex> (т.е. <tex>i = 0</tex>, и <tex>mask = 0</tex>). *Для остальных состояний (<tex>i \ne 0</tex> или <tex>mask \ne 0</tex>) перебираем все возможные переходы в <tex>i</tex>-ую вершину из любой посещенной ранее и выбираем минимальный результат. *Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>).
То есть, <tex>d[i][mask]</tex> считается по следующему правилупринимает значения:
<tex> d[i][mask] =
\begin{cases}
0, &\text{if }i = 0\text{ and }mask = 0 \\ \min\limits_{j:\text{ }mask_j=1,\text{ }(i, j) \in E} \begin{Bmatrix} w(i, j) + d[j][mask - 2^j] \end{Bmatrix}, & \text{if } i\neq 0 \text{ or } mask \neq 0\\ \infty, & \text{if } i \neq 0 \text{ and } mask \neq 0 \text{ and } j:\text{ }mask_j=1,\text{ }(i, j) \notin E
\end{cases}
</tex>
