26.03.2022

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


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

  • X ← U {displaystyle Xleftarrow U}
  • C ← ∅ {displaystyle Cleftarrow varnothing }
  • while X ≠ ∅ {displaystyle X ot =varnothing } do
  • выбираем S ∈ F {displaystyle Sin F} с наибольшим ∣ X ∩ S ∣ {displaystyle mid Xcap Smid }
  • X ← X ∖ S {displaystyle Xleftarrow Xsetminus S}
  • C ← C ∪ { S } {displaystyle Cleftarrow Ccup {S}}
  • return C {displaystyle C}
  • Можно показать, что этот алгоритм работает с точностью 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} ограничены константой, задача за полиномиальное время решается методами полного перебора.

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

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





    Яндекс.Метрика