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

Материал из 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^(1<<i)][to])$
  
 
Восстановление ответа делается также, как и в обычной динамике
 
Восстановление ответа делается также, как и в обычной динамике

Версия 09:21, 15 декабря 2019

Идея

Мы уже знаем, что такое маска, это способ закодировать множество в виде двоичного числа. Давайте теперь будем считать 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^(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, то такого пути нет, иначе есть

Как поменяется формула перехода, так как мы теперь храним маску, то нам нужно знать только можем ли мы прийти из вершины $to$, но тогда просто проверим $(dp[mask^(1<<i)][to])$, если она равна 0 то не можем, иначе сделаем $dp[mask][i] |= (1 << i)$



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

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