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