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