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