Задача про покриття множини є класичним питанням інформатики і теорії складності. Ця задача узагальнює 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)} разів перевищує розмір мінімального покриття.
Існує стандартний приклад, на якому жадібний алгоритм працює з точністю 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}} . Далі піддається мутації, після чого з нього будується особина, яка заміняє в новій популяції покриття з найбільшою вагою. Оновлення популяції виконується деяке (задане) число разів, і результатом роботи алгоритму є найкраще зі знайдених покриттів.
Часто задача про покриття множини формулюється як задача цілочисельного програмування[1]:
Потрібно знайти 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} обмежені константою, задача за поліноміальний час розв'язується методами повного перебору.