Задача о покрытии

Материал из свободной русской энциклопедии «Традиция»
(перенаправлено с «Set covering»)
Перейти к: навигация, поиск

Задача о покрытии («задача о покрытии множества», в англоязычной литературе — «Set covering») заключается в следующем:

Пусть на m-элементном множестве X задано некоторое семейство его подмножеств \(F=\{S_1, \ldots, S_n \}\) и \(X= \cup_{i=1}^n S_i\).

Надо найти минимальное по числу подмножеств подсемейства \(P \subseteq F\), обладающее свойством покрытия, то есть нахождении минимального \(J \subseteq \{1,2,\ldots, n\}\) такого, что \(X= \cup_{i \in J} S_i\)

Число |J| при этом, называется размером минимального покрытия.

Известно, что задача о покрытии NP-полна. По этой причине трудно надеяться на существование полиномиального алгоритма ее решения. Поэтому, можно рассматривать приближенные алгоритмы:


По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.