Персональные инструменты
 

Задача о покрытии — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показаны 4 промежуточные версии 3 участников)
Строка 1: Строка 1:
Задача о покрытии («задача о покрытии множества», в англоязычной литературе — «[[Set covering]]»)
+
#REDIRECT [[discopal:{{PAGENAME}}]]
заключается в следующем:
+
 
+
Пусть на '''''m'''''-элементном множестве ''X'' задано некоторое семейство его
+
подмножеств <math>F=\{S_1, \ldots, S_n \}</math> и <math>X= \cup_{i=1}^n S_i</math>.
+
 
+
Надо найти минимальное по числу подмножеств подсемейства <math>P \subseteq F</math>, обладающее свойством покрытия, то есть нахождении минимального <math>J \subseteq \{1,2,\ldots, n\}</math> такого, что <math>X= \cup_{i \in J} S_i</math>
+
 
+
Число '''''|J|''''' при этом, называется размером минимального покрытия.
+
 
+
Известно, что задача о покрытии NP-полна. По этой причине
+
трудно надеяться на существование полиномиального алгоритма
+
ее решения.
+
Поэтому, можно рассматривать приближенные алгоритмы:
+
* [[Задача о покрытии:Жадный алгоритм]]
+
 
+
 
+
[[Category:Задачи]]
+
{{replicate-from-custiswiki-to-lib}}
+

Текущая версия на 20:25, 13 июня 2011

  1. REDIRECT discopal:Задача о покрытии