Задача о покрытии множества
Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому является NP-сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в приближённом алгоритме, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм. Даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно медленно, поэтому такой подход можно считать полезным.
Формулировка задачи
Исходными данными задачи о покрытии множества является конечное множество [math]\displaystyle{ \mathcal{U} }[/math] и семейство [math]\displaystyle{ \mathcal{S} }[/math] его подмножеств. Покрытием называют семейство [math]\displaystyle{ \mathcal{C}\subseteq\mathcal{S} }[/math] наименьшей мощности, объединением которых является [math]\displaystyle{ \mathcal{U} }[/math]. В случае постановки вопроса о разрешении на вход подаётся пара [math]\displaystyle{ (\mathcal{U},\mathcal{S}) }[/math] и целое число [math]\displaystyle{ k }[/math]; вопросом является существование покрывающего множества мощности [math]\displaystyle{ k }[/math] (или менее).
Пример
В качестве примера задачи о покрытии множества можно привести следующую проблему: представим себе, что для выполнения какого-то задания необходим некий набор навыков [math]\displaystyle{ S }[/math]. Также есть группа людей, каждый из которых владеет некоторыми из этих навыков. Необходимо сформировать наименьшую подгруппу, достаточную для выполнения задания, т.е. включающую в себя носителей всех необходимых навыков.
Методы решения
Жадный приближенный алгоритм
Жадный алгоритм выбирает множества руководствуясь следующим правилом: на каждом этапе выбирается множество, покрывающее максимальное число ещё не покрытых элементов.
Greedy-Set-Cover(U,F), где [math]\displaystyle{ U }[/math] — заданное множество всех элементов, [math]\displaystyle{ F }[/math] — семейство подмножеств [math]\displaystyle{ U }[/math]
- [math]\displaystyle{ X \leftarrow U }[/math]
- [math]\displaystyle{ C \leftarrow \varnothing }[/math]
while[math]\displaystyle{ X \not= \varnothing }[/math]do- выбираем [math]\displaystyle{ S \in F }[/math] с наибольшим [math]\displaystyle{ \mid X \cap S \mid }[/math]
- [math]\displaystyle{ X \leftarrow X \setminus S }[/math]
- [math]\displaystyle{ C \leftarrow C \cup \{S\} }[/math]
return[math]\displaystyle{ C }[/math]
Можно показать, что этот алгоритм работает с точностью [math]\displaystyle{ O(H(s)) }[/math], где [math]\displaystyle{ s }[/math] — мощность наибольшего множества, а [math]\displaystyle{ H(n) }[/math] — это сумма первых [math]\displaystyle{ n }[/math] членов гармонического ряда.
- [math]\displaystyle{ H(n) = \sum_{k=1}^{n} \frac{1}{k} \le \ln{n} +1 }[/math]
Другими словами, алгоритм находит покрытие, размер которого не более чем в [math]\displaystyle{ H(s) }[/math] раз превосходит размер минимального покрытия.
Теорма Фейге гоасит, что для задачи о покрытии множества не существует алгоритма с фактором аппроксимации [math]\displaystyle{ (1 - \epsilon) \cdot H(n) }[/math], т.к. иначе класс сложности NP был бы равен классу сложности TIME([math]\displaystyle{ n^{O(\log \log n)} }[/math]).[1] Таким образом жадный алгоритм - лучший аппроксимационный алгоритм для задачи о покрытии множества.
Существует стандартный пример, на котором жадный алгоритм работает с точностью [math]\displaystyle{ \log_2(n)/2 }[/math].
Универсуум состоит из [math]\displaystyle{ n=2^{(k+1)}-2 }[/math] элементов. Набор множеств состоит из [math]\displaystyle{ k }[/math] попарно не пересекающихся множеств [math]\displaystyle{ S_1,\ldots,S_k }[/math], мощности которых [math]\displaystyle{ 2,4,8,\ldots,2^k }[/math] соответственно. Также имеются два непересекающихся множества [math]\displaystyle{ T_0,T_1 }[/math], каждое из которых содержит половину элементов из каждого [math]\displaystyle{ S_i }[/math]. На таком наборе жадный алгоритм выбирает множества [math]\displaystyle{ S_k,\ldots,S_1 }[/math], тогда как оптимальным решением является выбор множеств [math]\displaystyle{ T_0 }[/math] и [math]\displaystyle{ T_1 }[/math] Пример подобных входных данных для [math]\displaystyle{ k=3 }[/math] можно увидеть на рисунке справа.
Генетический алгоритм
Генетический алгоритм представляет собой эвристический метод случайного поиска, основанный на принципе имитации эволюции биологической популяции.
В общем случае в процессе работы алгоритма происходит последовательная смена популяций, каждая из которых является семейством покрытий, называемых особями популяции. Покрытия начальной популяции строятся случайным образом. Наиболее распространённая и лучше всего зарекомендовавшая себя — стационарная схема генетического алгоритма, в которой очередная популяция отличается от предыдущей лишь одной или двумя новыми особями. При построении новой особи из текущей популяции с учётом весов покрытий выбирается «родительская» пара особей [math]\displaystyle{ J^\prime, J'' }[/math], и на их основе в процедуре кроссинговера (случайно или детерминированно) формируется некоторый набор покрывающих множеств [math]\displaystyle{ J_x }[/math]. Далее подвергается мутации, после чего из него строится особь, которая замещает в новой популяции покрытие с наибольшим весом. Обновление популяции выполняется некоторое(заданное) число раз, и результатом работы алгоритма является лучшее из найденных покрытий.
Точное решение
Часто задача о покрытии множества формулируется, как задача целочисленного программирования[2]:
Требуется найти [math]\displaystyle{ f^*(c,A) = \min\{(c,x)|Ax \ge e, x \in \{0,1\}^n\} }[/math], где [math]\displaystyle{ A }[/math] — [math]\displaystyle{ (m \times n) }[/math] матрица, причём [math]\displaystyle{ a_{ij} }[/math] = 1, если [math]\displaystyle{ i \in S_j }[/math], и [math]\displaystyle{ a_{ij} }[/math] = 0 в противном случае; [math]\displaystyle{ e }[/math] обозначает [math]\displaystyle{ m }[/math] — вектор из единиц; [math]\displaystyle{ c = (c_1, c_2,\dots, c_n)^T }[/math]; [math]\displaystyle{ x = (x_1, x_2, \dots , x_n)^T }[/math] — вектор, где [math]\displaystyle{ x_j = 1 }[/math], если [math]\displaystyle{ S_j }[/math] входит в покрытие, иначе [math]\displaystyle{ x_j = 0 }[/math].
Точное решение может быть получено за полиномиальное время, в случае, когда матрица [math]\displaystyle{ A }[/math] вполне унимодулярна. Сюда можно отнести и задачу о вершинном покрытии на двудольном графе и дереве. В частности, когда каждый столбец матрицы [math]\displaystyle{ A }[/math] содержит ровно две единицы, задачу можно рассматривать как задачу рёберного покрытия графа, которая эффективно сводится к поиску максимального паросочетания. На классах задач, где [math]\displaystyle{ n }[/math] или [math]\displaystyle{ m }[/math] ограничены константой, задача за полиномиальное время решается методами полного перебора.
Схожие задачи
Литература
- А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования. Дискретный анализ и исследование операций. Сер. 2. 2000. Т. 7, N 2. С.22-46.
- Томас Х. Кормен и др. Глава 16. Жадные алгоритмы // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 1-е изд. — М.: Московского центра непрерывного математического образования, 2001. — С. 889-892. — ISBN 5-900916-37-5.
Примечания
- ↑ Uriel Feige. A threshold of ln n for approximating set cover (англ.) // Journal of the ACM. — 1998-07. — Vol. 45, iss. 4. — P. 634–652. — ISSN 1557-735X 0004-5411, 1557-735X. — doi:10.1145/285055.285059.
- ↑ А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов. ЗАДАЧА О ПОКРЫТИИ МНОЖЕСТВА: СЛОЖНОСТЬ, АЛГОРИТМЫ, ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ // ДИСКРЕТНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ. — 2000. — Июль—декабрь (т. 7, № 2). — С. 22-46. Архивировано 25 января 2021 года.
