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