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

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

Материал из CustisWiki

Перейти к: навигация, поиск
м (1 версия)
м (обновление данных)
Строка 3: Строка 3:
  
 
Пусть на '''''m'''''-элементном множестве ''X'' задано некоторое семейство его
 
Пусть на '''''m'''''-элементном множестве ''X'' задано некоторое семейство его
подмножеств <math>F=\{S_1, \ldots, S_n \}</math> и <math>X= \cup_{i=1}^n S_i</math>.
+
подмножеств <m>F=\{S_1, \ldots, S_n \}</m> и <m>X= \cup_{i=1}^n S_i</m>.
  
Надо найти минимальное по числу подмножеств подсемейства <math>P \subseteq F</math>, обладающее свойством покрытия, то есть нахождении минимального <math>J \subseteq \{1,2,\ldots, n\}</math> такого, что <math>X= \cup_{i \in J} S_i</math>
+
Надо найти минимальное по числу подмножеств подсемейства <m>P \subseteq F</m>, обладающее свойством покрытия, то есть нахождении минимального <m>J \subseteq \{1,2,\ldots, n\}</m> такого, что <m>X= \cup_{i \in J} S_i</m>
  
 
Число '''''|J|''''' при этом, называется размером минимального покрытия.
 
Число '''''|J|''''' при этом, называется размером минимального покрытия.

Версия 18:40, 22 октября 2008

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

Пусть на m-элементном множестве X задано некоторое семейство его подмножеств и .

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

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

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


Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».

Репликация: База Знаний «Заказных Информ Систем» → «Задача о покрытии»