Изменения
→Оптимизация решения
Сама динамика будет такая: <br>
<tex>d[mask][i] = 1</tex>, если <tex>|mask| = 1</tex> и <tex>mask_i = 1</tex> <br>
<tex>d[mask][i] = OR_\bigvee_{mask[j]=1, (j, i) \in E}\limits d[mask \oplus 2^i][j]</tex>, если <tex>|mask| > 1</tex> и <tex>mask_i= 1</tex> <br>
<tex>d[mask][i] = 0</tex> во всех остальных случаях <br>
Это решение требует <tex>O(2^nn)</tex> памяти и <tex>O(2^nn^2)</tex> времени. Эту оценку можно улучшить, если изменить динамику следующим образом.
Пусть теперь <tex>d'[mask]</tex> хранит маску подмножества всех вершин, для которых существует гамильтонов путь в подмножестве <tex>mask</tex>, заканчивающихся в этой вершине. Другими словами, сожмем предыдущую динамику: <tex>d'[mask]</tex> будет равно <tex>\sum_{i \in [0..n-1]} \limits d[mask][i] \cdot 2 ^i </tex>. Для графа <tex>G</tex> выпишем <tex>n</tex> масок <tex>M_i</tex>, для каждой вершины задающие множество вершин, которые связаны ребром в данной вершиной. То есть <tex>M_i = \sum_{j \in [0..n-1]} \limits 2^i \cdot ((i, j) \in E ? 1:0) </tex>.
Тогда динамика перепишется следующим образом: <br>
<tex>d'[mask] = 2^i</tex>, если <tex>|mask| = 1</tex> и <tex>mask_i = 1</tex> <br>
<tex>d'[mask]=\sum_{j \in [0..n-1]} \limits 2^i \cdot ((d[mask \oplus 2^i] \& M_i) \neq 0?1:0) </tex>, если <tex>|mask|> 1</tex> <br>
<tex>dp'[mask] = 0</tex> во всех остальных случаях <br>
