MAX-SAT: вероятностное округление/Задачи/MAX-SAT-1-2-expected-time — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена Category:Решенные задачи на Category:Нерешенные задачи) |
StasFomin (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
Оцените матожидание времени работы. | Оцените матожидание времени работы. | ||
| − | + | [[Категория:Решенные задачи]] | |
| − | [[ | + | |
Версия 23:23, 13 декабря 2016
Рассмотрим следующий алгоритм для задачи MAX-SAT.
- Случайно (равномерное распределение) выбираем значения переменных
- Если выполнено меньше половины скобок — повторяем.
Т.е. алгоритм гарантирует выполнение более половины скобок.
Оцените матожидание времени работы.