ДП на подмножествах — различия между версиями
(→Описание проблемы) |
(Исправил опечатки) |
||
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Проблема представления подмножеств == | == Проблема представления подмножеств == | ||
| − | Пусть у нас есть некоторое | + | Пусть у нас есть некоторое множество N = {0, 1, 2, ..., n - 1}, n ≤ 30 <br><br> |
Мы хотим получить ответить на вопрос: " Как эффективно хранить и кодировать подмножества N?". | Мы хотим получить ответить на вопрос: " Как эффективно хранить и кодировать подмножества N?". | ||
| Строка 6: | Строка 6: | ||
===Что такое битовые маски?=== | ===Что такое битовые маски?=== | ||
Подмножество будем кодировать с помощью двоичного числа, в котором на i-й позиции стоит 1, если i-й элемент множества входит в это подмножество, и 0 в противном случае. <br><br> | Подмножество будем кодировать с помощью двоичного числа, в котором на i-й позиции стоит 1, если i-й элемент множества входит в это подмножество, и 0 в противном случае. <br><br> | ||
| − | + | Например, если есть множество А = {3, 5, 7, 9}, то его подмножество B = {3, 7, 9} можно закодировать с помощью маски 1011<sub>2</sub> = 11<sub>10</sub>. Таким образом, если мы будем кодировать подмножества с помощью десятичного числа типа <code>unsigned int</code>, то сможем закодировать любое подмножество, размер которого не больше 32х. | |
===Как работать с множествами, с помощью масок?=== | ===Как работать с множествами, с помощью масок?=== | ||
<p>Вот так на языке С будет выглядеть функция проверяющая, входит ли элемент множества, стоящий на позиции pos в подмножество с маской mask:</p> | <p>Вот так на языке С будет выглядеть функция проверяющая, входит ли элемент множества, стоящий на позиции pos в подмножество с маской mask:</p> | ||
| Строка 12: | Строка 12: | ||
return (mask >> pos) & 1; | return (mask >> pos) & 1; | ||
} | } | ||
| − | Похожим образом выглядят функции добавления и удаления элемента из подмножества. Для подсчета количества элементов в подмножестве | + | Похожим образом выглядят функции добавления и удаления элемента из подмножества. Для подсчета количества элементов в подмножестве подойдет функция <code>__builtin_popcount (mask)</code>, которая возвращает количество единичных битов в двоичном представлении mask. Пересечение и объединение подмножеств соответствует побитовому пересечению и побитовому объединению масок, соответствующих данным подмножествам. |
| + | ==ДП на подмножествах== | ||
| + | ===Задача о гамильтоновом цикле=== | ||
| + | 1) Пусть есть неориентированный взвешенный граф (можно считать, что между любыми двумя вершинами есть ребро). Необходимо найти [https://ru.wikipedia.org/wiki/%D0%93%D0%BB%D0%BE%D1%81%D1%81%D0%B0%D1%80%D0%B8%D0%B9_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2#%D0%9F гамильтонов цикл] наименьшего веса. | ||
| + | ====Наивное решение==== | ||
| + | Наивное решение заключается в полном переборе всех гамильтонов циклов и выборе из них цикла с наименьшей стоимостью. Количество циклов равно n! (количество перестановок вершин). Решение можно улучшить до O ($\frac {(n-1)!}{2}$), если заметить, что нам не важно из какой вершины начинать обход и в какую сторону обходить. | ||
| + | ====Оптимизация наивного решения с помощью ДП==== | ||
| + | Заведем массив <code>dp</code> такой, что <code>dp[mask][v]</code> - минимальная длина пути из 0-й вершины в вершину v, проходящий только по вершинам из множества mask ровно по одному разу. | ||
Текущая версия на 01:50, 15 мая 2020
Содержание
Проблема представления подмножеств
Пусть у нас есть некоторое множество N = {0, 1, 2, ..., n - 1}, n ≤ 30
Мы хотим получить ответить на вопрос: " Как эффективно хранить и кодировать подмножества N?".
Битовые маски
Что такое битовые маски?
Подмножество будем кодировать с помощью двоичного числа, в котором на i-й позиции стоит 1, если i-й элемент множества входит в это подмножество, и 0 в противном случае.
Например, если есть множество А = {3, 5, 7, 9}, то его подмножество B = {3, 7, 9} можно закодировать с помощью маски 10112 = 1110. Таким образом, если мы будем кодировать подмножества с помощью десятичного числа типа 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 ровно по одному разу.
