ДП на подмножествах

Проблема представления подмножеств

Пусть у нас есть некоторое множество N = {0, 1, 2, ..., n - 1}, n ≤ 30

Мы хотим получить ответить на вопрос: " Как эффективно хранить и кодировать подмножества N?".

Битовые маски

Что такое битовые маски?

Подмножество будем кодировать с помощью двоичного числа, в котором на i-й позиции стоит 1, если i-й элемент множества входит в это подмножество, и 0 в противном случае.

Например, если есть множество А = {3, 5, 7, 9}, то его подмножество B = {3, 7, 9} можно закодировать с помощью маски 1011₂ = 11₁₀. Таким образом, если мы будем кодировать подмножества с помощью десятичного числа типа unsigned int, то сможем закодировать любое подмножество, размер которого не больше 32х.

Как работать с множествами, с помощью масок?

Вот так на языке С будет выглядеть функция проверяющая, входит ли элемент множества, стоящий на позиции pos в подмножество с маской mask:

   bool elem_in_subset (unsigned int mask, int pos) {
       return (mask >> pos) & 1;
   }

Похожим образом выглядят функции добавления и удаления элемента из подмножества. Для подсчета количества элементов в подмножестве подойдет функция __builtin_popcount (mask), которая возвращает количество единичных битов в двоичном представлении mask. Пересечение и объединение подмножеств соответствует побитовому пересечению и побитовому объединению масок, соответствующих данным подмножествам.

ДП на подмножествах

Задача о гамильтоновом цикле

1) Пусть есть неориентированный взвешенный граф (можно считать, что между любыми двумя вершинами есть ребро). Необходимо найти гамильтонов цикл наименьшего веса.

Наивное решение

Наивное решение заключается в полном переборе всех гамильтонов циклов и выборе из них цикла с наименьшей стоимостью. Количество циклов равно n! (количество перестановок вершин). Решение можно улучшить до O ($\frac {(n-1)!}{2}$), если заметить, что нам не важно из какой вершины начинать обход и в какую сторону обходить.

Оптимизация наивного решения с помощью ДП

Заведем массив dp такой, что dp[mask][v] - минимальная длина пути из 0-й вершины в вершину v, проходящий только по вершинам из множества mask ровно по одному разу.