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

Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает 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} \le \ln{n} +1$

Упрощённый пример работы жадного алгоритма для 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 \le 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