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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 16 промежуточных версий этого же участника)
Строка 1: Строка 1:
−
Жадный алгоритм: на <math>k</math>-ом шаге добавляем элемент <math>x_{k}</math>, который содержится в наибольшем числе изначальных подмножеств, не содержащих ни один из элементов <math>x_{k-1}, \ldots, x_{1}</math>.
+
Предложите детерминированный приближенный алгоритм для [[Minimum 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 не покрывал бы и оставшиеся подмножества. В результате,
+
{{needjupyternotebook}}
−
<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>
+
−
 
+
−
 
+
−
Требуя, чтобы правая часть неравенства была меньше единицы, то есть полное покрытие всего семейства получам, что
+
−
<math>
+
−
\frac{k_{1}}{M} \le 1 + \ln(J)
+
−
</math>
+
−
 
+
−
Но <math>k_{1}</math> - и есть число элементов в жадном hitting set-е. Значит получена оценка на точность.
+
−
 
+
−
[[Категория:На проверку]]
+

Текущая версия на 06:50, 4 мая 2023

Предложите детерминированный приближенный алгоритм для Minimum Hitting Set и оцените его точность.

Решение, по возможности, оформите в виде jupyter notebook.

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