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

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

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

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

Приклад

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

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

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

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

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

1. $X\leftarrow U$
2. $C\leftarrow \varnothing$
3. while $X\not =\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}}\leq \ln {n}+1$

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

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

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

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

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

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

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

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

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

Потрібно знайти $f^{*}(c,A)=\min\{(c,x)|Ax\geq 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.
• Томас Х. Кормен и др. Глава 16. Жадные алгоритмы // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 1-е изд. — М. : Московского центра непрерывного математического образования, 2001. — С. 889-892. — ISBN 5-900916-37-5.

Посилання

• Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Determination Winner [Архівовано 25 липня 2017 у Wayback Machine.]