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

Задача про покриття множини є класичним питанням інформатики і теорії складності. Ця задача узагальнює NP-повну задачу про вершинне покриття (і тому є NP-складною). Попри те, що задача про вершинне покриття подібна до цієї, підхід, використаний у наближеному алгоритмі, тут не працює. Замість цього ми розглянемо жадібний алгоритм. Отриманий за ним розв'язок буде гіршим від оптимального в логарифмічне число разів. Із зростанням розміру задачі якість розв'язку погіршується, але все ж досить повільно, тому такий підхід можна вважати корисним.

Формулювання задачі

Вхідними даними задачі про покриття множини є скінченна множина $𝒰$ і сімейство $𝒮$ її підмножин. Покриттям називають сімейство $𝒞\subseteq 𝒮$ найменшої потужності, об'єднанням яких є $𝒰$. В разі постановки питання про дозвіл на вхід подається пара $(𝒰,𝒮)$ і ціле число $k$; питанням є існування покривної множини з потужністю $k$ (або менше).

Приклад

Прикладом задачі про покриття множини є така задача: уявімо собі, що для виконання якогось завдання потрібен певний набір навичок $S$. Також є група людей, кожен з яких володіє деякими з цих навичок. Необхідно сформувати найменшу підгрупу, достатню для виконання завдання, тобто таку, що включає носіїв усіх необхідних навичок.

Методи розв'язування

Жадібний наближений алгоритм

Жадібний алгоритм вибирає множини керуючись таким правилом: на кожному етапі вибирається множина, що покриває найбільше число ще не покритих елементів.

Greedy-Set-Cover(U,F), де $U$ — задана множина всіх елементів, $F$ — сімейство підмножин $U$

1. $X\leftarrow U$
2. $C\leftarrow \varnothing$
3. while $X=\varnothing$ do
   1. вибираємо $S\in F$ з найбільшим $\mid X\cap S\mid$
   2. $X\leftarrow X\setminus S$
   3. $C\leftarrow C\cup \{S\}$
4. return $C$

Можна показати, що цей алгоритм працює з точністю $O(H(s))$, де $s$ — потужність найбільшої множини, а $H(n)$ — сума перших $n$ членів гармонійного ряду.

$H(n)=\sum _{k=1}^n\frac{1}{k}\le \ln n+1$

Іншими словами, алгоритм знаходить покриття, розмір якого не більше ніж в$H(s)$ разів перевищує розмір мінімального покриття.

Спрощений приклад роботи жадібного алгоритму для k = 3

Існує стандартний приклад, на якому жадібний алгоритм працює з точністю ${\log }_2(n)/2$.

Універсуум складається з $n=2^{(k+1)}-2$ елементів. Набір множин складається з $k$ попарно не перетинних множин $S_1,\dots ,S_k$, потужності яких $2,4,8,\dots ,2^k$ відповідно. Також є дві неперетинних підмножини $T_0,T_1$, кожна з яких містить половину елементів з кожного $S_i$. На такому наборі жадібний алгоритм вибирає множини $S_k,\dots ,S_1$, тоді як оптимальним розв'язком є вибір множин $T_0$ і $T_1$. Приклад таких вхідних даних $k=3$ можна побачити на малюнку праворуч.

Генетичний алгоритм

Генетичний алгоритм являє собою евристичний метод випадкового пошуку, заснований на принципі імітації еволюції біологічної популяції.

У загальному випадку в процесі роботи алгоритму відбувається послідовна зміна популяцій, кожна з яких є сімейством покриттів, званих особинами популяції. Покриття початкової популяції будуються випадковим чином. Найпоширенішою є стаціонарна схема генетичного алгоритму, в якій чергова популяція відрізняється від попередньої лише однією або двома новими особинами. Під час побудови нової особини з поточної популяції з урахуванням ваг покриттів вибирається «батьківська» пара особин $J^{\prime },J^{″}$, і на їх основі у процедурі кросинговеру (випадково або детерміновано) формується певний набір покривних множин $J_x$. Далі піддається мутації, після чого з нього будується особина, яка заміняє в новій популяції покриття з найбільшою вагою. Оновлення популяції виконується деяке (задане) число разів, і результатом роботи алгоритму є найкраще зі знайдених покриттів.

Точний розв'язок

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

Потрібно знайти $f^{*}(c,A)=\min \{(c,x)|Ax\ge e,x\in \{0,1{\}}^n\}$.

де $A$ — $(m\times n)$ матриця, причому $a_{ij}$ = 1, якщо $i\in S_j$ і $a_{ij}$ = 0 в іншому випадку; $e$ позначає $m$ — вектор з одиниць; $c=(c_1,c_2,\dots ,c_n{)}^T$; $x=(x_1,x_2,\dots ,x_n{)}^T$ — вектор, де $x_j=1$, якщо $S_j$ входить у покриття, інакше $x_j=0$.

Точний розв'язок можна отримати за поліноміальний час, у випадку, коли матриця $A$ цілком унімодулярна. Сюди можна віднести і задачу про вершинне покриття на двочастковому графі та дереві. Зокрема, коли кожен стовпець матриці $A$ містить рівно дві одиниці, задачу можна розглядати як задачу реберного покриття графу, яка ефективно зводиться до пошуку максимального парування. На класах задач, де $n$ або $m$ обмежені константою, задача за поліноміальний час розв'язується методами повного перебору.

Схожі задачі

• Задача про вершинне покриття
• Задача про призначення найменшого числа виконавців
• Задача про найменше коло

Література

• А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования. Дискретный анализ и исследование операций. Сер. 2. 2000. Т. 7, N 2. С.22-46.
• Шаблон:Книга

Посилання

• Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Determination Winner Шаблон:Webarchive