1632
правки
Изменения
м
rollbackEdits.php mass rollback
то граф <tex> G </tex> [[Гамильтоновы графы|гамильтонов]].
}}
== Задача о коммивояжере ==
Для того, чтобы восстановить сам путь, воспользуемся соотношением <tex> d[i][mask] = w(i, j) + d[j][mask - 2^j] </tex>, которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния <tex> i = 0 </tex>, <tex> mask = 2^n - 1</tex>, найдем вершину <tex>j</tex>, для которой выполняется указанное соотношение, добавим <tex>j</tex> в ответ, пересчитаем текущее состояние как <tex>i = j</tex>, <tex> mask = mask - 2^j </tex>. Процесс заканчивается в состоянии <tex>i = 0</tex>, <tex> mask = 0 </tex>.
===== Оптимизация решения Поиск любого гамильтонова пути методом динамического программирования =====
Пусть <tex>d[mask][i]</tex> содержит булево значение — существует ли в подмножестве <tex>mask</tex> гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.
d'[mask] = \left\{\begin{array}{llcl}
mask &;\ |mask| = 1 \\
\sum_{i \in [0..n-1] \& mask_i=1}\limits 2^i \cdot ((d'[mask \oplus 2^i] \& M_i) \neq 0?1:0) &;\ |mask| > 1 \\
0&;\ otherwise\\
\end{array}\right.
</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>.
Окончательная проверка состоит в сравнении <tex>d'[2^n - 1]</tex> c <tex>0</tex>.
Это решение использует <tex>O(2^n)</tex> памяти и имеет асимптотику <tex>O(2^nn)</tex>.
