https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D0%B8%D0%B8Задача о покрытии - История изменений2026-05-06T08:40:19ZИстория изменений этой страницы в викиMediaWiki 1.26.4https://discopal.ispras.ru/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D0%B8%D0%B8&diff=1114&oldid=prevWikiSysop: 1 версия2008-10-23T16:48:00Z<p>1 версия</p>
<p><b>Новая страница</b></p><div>Задача о покрытии («задача о покрытии множества», в англоязычной литературе — «[[Set covering]]»)<br />
заключается в следующем:<br />
<br />
Пусть на '''''m'''''-элементном множестве ''X'' задано некоторое семейство его<br />
подмножеств <m>F=\{S_1, \ldots, S_n \}</m> и <m>X= \cup_{i=1}^n S_i</m>.<br />
<br />
Надо найти минимальное по числу подмножеств подсемейства <m>P \subseteq F</m>, обладающее свойством покрытия, то есть нахождении минимального <m>J \subseteq \{1,2,\ldots, n\}</m> такого, что <m>X= \cup_{i \in J} S_i</m><br />
<br />
Число '''''|J|''''' при этом, называется размером минимального покрытия.<br />
<br />
Известно, что задача о покрытии NP-полна. По этой причине<br />
трудно надеяться на существование полиномиального алгоритма<br />
ее решения. <br />
Поэтому, можно рассматривать приближенные алгоритмы:<br />
* [[Задача о покрытии:Жадный алгоритм]]<br />
<br />
<br />
[[Category:Задачи]]<br />
{{replicate-from-custiswiki-to-lib}}</div>WikiSysop