Изменения
Нет описания правки
Для того, чтобы восстановить сам путь, воспользуемся соотношением <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>.
==== Оптимизация решения ====
Тут можно обойтись решением 2, заменив сумму на побитовое ИЛИ. Тогда dp[mask][i] будет содержать булево значение - существует ли в подмножестве mask гамильтонов путь, заканчивающийся в вершине i. Сама динамика будет такая:
dp[mask][i] = 1, если count(mask) = 1 и bit(i, mask) = 1;
, если count(mask) > 1 и bit(i, mask) = 1;
dp[mask][i] = 0 во всех остальных случаях.
Это решение, как и решение 2, требует O(2nn) памяти и O(2nn2) времени. Эту оценку можно улучшить, если изменить динамику следующим образом.
Пусть dp'[mask] хранит маску подмножества всех вершин, для которых существует гамильтонов путь в подмножестве mask, заканчивающихся в этой вершине. Другими словами, сожмем предыдущую динамику: dp'[mask] будет равно . Для графа G выпишем n масок Mi, для каждой вершины задающие множество вершин, которые связаны ребром в данной вершиной. То есть .
Тогда динамика перепишется следующим образом:
dp'[mask] = 2i, если count(mask) = 1 и bit(i, mask) = 1;
, если count(mask) > 1;
dp'[mask] = 0 во всех остальных случаях.
Особое внимание следует уделить выражению . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве mask без вершины i, а вторая - подмножество вершин, связанных с i ребром. Если эти множества пересекаются хотя бы по одной вершине (их and не равен 0), то, как нетрудно понять, в mask существует гамильтонов путь, заканчивающийся в вершине i.
Окончательная проверка состоит в сравнении dp[2n - 1] c 0.
Это решение использует O(2n) памяти и имеет асимптотику O(2nn).
== Реализация ==
