Жадный алгоритм в задачах о покрытии/Задачи/Hitting-set — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
−
Жадный алгоритм: на <math>k</math>-ом шаге добавляем элемент <math>x_{k}</math>, который содержится в наибольшем числе изначальных подмножеств, не содержащих ни один из элементов <math>x_{k-1}, \ldots, x_{1}</math>.
+
Для данного семейства подмножеств найти минимальное число элементов S таких, что для любого подмножества из данного семейства в нем найдется хотя бы один элемент из S (hitting set).
 +
Предложите детерминированный приближенный алгоритм и оцените его точность.
  
−
Пусть на <math>k</math>-ом шаге осталось <math>X_{k}</math> подмножеств, в которых не содержаться ни один из элементов <math>x_{k-1}, \ldots, x_{1}</math>. Пусть также размер оптимального hitting seta равен <math>M</math>, а изначально было <math>J</math> подмножеств. Тогда на <math>k</math> - ом шаге будет покрыто не менее <math>\frac{X_{k}}{M}</math> объектов. Действительно, иначе оптимальный hitting set не покрывал бы и оставшиеся подмножества. В результате,
 
−
<math>
 
−
X_{k + 1} \le X_{k} - \frac{X_{k}}{M},
 
−
</math>
 
−
А значит,
 
  
−
<math>
 
−
X_{k} \le J(1 - \frac{1}{M})^{k} \le J\exp(-\frac{k}{M}),
 
−
</math>
 
  
  
−
Требуя, чтобы правая часть неравенства была меньше единицы, то есть полное покрытие всего семейства получам, что
+
[[Category:Решенные задачи]]
−
<math>
+
<!--Вообще-то, решения уже есть-->
−
\frac{k_{1}}{M} \le 1 + \ln(J)
+
−
</math>
+
−
 
+
−
Но <math>k_{1}</math> - и есть число элементов в жадном hitting set-е. Значит получена оценка на точность.
+
−
 
+
−
[[Категория:На проверку]]
+

Версия 23:43, 24 декабря 2014

Для данного семейства подмножеств найти минимальное число элементов S таких, что для любого подмножества из данного семейства в нем найдется хотя бы один элемент из S (hitting set). Предложите детерминированный приближенный алгоритм и оцените его точность.

Источник — «https://discopal.ispras.ru/index.php?title=Жадный_алгоритм_в_задачах_о_покрытии/Задачи/Hitting-set&oldid=3396»