MAX-SAT: вероятностное округление/Задачи/MAX-SAT-random-t-samples

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

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

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

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

Какова вероятность, что будет выполнено более половины скобок?

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

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

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

Источник — «https://discopal.ispras.ru/index.php?title=MAX-SAT:_вероятностное_округление/Задачи/MAX-SAT-random-t-samples&oldid=5334»