Задача о покрытии множества

Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому является NP-сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в приближённом алгоритме, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм. Даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно медленно, поэтому такой подход можно считать полезным.

Формулировка задачи

Исходными данными задачи о покрытии множества является конечное множество ${\mathcal {U}}$ и семейство ${\mathcal {S}}$ его подмножеств. Покрытием называют семейство ${\mathcal {C}}\subseteq {\mathcal {S}}$ наименьшей мощности, объединением которых является ${\mathcal {U}}$. В случае постановки вопроса о разрешении на вход подаётся пара $({\mathcal {U}},{\mathcal {S}})$ и целое число $k$; вопросом является существование покрывающего множества мощности $k$ (или менее).

Пример

В качестве примера задачи о покрытии множества можно привести следующую проблему: представим себе, что для выполнения какого-то задания необходим некий набор навыков $S$. Также есть группа людей, каждый из которых владеет некоторыми из этих навыков. Необходимо сформировать наименьшую подгруппу, достаточную для выполнения задания, т. е. включающую в себя носителей всех необходимых навыков.

Методы решения

Жадный приближенный алгоритм

Жадный алгоритм выбирает множества, руководствуясь следующим правилом: на каждом этапе выбирается множество, покрывающее максимальное число ещё не покрытых элементов.

Greedy-Set-Cover(U,F), где $U$ — заданное множество всех элементов, $F$ — семейство подмножеств $U$

1. $X\leftarrow U$
2. $C\leftarrow \varnothing$
3. while $X\not =\varnothing$ do
   1. выбираем $S\in F$ с наибольшим $\mid X\cap S\mid$
   2. $X\leftarrow X\setminus S$
   3. $C\leftarrow C\cup \{S\}$
4. return $C$

Можно показать, что этот алгоритм работает с точностью $O(H(s))$, где $s$ — мощность наибольшего множества, а $H(n)$ — это сумма первых $n$ членов гармонического ряда.

$H(n)=\sum _{k=1}^{n}{\frac {1}{k}}\leq \ln {n}+1$

Другими словами, алгоритм находит покрытие, размер которого не более чем в $H(s)$ раз превосходит размер минимального покрытия.

Теорема Фейге гласит, что для задачи о покрытии множества не существует алгоритма с фактором аппроксимации $(1-\epsilon )\cdot H(n)$, т.к. иначе класс сложности NP был бы равен классу сложности TIME($n^{O(\log \log n)}$). Таким образом жадный алгоритм - лучший аппроксимационный алгоритм для задачи о покрытии множества.

Упрощённый пример работы жадного алгоритма для k = 3

Существует стандартный пример, на котором жадный алгоритм работает с точностью $\log _{2}(n)/2$.

Универсум состоит из $n=2^{(k+1)}-2$ элементов. Набор множеств состоит из $k$ попарно не пересекающихся множеств $S_{1},\ldots ,S_{k}$, мощности которых $2,4,8,\ldots ,2^{k}$ соответственно. Также имеются два непересекающихся множества $T_{0},T_{1}$, каждое из которых содержит половину элементов из каждого $S_{i}$. На таком наборе жадный алгоритм выбирает множества $S_{k},\ldots ,S_{1}$, тогда как оптимальным решением является выбор множеств $T_{0}$ и $T_{1}$ Пример подобных входных данных для $k=3$ можно увидеть на рисунке справа.

Генетический алгоритм

Генетический алгоритм представляет собой эвристический метод случайного поиска, основанный на принципе имитации эволюции биологической популяции.

В общем случае в процессе работы алгоритма происходит последовательная смена популяций, каждая из которых является семейством покрытий, называемых особями популяции. Покрытия начальной популяции строятся случайным образом. Наиболее распространённая и лучше всего зарекомендовавшая себя — стационарная схема генетического алгоритма, в которой очередная популяция отличается от предыдущей лишь одной или двумя новыми особями. При построении новой особи из текущей популяции с учётом весов покрытий выбирается «родительская» пара особей $J^{\prime },J''$, и на их основе в процедуре кроссинговера (случайно или детерминированно) формируется некоторый набор покрывающих множеств $J_{x}$. Далее подвергается мутации, после чего из него строится особь, которая замещает в новой популяции покрытие с наибольшим весом. Обновление популяции выполняется некоторое(заданное) число раз, и результатом работы алгоритма является лучшее из найденных покрытий.

Точное решение

Часто задача о покрытии множества формулируется, как задача целочисленного программирования:

Требуется найти $f^{*}(c,A)=\min\{(c,x)|Ax\geq e,x\in \{0,1\}^{n}\}$, где $A$ — $(m\times n)$ матрица, причём $a_{ij}$ = 1, если $i\in S_{j}$, и $a_{ij}$ = 0 в противном случае; $e$ обозначает $m$ — вектор из единиц; $c=(c_{1},c_{2},\dots ,c_{n})^{T}$; $x=(x_{1},x_{2},\dots ,x_{n})^{T}$ — вектор, где $x_{j}=1$, если $S_{j}$ входит в покрытие, иначе $x_{j}=0$.

Точное решение может быть получено за полиномиальное время, в случае, когда матрица $A$ вполне унимодулярна. Сюда можно отнести и задачу о вершинном покрытии на двудольном графе и дереве. В частности, когда каждый столбец матрицы $A$ содержит ровно две единицы, задачу можно рассматривать как задачу рёберного покрытия графа, которая эффективно сводится к поиску максимального паросочетания. На классах задач, где $n$ или $m$ ограничены константой, задача за полиномиальное время решается методами полного перебора.

Схожие задачи

• Задача о вершинном покрытии
• Задача о назначении минимума исполнителей

Литература

• А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования. Дискретный анализ и исследование операций. Сер. 2. 2000. Т. 7, N 2. С.22-46.
• Томас Х. Кормен и др. Глава 16. Жадные алгоритмы // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 1-е изд. — М.: Московского центра непрерывного математического образования, 2001. — С. 889-892. — ISBN 5-900916-37-5.

Ссылки

• Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination