MAX-SAT: вероятностное округление/Задачи/MAX-SAT-1-2-expected-time

Материал из DISCOPAL
< MAX-SAT: вероятностное округление‎ | Задачи
Версия от 12:57, 5 октября 2020; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Рассмотрим следующий алгоритм для задачи MAX-SAT.

  • Случайно (равномерное распределение) выбираем значения переменных
  • Если выполнено меньше половины скобок — повторяем.

Т.е. алгоритм гарантирует выполнение более половины скобок. Оцените матожидание времени работы.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.