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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

Примечания

1. Uriel Feige. A threshold of ln n for approximating set cover (англ.) // Journal of the ACM. — 1998-07. — Vol. 45, iss. 4. — P. 634–652. — ISSN 1557-735X 0004-5411, 1557-735X. — doi:10.1145/285055.285059. Архивировано 23 августа 2022 года.
2. А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов. ЗАДАЧА О ПОКРЫТИИ МНОЖЕСТВА: СЛОЖНОСТЬ, АЛГОРИТМЫ, ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ // ДИСКРЕТНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ. — 2000. — Июль—декабрь (т. 7, № 2). — С. 22-46. Архивировано 25 января 2021 года.

Ссылки

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