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

класичне питання інформатики і теорії складності

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

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

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

Приклад ред.

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

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

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

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

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

  1.  
  2.  
  3. while   do
    1. вибираємо   з найбільшим  
    2.  
    3.  
  4. return  

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

 

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

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

Існує стандартний приклад, на якому жадібний алгоритм працює з точністю  .

Універсуум складається з   елементів. Набір множин складається з   попарно не перетинних множин  , потужності яких   відповідно. Також є дві неперетинних підмножини  , кожна з яких містить половину елементів з кожного  . На такому наборі жадібний алгоритм вибирає множини  , тоді як оптимальним розв'язком є вибір множин   і  . Приклад таких вхідних даних   можна побачити на малюнку праворуч.

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

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

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

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

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

Потрібно знайти  .

де   —   матриця, причому   = 1, якщо   і   = 0 в іншому випадку;   позначає   — вектор з одиниць;  ;   — вектор, де  , якщо   входить у покриття, інакше  .

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

Схожі задачі ред.

Примітки ред.

  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. — ISBN 5-900916-37-5.

Посилання ред.