Задача о покрытии множества
Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает 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}
Можно показать, что этот алгоритм работает с точностью O ( H ( s ) ) {displaystyle O(H(s))} , где s {displaystyle s} — мощность наибольшего множества, а H ( n ) {displaystyle H(n)} — это сумма первых n {displaystyle n} членов гармонического ряда.
H ( n ) = ∑ k = 1 n 1 k ≤ ln n + 1 {displaystyle H(n)=sum _{k=1}^{n}{frac {1}{k}}leq ln {n}+1}Другими словами, алгоритм находит покрытие, размер которого не более чем в H ( s ) {displaystyle H(s)} раз превосходит размер минимального покрытия.
Существует стандартный пример, на котором жадный алгоритм работает с точностью 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}} . Далее подвергается мутации, после чего из него строится особь, которая замещает в новой популяции покрытие с наибольшим весом. Обновление популяции выполняется некоторое(заданное) число раз, и результатом работы алгоритма является лучшее из найденных покрытий.
Точное решение
Часто задача о покрытии множества формулируется, как задача целочисленного программирования:
Требуется найти f ∗ ( c , A ) = min { ( c , x ) | A x ≥ e , x ∈ { 0 , 1 } n } {displaystyle f^{*}(c,A)=min{(c,x)|Axgeq e,xin {0,1}^{n}}} , где A {displaystyle A} — ( m × n ) {displaystyle (m imes n)} матрица, причём a i j {displaystyle a_{ij}} = 1, если i ∈ S j {displaystyle iin 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} ограничены константой, задача за полиномиальное время решается методами полного перебора.
Схожие задачи
- Задача о вершинном покрытии
- Задача о назначении минимума исполнителей
