Задача о покрытии («задача о покрытии множества», в англоязычной литературе — «Set covering»)
заключается в следующем:
Пусть на m-элементном множестве X задано некоторое семейство его
подмножеств и .
Надо найти минимальное по числу подмножеств подсемейства , обладающее свойством покрытия, то есть нахождении минимального такого, что
Число |J| при этом, называется размером минимального покрытия.
Известно, что задача о покрытии NP-полна. По этой причине
трудно надеяться на существование полиномиального алгоритма
ее решения.
Поэтому, можно рассматривать приближенные алгоритмы:
Внимание! Данная статья выбрана для репликации во внешнюю базу знаний компании. Пожалуйста, не допускайте в этой статье публикацию конфиденциальной информации, ведения обсуждений в теле статьи, и более ответственно относитесь к качеству самой статьи — проверяйте орфографию, пишите по-русски, избегайте непроверенной вами информации.
