Алгоритм Монте-Карло - Monte Carlo algorithm

В вычислении , А алгоритм Монте - Карло является рандомизированное алгоритм выход которого может быть неправильным с определенным (обычно небольшой) вероятности . Двумя примерами таких алгоритмов являются алгоритм Каргера – Стейна и алгоритм Монте-Карло для минимального набора дуг обратной связи .

Название относится к грандиозному казино в Княжестве Монако в Монте-Карло , которое широко известно во всем мире как икона азартных игр. Термин «Монте-Карло» впервые был введен в 1947 году Николасом Метрополисом .

Алгоритмы Лас-Вегаса - это двойные алгоритмы Монте-Карло, которые никогда не возвращают неправильный ответ, однако они могут делать случайный выбор в рамках своей работы. В результате затраченное время может варьироваться между запусками даже с одним и тем же входом.

Если существует процедура для проверки правильности ответа, данного алгоритмом Монте-Карло, и вероятность правильного ответа ограничена выше нуля, то с вероятностью один повторное выполнение алгоритма при проверке ответов в конечном итоге даст правильный ответ. Является ли этот процесс алгоритмом Лас-Вегаса, зависит от того, считается ли остановка с вероятностью единица удовлетворяющей определению.

Односторонняя и двусторонняя ошибка

В то время как ответ, возвращаемый детерминированным алгоритмом , всегда ожидается правильным, это не относится к алгоритмам Монте-Карло. Для решения проблем эти алгоритмы обычно классифицируются как ложно- смещенные или истинно- смещенные. Ложный -biased алгоритм Монте - Карло всегда правильно , когда она возвращает ложь ; алгоритм с истинным смещением всегда верен, когда возвращает истину . Хотя здесь описываются алгоритмы с односторонними ошибками , другие могут не иметь предвзятости; считается, что они имеют двусторонние ошибки . Ответ, который они предоставят ( истинный или ложный ), будет неправильным или правильным с некоторой ограниченной вероятностью.

Например, критерий простоты Соловея – Штрассена используется для определения того, является ли данное число простым . Он всегда отвечает истинным для вводимых простых чисел; для композитных входов, он отвечает на ложном с вероятностью по крайней мере 1 / 2 и верно с вероятностью меньше , чем 1 / 2 . Таким образом, ложные ответы алгоритма обязательно будут правильными, в то время как истинные ответы остаются неопределенными; это называется 1 / 2- правильным алгоритмом с ложным смещением .

Усиление

Для алгоритма Монте-Карло с односторонними ошибками вероятность отказа можно уменьшить (и увеличить вероятность успеха), запустив алгоритм k раз. Рассмотрим снова алгоритм Соловея – Штрассена, который является 1 / 2- правильным с ложным смещением . Можно запустить этот алгоритм несколько раз, возвращая ложный ответ, если он достигает ложного ответа в течение k итераций, и в противном случае возвращает истину . Таким образом, если число простое, то ответ всегда правильный, а если число составное, то ответ правильный с вероятностью не менее 1− (1− 1 ⁄ 2 ) ^k  = 1−2 ^−k .

Для алгоритмов принятия решений Монте-Карло с двусторонней ошибкой вероятность отказа можно снова уменьшить, запустив алгоритм k раз и вернув функцию большинства ответов.

Классы сложности

Класс сложности BPP описывает проблемы решения, которые могут быть решены алгоритмами Монте-Карло с полиномиальным временем с ограниченной вероятностью двусторонних ошибок, а класс сложности RP описывает проблемы, которые могут быть решены алгоритмом Монте-Карло с ограниченной вероятностью, равной единице. -сторонняя ошибка: если правильный ответ ложный , алгоритм всегда так говорит, но он может ответить ложно неверно в некоторых случаях, когда правильный ответ является истинным . Напротив, класс сложности ZPP описывает проблемы, решаемые с помощью алгоритмов Лас-Вегаса с полиномиальным ожидаемым временем. ZPP ⊆ RP ⊆ BPP , но неизвестно, отличается ли какой-либо из этих классов сложности друг от друга; то есть алгоритмы Монте-Карло могут иметь большую вычислительную мощность, чем алгоритмы Лас-Вегаса, но это не было доказано. Другой класс сложности, PP , описывает проблемы , решения с полиномиальным алгоритмом Монта - Карло , который является более точным , чем монетка , но где вероятность ошибки не обязательно может быть отделена от 1 / 2 .

Приложения в вычислительной теории чисел

Хорошо известные алгоритмы Монте - Карло , включают тест Соловея-Штрассена, простоты в тест-Бэйли простоты PSW , то тест на простоту Миллера-Рабина , и некоторые варианты быстро от алгоритма шрейеровы-Sims в вычислительной теории групп .

Смотрите также

• Методы Монте-Карло , алгоритмы, используемые в физическом моделировании и вычислительной статистике, основанные на отборе случайных выборок.
• Алгоритм Атлантик-Сити
• Алгоритм Лас-Вегаса

Рекомендации

Цитаты

Источники