Задача о покрытии — различия между версиями
BenderBot (обсуждение | вклад) м (реплицировано из внутренней CustisWiki) |
StasFomin (обсуждение | вклад) м |
||
Строка 1: | Строка 1: | ||
− | Задача о покрытии («задача о покрытии множества», в англоязычной литературе — | + | Задача о покрытии («задача о покрытии множества», в англоязычной литературе — «[[Set covering]]») |
заключается в следующем: | заключается в следующем: | ||
Версия 19:21, 19 апреля 2006
Задача о покрытии («задача о покрытии множества», в англоязычной литературе — «Set covering») заключается в следующем:
Пусть на m-элементном множестве X задано некоторое семейство его подмножеств и .
Надо найти минимальное по числу подмножеств подсемейства , обладающее свойством покрытия, то есть нахождении минимального такого, что
Число |J| при этом, называется размером минимального покрытия.
Известно, что задача о покрытии NP-полна. По этой причине трудно надеяться на существование полиномиального алгоритма ее решения. Поэтому, можно рассматривать приближенные алгоритмы:
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
Репликация: База Знаний «Заказных Информ Систем» → «Задача о покрытии»