MAX-SAT: вероятностное округление/Задачи/MAX-SAT-1-2-expected-time — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
Строка 2: | Строка 2: | ||
* Случайно (равномерное распределение) выбираем значения переменных <m>x_1,\ldots,x_n</m> | * Случайно (равномерное распределение) выбираем значения переменных <m>x_1,\ldots,x_n</m> | ||
+ | |||
* Если выполнено меньше половины скобок — повторяем. | * Если выполнено меньше половины скобок — повторяем. | ||
Строка 9: | Строка 10: | ||
− | [[ | + | [[Категория:На проверку]] |
− | < | + | |
+ | ===Стенина Мария, группа 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> |
Версия 07:57, 24 октября 2014
Рассмотрим следующий алгоритм для задачи MAX-SAT.
- Случайно (равномерное распределение) выбираем значения переменных
- Если выполнено меньше половины скобок — повторяем.
Т.е. алгоритм гарантирует выполнение более половины скобок.
Оцените матожидание времени работы.
Стенина Мария, группа 974