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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи на :Решенные задачи)
 
Строка 7: Строка 7:
 
Какова вероятность, что будет выполнено более половины скобок?
 
Какова вероятность, что будет выполнено более половины скобок?
  
[[Category:Решенные задачи]]
+
[[Категория:Проблемные задачи]]

Текущая версия на 08:23, 20 декабря 2016

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

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

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