Задача о покрытии множества

Задача о покрытии множества

Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому является NP-сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в приближённом алгоритме, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм. Даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно медленно, поэтому такой подход можно считать полезным.

Содержание

Формулировка задачи

Исходными данными задачи о покрытии множества является конечное множество \mathcal{U} и семейство \mathcal{S} его подмножеств. Покрытием называют семейство \mathcal{C}\subseteq\mathcal{S} наименьшей мощности, объединением которых является \mathcal{U}. В случае постановки вопроса о разрешении на вход подаётся пара (\mathcal{U},\mathcal{S}) и целое число k; вопросом является существование покрывающего множества мощности k (или менее).

Пример

В качестве примера задачи о покрытии множества можно привести следующую проблему: представим себе, что для выполнения какого-то задания необходим некий набор навыков S. Так же, есть группа людей, владеющих некоторыми из этих навыков. Необходимо сформировать минимальную группу для выполнения задания, включающую в себя носителей всех необходимых навыков.

Методы решения

Жадный приближенный алгоритм

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

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

  1. X \leftarrow U
  2. C \leftarrow \varnothing
  3. while  X \not=  \varnothing do
    1. выбираем S \in F с наибольшим \mid X \cap S \mid
    2. X \leftarrow X \setminus S
    3. C \leftarrow C \cup \{S\}
  4. return C


Можно показать, что такой алгоритм показывает время работы O(H(s)), где s — мощность наибольшего множества, и H(n) — это сумма первых n членов гармонического ряда.

 H(n) = \sum_{k=1}^{n} \frac{1}{k} \le \ln{n} +1
Упрощённый пример работы жадного алгоритма для k = 3

Существует стандартный пример, на котором жадный алгоритм работает за время \log_2(n)/2.

Универсуум состоит из n=2^{(k+1)}-2 элементов. Набор множеств состоит из k попарно не пересекающихся множеств S_1,\ldots,S_k, мощности которых 2,4,8,\ldots,2^k соответственно. Так же имеются два непересекающихся множества T_0,T_1, каждое из которых содержит половину элементов из каждого S_i. На таком наборе жадный алгоритм выбирает множества S_k,\ldots,S_1, тогда как оптимальным решением является выбор множеств T_0 и T_1 Пример подобных входных данных для k=3 можно увидеть на рисунке справа.

Генетический алгоритм

Генетический алгоритм представляет собой эвристический метод случайного поиска, основанный на принципе имитации эволюции биологической популяции.

В общем случае в процессе работы алгоритма происходит последовательная смена популяций, каждая из которых является семейством покрытий, называемых особями популяции. Покрытия начальной популяции строятся случайным образом. Наиболее распространённая и лучше всего зарекомендовавшая себя — стационарная схема генетического алгоритма, в которой очередная популяция отличается от предыдущей лишь одной или двумя новыми особями. При построении новой особи из текущей популяции с учётом весов покрытий выбирается "родительская" пара особей J^\prime, J'', и на их основе в процедуре кроссинговера (случайно или детерминированно) формируется некоторый набор покрывающих множеств J_x. Далее подвергается мутации, после чего из него строится особь, которая замещает в новой популяции покрытие с наибольшим весом. Обновление популяции выполняется некоторое(заданное) число раз, и результатом работы алгоритма является лучшее из найденных покрытий.

Точное решение

Часто задача о покрытии множества формулируется, как задача целочисленного программирования:

Требуется найти f*(c,A) = \min\{(c,x)|Ax \le e, x \in \{0,1\}^n\}.

Где A(m \times n) матрица, причем a_{ij} = 1, если i \in S_j, и a_{ij} = 0 в противном случае; e обозначает m — вектор из единиц; c = (c_1, c_2,\dots, c_n)^T; x = (x_1, x_2, \dots , x_n)^T — вектор, где x_j = 1, если S_j входит в покрытие, иначе x_j = 0.

Точное решение может быть получено за полиномиальное время, в случае, когда матрица A вполне унимодулярна. Сюда можно отнести и задачу о вершинном покрытии на двудольном графе и дереве. В частности, когда каждый столбец матрицы A содержит ровно две единицы, задачу можно рассматривать как задачу рёберного покрытия графа, которая эффективно сводится к поиску максимального паросочетания. На классах задач, где n или m ограничены константой, задача за полиномиальное время решается методами полного перебора.

Схожие задачи

Литература

  • А.В.Еремеев, Л.А.Заозерская, А.А.Колоколов. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования. Дискретный анализ и исследование операций. Сер. 2. 2000. Т. 7, N 2. С.22-46.
  • Томас Х. Кормен и др. Глава 16. Жадные алгоритмы // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 1-е изд. — М.: Московского центра непрерывного математического образования, 2001. — С. 889-892. — ISBN 5-900916-37-5


Примечания

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "Задача о покрытии множества" в других словарях:

  • Задача о независимом множестве — относится к классу NP полных задач в области теории графов. Эквивалентна задаче о клике. Содержание 1 Определения 2 Максимальное независимое множество в дереве …   Википедия

  • Задача о независимом наборе — Задача о независимом множестве относится к классу NP полных задач в области теории графов. По сути, она полностью эквивалентна задаче о клике. Независимый набор из 9 голубых вершин Множество вершин графа называется независимым, если никакие две… …   Википедия

  • Задача о рюкзаке — Задача о ранце (рюкзаке) одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен. Подобные… …   Википедия

  • Задача о рюказаке — Задача о ранце (рюкзаке) одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен. Подобные… …   Википедия

  • Задача о вершинном покрытии — NP полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP полноты более сложных задач. Содержание 1 Определение 2 NP полнота 3 Ссылки …   Википедия

  • Задача SAT — Задача выполнимости булевых формул (SAT или ВЫП) задача распознавания, важная для теории вычислительной сложности. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача… …   Википедия

  • Задача ВЫП — Задача выполнимости булевых формул (SAT или ВЫП) задача распознавания, важная для теории вычислительной сложности. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача… …   Википедия

  • Задача о клике — относится к классу NP полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом.[1] …   Википедия

  • Задача о коммивояжере — Задача коммивояжёра (коммивояжёр  бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… …   Википедия

  • Задача о коммивояжёре — Задача коммивояжёра (коммивояжёр  бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»