Изменения
→Оптимизация решения
Сама динамика будет такая: <br>
<tex>d[mask][i] = 1</tex>, если <tex>\left\{\begin{array}{llcl}1&;\ |mask| = 1</tex> и <tex>,\ mask_i = 1</tex> <br>\\<tex>d[mask][i] = \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> &;\ во всех остальных случаях \\\end{array}\right.<br/tex>
Это решение требует <tex>O(2^nn)</tex> памяти и <tex>O(2^nn^2)</tex> времени. Эту оценку можно улучшить, если изменить динамику следующим образом.
Тогда динамика перепишется следующим образом: <br>
<tex>d'[mask] [i] = 2\left\{\begin{array}{llcl}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> &;\ во всех остальных случаях \\\end{array}\right.<br/tex>
Особое внимание следует уделить выражению <tex>d[mask \oplus 2^i] \& M_i</tex> . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве <tex>mask</tex> без вершины <tex>i</tex>, а вторая — подмножество вершин, связанных с <tex>i</tex> ребром. Если эти множества пересекаются хотя бы по одной вершине (их <tex>\&</tex> не равен <tex>0</tex>), то, как нетрудно понять, в <tex>mask</tex> существует гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.
