Задача про покриття множини
Задача про покриття множини є класичним питанням інформатики і теорії складності. Ця задача узагальнює NP-повну задачу про вершинне покриття (і тому є NP-складною). Попри те, що задача про вершинне покриття подібна до цієї, підхід, використаний у наближеному алгоритмі, тут не працює. Замість цього ми розглянемо жадібний алгоритм. Отриманий за ним розв'язок буде гіршим від оптимального в логарифмічне число разів. Із зростанням розміру задачі якість розв'язку погіршується, але все ж досить повільно, тому такий підхід можна вважати корисним.
Вхідними даними задачі про покриття множини є скінченна множина і сімейство її підмножин. Покриттям називають сімейство найменшої потужності, об'єднанням яких є . В разі постановки питання про дозвіл на вхід подається пара і ціле число ; питанням є існування покривної множини з потужністю (або менше).
Прикладом задачі про покриття множини є така задача: уявімо собі, що для виконання якогось завдання потрібен певний набір навичок . Також є група людей, кожен з яких володіє деякими з цих навичок. Необхідно сформувати найменшу підгрупу, достатню для виконання завдання, тобто таку, що включає носіїв усіх необхідних навичок.
Жадібний алгоритм вибирає множини керуючись таким правилом: на кожному етапі вибирається множина, що покриває найбільше число ще не покритих елементів.
Greedy-Set-Cover(U,F)
, де — задана множина всіх елементів, — сімейство підмножин
while
do
- вибираємо з найбільшим
return
Можна показати, що цей алгоритм працює з точністю , де — потужність найбільшої множини, а — сума перших членів гармонійного ряду.
Іншими словами, алгоритм знаходить покриття, розмір якого не більше ніж в разів перевищує розмір мінімального покриття.
![](http://upload.wikimedia.org/wikipedia/commons/4/4b/SetCoverGreedy.gif)
Існує стандартний приклад, на якому жадібний алгоритм працює з точністю .
Універсуум складається з елементів. Набір множин складається з попарно не перетинних множин , потужності яких відповідно. Також є дві неперетинних підмножини , кожна з яких містить половину елементів з кожного . На такому наборі жадібний алгоритм вибирає множини , тоді як оптимальним розв'язком є вибір множин і . Приклад таких вхідних даних можна побачити на малюнку праворуч.
Генетичний алгоритм являє собою евристичний метод випадкового пошуку, заснований на принципі імітації еволюції біологічної популяції.
У загальному випадку в процесі роботи алгоритму відбувається послідовна зміна популяцій, кожна з яких є сімейством покриттів, званих особинами популяції. Покриття початкової популяції будуються випадковим чином. Найпоширенішою є стаціонарна схема генетичного алгоритму, в якій чергова популяція відрізняється від попередньої лише однією або двома новими особинами. Під час побудови нової особини з поточної популяції з урахуванням ваг покриттів вибирається «батьківська» пара особин , і на їх основі у процедурі кросинговеру (випадково або детерміновано) формується певний набір покривних множин . Далі піддається мутації, після чого з нього будується особина, яка заміняє в новій популяції покриття з найбільшою вагою. Оновлення популяції виконується деяке (задане) число разів, і результатом роботи алгоритму є найкраще зі знайдених покриттів.
Часто задача про покриття множини формулюється як задача цілочисельного програмування[1]:
Потрібно знайти .
де — матриця, причому = 1, якщо і = 0 в іншому випадку; позначає — вектор з одиниць; ; — вектор, де , якщо входить у покриття, інакше .
Точний розв'язок можна отримати за поліноміальний час, у випадку, коли матриця цілком унімодулярна. Сюди можна віднести і задачу про вершинне покриття на двочастковому графі та дереві. Зокрема, коли кожен стовпець матриці містить рівно дві одиниці, задачу можна розглядати як задачу реберного покриття графу, яка ефективно зводиться до пошуку максимального парування. На класах задач, де або обмежені константою, задача за поліноміальний час розв'язується методами повного перебору.
- Задача про вершинне покриття
- Задача про призначення найменшого числа виконавців
- Задача про найменше коло
- ↑ А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов. ЗАДАЧА О ПОКРЫТИИ МНОЖЕСТВА: СЛОЖНОСТЬ, АЛГОРИТМЫ, ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ // ДИСКРЕТНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ. — 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.