ДП по подмножествам: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
 
Строка 10: Строка 10:
  
 
Пусть $dp[mask][i]$ - Размер минимального пути, который по одному разу посетил все вершины из $mask$ и закончил в $i$-й вершине, тогда база динамики - $dp[(1 << i)][i] = 0$, ответ же будет - $min_{i = 0}^n(dp[(1 << n) - 1][i])$, так как нам подходит путь, кончающийся в любой вершине.  
 
Пусть $dp[mask][i]$ - Размер минимального пути, который по одному разу посетил все вершины из $mask$ и закончил в $i$-й вершине, тогда база динамики - $dp[(1 << i)][i] = 0$, ответ же будет - $min_{i = 0}^n(dp[(1 << n) - 1][i])$, так как нам подходит путь, кончающийся в любой вершине.  
Теперь рассмотрим переходы. Мы могли попасть в состояние $dp[mask][i]$, только из вершины которая есть в маске, тогда переход динамики очень прост : $dp[mask][i] = min_{to \ \in \ mask}(dp[mask^(1<<i)][to])$
+
Теперь рассмотрим переходы. Мы могли попасть в состояние $dp[mask][i]$, только из вершины которая есть в маске, тогда переход динамики очень прост : $dp[mask][i] = min_{to \ \in \ mask}(dp[mask \bigoplus (1<<i)][to])$
  
 
Восстановление ответа делается также, как и в обычной динамике
 
Восстановление ответа делается также, как и в обычной динамике

Текущая версия на 19:13, 28 января 2021

Идея

Мы уже знаем, что такое маска, это способ закодировать множество в виде двоичного числа. Давайте теперь будем считать dp[mask] - ответ для маски в какой-то задачу, так как мы уже знаем ответ для всех подмасок данной маски, то мы можем как-то считать dp[mask] через dp[submask]], давайте разберемся как

Задача

Дан граф из $n$ вершин, требуется найти путь минимального веса, такой, что он проходит по всем вершинам и ни в какую вершину не заходит дважды.

Решение

Пусть $dp[mask][i]$ - Размер минимального пути, который по одному разу посетил все вершины из $mask$ и закончил в $i$-й вершине, тогда база динамики - $dp[(1 << i)][i] = 0$, ответ же будет - $min_{i = 0}^n(dp[(1 << n) - 1][i])$, так как нам подходит путь, кончающийся в любой вершине. Теперь рассмотрим переходы. Мы могли попасть в состояние $dp[mask][i]$, только из вершины которая есть в маске, тогда переход динамики очень прост : $dp[mask][i] = min_{to \ \in \ mask}(dp[mask \bigoplus (1<<i)][to])$

Восстановление ответа делается также, как и в обычной динамике

Оценка ассимптотики

Всего у нас $O(2^n \cdot n)$ состояний для каждого состояния мы считаем ответ за $O(n)$, итоговая асимптотика - $O(2^n \cdot n^2)$

Оптимизация

Пусть теперь нам нужно только проверить есть ли такой путь, тогда мы можем решать задачу за $O(2^n \cdot n)$. Пусть теперь $dp[mask]$ - маска всех вершин, где может заканчиваться путь по mask вершин, база динамики $dp[(1 << i)] = (1 << i)$, для ответа нужно проверить $dp[(1 << n) - 1]$, если она будет равна 0, то такого пути нет, иначе есть

Как поменяется формула перехода, так как мы теперь храним маску, то нам нужно знать только можем ли мы прийти из какой-то вершины, но тогда просто проверим (dp[mask ^ (1 << i)]), если она не равна 0 и при этом из какой-то вершины маски (dp[mask ^ (1 << i)]) есть ребро до вершины i, сделаем dp[mask] |= (1 << i), иначе вершина $i$ не может быть последней, (теперь нужно за O(1) проверять всех соседей вершины, можно например считать, что $g[i] =$ маска всех соседей $i$ вершины и тогда проверка будет просто dp[mask ^ (1 << i)] & g[i], так как если какой-то бит равен 1 в dp[mask ^ (1 << i)] & g[i], тогда это значит, что она сосед $i$ и при этом она есть в маске dp[mask ^ (1 << i)]) так как мы перебираем все маски и для каждой перебираем каждую вершину, итоговая асимптотика - $O(2^n \cdot n)$



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin