Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому является NP-сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в приближённом алгоритме, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм. Даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно медленно, поэтому такой подход можно считать полезным.
Исходными данными задачи о покрытии множества является конечное множество U {\displaystyle {\mathcal {U}}} и семейство S {\displaystyle {\mathcal {S}}} его подмножеств. Покрытием называют семейство C ⊆ S {\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}} наименьшей мощности, объединением которых является U {\displaystyle {\mathcal {U}}} . В случае постановки вопроса о разрешении на вход подаётся пара ( U , S ) {\displaystyle ({\mathcal {U}},{\mathcal {S}})} и целое число k {\displaystyle k} ; вопросом является существование покрывающего множества мощности k {\displaystyle k} (или менее).
В качестве примера задачи о покрытии множества можно привести следующую проблему: представим себе, что для выполнения какого-то задания необходим некий набор навыков S {\displaystyle S} . Также есть группа людей, каждый из которых владеет некоторыми из этих навыков. Необходимо сформировать наименьшую подгруппу, достаточную для выполнения задания, т. е. включающую в себя носителей всех необходимых навыков.
Жадный алгоритм выбирает множества, руководствуясь следующим правилом: на каждом этапе выбирается множество, покрывающее максимальное число ещё не покрытых элементов.
Greedy-Set-Cover(U,F), где U {\displaystyle U} — заданное множество всех элементов, F {\displaystyle F} — семейство подмножеств U {\displaystyle U}
Greedy-Set-Cover(U,F)
while
do
return
Можно показать, что этот алгоритм работает с точностью O ( H ( s ) ) {\displaystyle O(H(s))} , где s {\displaystyle s} — мощность наибольшего множества, а H ( n ) {\displaystyle H(n)} — это сумма первых n {\displaystyle n} членов гармонического ряда.
Другими словами, алгоритм находит покрытие, размер которого не более чем в H ( s ) {\displaystyle H(s)} раз превосходит размер минимального покрытия.
Теорема Фейге гласит, что для задачи о покрытии множества не существует алгоритма с фактором аппроксимации ( 1 − ϵ ) ⋅ H ( n ) {\displaystyle (1-\epsilon )\cdot H(n)} , т.к. иначе класс сложности NP был бы равен классу сложности TIME( n O ( log log n ) {\displaystyle n^{O(\log \log n)}} ).[1] Таким образом жадный алгоритм - лучший аппроксимационный алгоритм для задачи о покрытии множества.
Существует стандартный пример, на котором жадный алгоритм работает с точностью log 2 ( n ) / 2 {\displaystyle \log _{2}(n)/2} .
Универсум состоит из n = 2 ( k + 1 ) − 2 {\displaystyle n=2^{(k+1)}-2} элементов. Набор множеств состоит из k {\displaystyle k} попарно не пересекающихся множеств S 1 , … , S k {\displaystyle S_{1},\ldots ,S_{k}} , мощности которых 2 , 4 , 8 , … , 2 k {\displaystyle 2,4,8,\ldots ,2^{k}} соответственно. Также имеются два непересекающихся множества T 0 , T 1 {\displaystyle T_{0},T_{1}} , каждое из которых содержит половину элементов из каждого S i {\displaystyle S_{i}} . На таком наборе жадный алгоритм выбирает множества S k , … , S 1 {\displaystyle S_{k},\ldots ,S_{1}} , тогда как оптимальным решением является выбор множеств T 0 {\displaystyle T_{0}} и T 1 {\displaystyle T_{1}} Пример подобных входных данных для k = 3 {\displaystyle k=3} можно увидеть на рисунке справа.
Генетический алгоритм представляет собой эвристический метод случайного поиска, основанный на принципе имитации эволюции биологической популяции.
В общем случае в процессе работы алгоритма происходит последовательная смена популяций, каждая из которых является семейством покрытий, называемых особями популяции. Покрытия начальной популяции строятся случайным образом. Наиболее распространённая и лучше всего зарекомендовавшая себя — стационарная схема генетического алгоритма, в которой очередная популяция отличается от предыдущей лишь одной или двумя новыми особями. При построении новой особи из текущей популяции с учётом весов покрытий выбирается «родительская» пара особей J ′ , J ″ {\displaystyle J^{\prime },J''} , и на их основе в процедуре кроссинговера (случайно или детерминированно) формируется некоторый набор покрывающих множеств J x {\displaystyle J_{x}} . Далее подвергается мутации, после чего из него строится особь, которая замещает в новой популяции покрытие с наибольшим весом. Обновление популяции выполняется некоторое(заданное) число раз, и результатом работы алгоритма является лучшее из найденных покрытий.
Часто задача о покрытии множества формулируется, как задача целочисленного программирования[2]:
Требуется найти f ∗ ( c , A ) = min { ( c , x ) | A x ≥ e , x ∈ { 0 , 1 } n } {\displaystyle f^{*}(c,A)=\min\{(c,x)|Ax\geq e,x\in \{0,1\}^{n}\}} , где A {\displaystyle A} — ( m × n ) {\displaystyle (m\times n)} матрица, причём a i j {\displaystyle a_{ij}} = 1, если i ∈ S j {\displaystyle i\in S_{j}} , и a i j {\displaystyle a_{ij}} = 0 в противном случае; e {\displaystyle e} обозначает m {\displaystyle m} — вектор из единиц; c = ( c 1 , c 2 , … , c n ) T {\displaystyle c=(c_{1},c_{2},\dots ,c_{n})^{T}} ; x = ( x 1 , x 2 , … , x n ) T {\displaystyle x=(x_{1},x_{2},\dots ,x_{n})^{T}} — вектор, где x j = 1 {\displaystyle x_{j}=1} , если S j {\displaystyle S_{j}} входит в покрытие, иначе x j = 0 {\displaystyle x_{j}=0} .
Точное решение может быть получено за полиномиальное время, в случае, когда матрица A {\displaystyle A} вполне унимодулярна. Сюда можно отнести и задачу о вершинном покрытии на двудольном графе и дереве. В частности, когда каждый столбец матрицы A {\displaystyle A} содержит ровно две единицы, задачу можно рассматривать как задачу рёберного покрытия графа, которая эффективно сводится к поиску максимального паросочетания. На классах задач, где n {\displaystyle n} или m {\displaystyle m} ограничены константой, задача за полиномиальное время решается методами полного перебора.