MAX-SAT: вероятностное округление/Задачи/MAX-SAT-1-2-expected-time — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показано 5 промежуточных версий этого же участника)
Строка 2: Строка 2:
  
 
* Случайно (равномерное распределение) выбираем значения переменных <m>x_1,\ldots,x_n</m>
 
* Случайно (равномерное распределение) выбираем значения переменных <m>x_1,\ldots,x_n</m>
−
 
 
* Если выполнено меньше половины скобок — повторяем.
 
* Если выполнено меньше половины скобок — повторяем.
  
 
Т.е. алгоритм гарантирует выполнение более половины скобок.
 
Т.е. алгоритм гарантирует выполнение более половины скобок.
−
 
 
Оцените матожидание времени работы.
 
Оцените матожидание времени работы.
  
−
 
+
[[Категория:Проблемные задачи]]
−
[[Категория:На проверку]]
+
−
 
+
−
===Стенина Мария, группа 974===
+
−
 
+
−
<latex>
+
−
Распишем формулу математического ожидания числа итераций. Обозначим количество итераций $l$ и $\alpha = \mathbb{P}(\sum\limits_{i=1}^m z_i < \frac{m}{2})$, где $z_i$ --- значение $i$-той скобки (0 или 1).
+
−
$$
+
−
    \mathbb{E}(l) = \sum_{k = 1}^{\infty} k \alpha^{k-1} (1 - \alpha) = (1 - \alpha) \sum_{k=0}^{\infty} (1 + k) \alpha^k = \frac{1 - \alpha}{(1 - \alpha)^2} = \frac{1}{1 - \alpha}.
+
−
$$
+
−
 
+
−
Теперь оценим $\alpha$. Пусть $i$-тая скобка содержит $k_i$ литералов. Чтобы значение скобки было равно нулю, необходимо, чтобы значения всех литералов были равны нулю. Вероятность такого события $2^{-k_i}$. Следовательно, вероятность $\mathbb{P}(z_i = 0) \leq \frac{1}{2}$. Если предположить, что все $z_i$ независимые случайные величины, то $\alpha = \mathbb{P}(\sum\limits_{i=1}^m z_i < \frac{m}{2}) \leq \frac{1}{2}$. Если же $z_i$ зависимы, то из неравенства $\mathbb{P}(A, B) \leq \mathbb{P}(A) + \mathbb{P}(B)$ получаем ту же оценку на $\alpha$. Отсюда имеем оценку ожидания числа итераций
+
−
$$
+
−
  \mathbb{E}(l) \leq \frac{1}{1 - \frac{1}{2}} \leq 2.
+
−
$$
+
−
 
+
−
</latex>
+

Текущая версия на 12:57, 5 октября 2020

Рассмотрим следующий алгоритм для задачи MAX-SAT.

  • Случайно (равномерное распределение) выбираем значения переменных
  • Если выполнено меньше половины скобок — повторяем.

Т.е. алгоритм гарантирует выполнение более половины скобок. Оцените матожидание времени работы.

Источник — «https://discopal.ispras.ru/index.php?title=MAX-SAT:_вероятностное_округление/Задачи/MAX-SAT-1-2-expected-time&oldid=12667»