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

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

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

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

Приклад

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

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

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

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

Схожі задачі

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

Примітки

1. А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов. ЗАДАЧА О ПОКРЫТИИ МНОЖЕСТВА: СЛОЖНОСТЬ, АЛГОРИТМЫ, ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ // ДИСКРЕТНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ. — 2000. — Т. 7, № 2 (Июль—декабрь). — С. 22-46. з джерела 25 січня 2021. Процитовано 23 грудня 2020.

Література

• А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования. Дискретный анализ и исследование операций. Сер. 2. 2000. Т. 7, N 2. С.22-46.
• Томас Х. Кормен и др. Глава 16. Жадные алгоритмы // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 1-е изд. — М. : Московского центра непрерывного математического образования, 2001. — С. 889-892. — .

Посилання

• Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Determination Winner [ 25 липня 2017 у Wayback Machine.]