- Задача о покрытии множества
-
Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому является NP-сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в приближённом алгоритме, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм. Даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно медленно, поэтому такой подход можно считать полезным.
Содержание
Формулировка задачи
Исходными данными задачи о покрытии множества является конечное множество
и семейство
его подмножеств. Покрытием называют семейство
наименьшей мощности, объединением которых является
. В случае постановки вопроса о разрешении на вход подаётся пара
и целое число
; вопросом является существование покрывающего множества мощности
(или менее).
Пример
В качестве примера задачи о покрытии множества можно привести следующую проблему: представим себе, что для выполнения какого-то задания необходим некий набор навыков
. Так же, есть группа людей, владеющих некоторыми из этих навыков. Необходимо сформировать минимальную группу для выполнения задания, включающую в себя носителей всех необходимых навыков.
Методы решения
Жадный приближенный алгоритм
Жадный алгоритм выбирает множества руководствуясь следующим правилом: на каждом этапе выбирается множество, покрывающее максимальное число ещё не покрытых элементов.
Greedy-Set-Cover(U,F)
, где— заданное множество всех элементов,
— семейство подмножеств
while
do
- выбираем
с наибольшим
- выбираем
return
Можно показать, что такой алгоритм показывает время работы, где
— мощность наибольшего множества, и
— это сумма первых
членов гармонического ряда.
Упрощённый пример работы жадного алгоритма для k = 3Существует стандартный пример, на котором жадный алгоритм работает за время
.
Универсуум состоит из
элементов. Набор множеств состоит из
попарно не пересекающихся множеств
, мощности которых
соответственно. Так же имеются два непересекающихся множества
, каждое из которых содержит половину элементов из каждого
. На таком наборе жадный алгоритм выбирает множества
, тогда как оптимальным решением является выбор множеств
и
Пример подобных входных данных для
можно увидеть на рисунке справа.
Генетический алгоритм
Генетический алгоритм представляет собой эвристический метод случайного поиска, основанный на принципе имитации эволюции биологической популяции.
В общем случае в процессе работы алгоритма происходит последовательная смена популяций, каждая из которых является семейством покрытий, называемых особями популяции. Покрытия начальной популяции строятся случайным образом. Наиболее распространённая и лучше всего зарекомендовавшая себя — стационарная схема генетического алгоритма, в которой очередная популяция отличается от предыдущей лишь одной или двумя новыми особями. При построении новой особи из текущей популяции с учётом весов покрытий выбирается "родительская" пара особей
, и на их основе в процедуре кроссинговера (случайно или детерминированно) формируется некоторый набор покрывающих множеств
. Далее подвергается мутации, после чего из него строится особь, которая замещает в новой популяции покрытие с наибольшим весом. Обновление популяции выполняется некоторое(заданное) число раз, и результатом работы алгоритма является лучшее из найденных покрытий.
Точное решение
Часто задача о покрытии множества формулируется, как задача целочисленного программирования:
Требуется найти
.
Где
—
матрица, причем
= 1, если
, и
= 0 в противном случае;
обозначает
— вектор из единиц;
;
— вектор, где
, если
входит в покрытие, иначе
.
Точное решение может быть получено за полиномиальное время, в случае, когда матрица
вполне унимодулярна. Сюда можно отнести и задачу о вершинном покрытии на двудольном графе и дереве. В частности, когда каждый столбец матрицы
содержит ровно две единицы, задачу можно рассматривать как задачу рёберного покрытия графа, которая эффективно сводится к поиску максимального паросочетания. На классах задач, где
или
ограничены константой, задача за полиномиальное время решается методами полного перебора.
Схожие задачи
Литература
- А.В.Еремеев, Л.А.Заозерская, А.А.Колоколов. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования. Дискретный анализ и исследование операций. Сер. 2. 2000. Т. 7, N 2. С.22-46.
- Томас Х. Кормен и др. Глава 16. Жадные алгоритмы // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 1-е изд. — М.: Московского центра непрерывного математического образования, 2001. — С. 889-892. — ISBN 5-900916-37-5
Примечания
Ссылки
NP-полные задачи Математика Исследование операций:Оптимизация:Комбинаторная оптимизация Максимизационная задача
укладки (упаковки)Упаковка в контейнеры (двумерная упаковка • линейная упаковка • упаковка по весу • упаковка по стоимости) • Задача о ранце (рюкзаке) Теория графов
теория множествЗадача о вершинном покрытии • Задача о клике • Задача о независимом множестве (наборе) • Задача о покрытии множества • Задача Штейнера • Задача коммивояжёра • Обобщённая задача коммивояжёра Алгоритмические задачи Задача выполнимости булевых формул (в конъюнктивной нормальной форме) Логические игры
и головоломкиОбобщённые пятнашки с костяшками >15) (задача поиска кратчайшего решения) • Задачи, решения которых применяются в Тетрис • Задача обобщённого судоку • Задача о заполнении латинского квадрата • Задача какуро См. также Прикладная математика • Теория алгоритмов • Динамическое программирование • 21 NP-полная задача Карпа Классы сложности Категории:- NP-полные задачи
- Теория множеств
Wikimedia Foundation. 2010.