Задача про покриття множини

Прикладом задачі про покриття множини є така задача: уявімо собі, що для виконання якогось завдання потрібен певний набір навичок ${\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)}$ разів перевищує розмір мінімального покриття.

Спрощений приклад роботи жадібного алгоритму для 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}}$. Далі піддається мутації, після чого з нього будується особина, яка заміняє в новій популяції покриття з найбільшою вагою. Оновлення популяції виконується деяке (задане) число разів, і результатом роботи алгоритму є найкраще зі знайдених покриттів.

Часто задача про покриття множини формулюється як задача цілочисельного програмування[1]:

Потрібно знайти ${\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}$ обмежені константою, задача за поліноміальний час розв'язується методами повного перебору.