|
|
| (не показаны 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}}
| + | |
