MAX-SAT: вероятностное округление/Задачи/MAX-SAT-random-t-samples — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 2: | Строка 2: | ||
* t раз, случайно (равномерное распределение) выбираем набор — значения переменных <m>x_1,\ldots,x_n</m> | * t раз, случайно (равномерное распределение) выбираем набор — значения переменных <m>x_1,\ldots,x_n</m> | ||
| + | |||
* выбираем лучший результат | * выбираем лучший результат | ||
Какова вероятность, что будет выполнено более половины скобок? | Какова вероятность, что будет выполнено более половины скобок? | ||
| − | [[ | + | [[Категория:На проверку]] |
| − | < | + | |
| + | ===Стенина Мария, группа 974=== | ||
| + | |||
| + | <latex> | ||
| + | Оценим вероятность, что после $t$ выборов выполнено не более половины скобок. Это значит, что каждый выбранный набор переменных обеспечивает выполнение не более $\frac{m}{2}$ скобок. | ||
| + | Обозначим количество итераций $\alpha = \mathbb{P}(\sum\limits_{i=1}^m z_i \leq \frac{m}{2})$, где $z_i$ --- значение $i$-той скобки (0 или 1). | ||
| + | Теперь оценим $\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 \leq \frac{m}{2}) \leq \frac{1}{2}$. Если же $z_i$ зависимы, то из неравенства $\mathbb{P}(A, B) \leq \mathbb{P}(A) + \mathbb{P}(B)$ получаем ту же оценку на $\alpha$. Отсюда имеем оценку вероятности выполнения не более половины скобок не больше $2^{-t}$. Поэтому искомая вероятность не меньше, чем $1 - 2^{-t}$. | ||
| + | </latex> | ||
Версия 08:07, 24 октября 2014
Рассмотрим следующий алгоритм для задачи MAX-SAT.
- t раз, случайно (равномерное распределение) выбираем набор — значения переменных
- выбираем лучший результат
Какова вероятность, что будет выполнено более половины скобок?
Стенина Мария, группа 974