Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому является NP-сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в приближённом алгоритме, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм. Даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно медленно, поэтому такой подход можно считать полезным.
Исходными данными задачи о покрытии множества является конечное множество и семейство его подмножеств. Покрытием называют семейство наименьшей мощности, объединением которых является . В случае постановки вопроса о разрешении на вход подаётся пара и целое число ; вопросом является существование покрывающего множества мощности (или менее).
В качестве примера задачи о покрытии множества можно привести следующую проблему: представим себе, что для выполнения какого-то задания необходим некий набор навыков . Также есть группа людей, каждый из которых владеет некоторыми из этих навыков. Необходимо сформировать наименьшую подгруппу, достаточную для выполнения задания, т.е. включающую в себя носителей всех необходимых навыков.
Жадный алгоритм выбирает множества руководствуясь следующим правилом: на каждом этапе выбирается множество, покрывающее максимальное число ещё не покрытых элементов.
Greedy-Set-Cover(U,F)
, где
— заданное множество всех элементов,
— семейство подмножеств
while
do
return
Можно показать, что этот алгоритм работает с точностью , где — мощность наибольшего множества, а — это сумма первых членов гармонического ряда.
Другими словами, алгоритм находит покрытие, размер которого не более чем в раз превосходит размер минимального покрытия.
Существует стандартный пример, на котором жадный алгоритм работает с точностью .
Универсуум состоит из элементов. Набор множеств состоит из попарно не пересекающихся множеств , мощности которых соответственно. Так же имеются два непересекающихся множества , каждое из которых содержит половину элементов из каждого . На таком наборе жадный алгоритм выбирает множества , тогда как оптимальным решением является выбор множеств и Пример подобных входных данных для можно увидеть на рисунке справа.
Генетический алгоритм представляет собой эвристический метод случайного поиска, основанный на принципе имитации эволюции биологической популяции.
В общем случае в процессе работы алгоритма происходит последовательная смена популяций, каждая из которых является семейством покрытий, называемых особями популяции. Покрытия начальной популяции строятся случайным образом. Наиболее распространённая и лучше всего зарекомендовавшая себя — стационарная схема генетического алгоритма, в которой очередная популяция отличается от предыдущей лишь одной или двумя новыми особями. При построении новой особи из текущей популяции с учётом весов покрытий выбирается «родительская» пара особей , и на их основе в процедуре кроссинговера (случайно или детерминированно) формируется некоторый набор покрывающих множеств . Далее подвергается мутации, после чего из него строится особь, которая замещает в новой популяции покрытие с наибольшим весом. Обновление популяции выполняется некоторое(заданное) число раз, и результатом работы алгоритма является лучшее из найденных покрытий.
Часто задача о покрытии множества формулируется, как задача целочисленного программирования:
Требуется найти .
Где — матрица, причём = 1, если , и = 0 в противном случае; обозначает — вектор из единиц; ; — вектор, где , если входит в покрытие, иначе .
Точное решение может быть получено за полиномиальное время, в случае, когда матрица вполне унимодулярна. Сюда можно отнести и задачу о вершинном покрытии на двудольном графе и дереве. В частности, когда каждый столбец матрицы содержит ровно две единицы, задачу можно рассматривать как задачу рёберного покрытия графа, которая эффективно сводится к поиску максимального паросочетания. На классах задач, где или ограничены константой, задача за полиномиальное время решается методами полного перебора.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .