В вычислении , А алгоритм Монте - Карло является рандомизированное алгоритм выход которого может быть неправильным с определенным (обычно небольшой) вероятности . Двумя примерами таких алгоритмов являются алгоритм Каргера – Стейна [1] и алгоритм Монте-Карло для минимального набора дуг обратной связи . [2]
Название относится к грандиозному казино в Княжестве Монако в Монте-Карло , которое широко известно во всем мире как икона азартных игр. Термин «Монте-Карло» впервые был введен в 1947 году Николасом Метрополисом . [3]
Алгоритмы Лас-Вегаса - это подмножество алгоритмов Монте-Карло, которые всегда дают правильный ответ. Поскольку они делают случайный выбор в рамках своей работы, время, затрачиваемое на запуск, может варьироваться даже с одним и тем же входом.
Если существует процедура для проверки правильности ответа, данного алгоритмом Монте-Карло, и вероятность правильного ответа ограничена выше нуля, то с вероятностью один повторное выполнение алгоритма при проверке ответов в конечном итоге даст правильный ответ. Является ли этот процесс алгоритмом Лас-Вегаса, зависит от того, считается ли остановка с вероятностью единица удовлетворяющей определению.
Односторонняя и двусторонняя ошибка
В то время как ответ, возвращаемый детерминированным алгоритмом , всегда ожидается правильным, это не относится к алгоритмам Монте-Карло. Для решения проблем эти алгоритмы обычно классифицируются как ложно- смещенные или истинно- смещенные. Ложный -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 в вычислительной теории групп .
Смотрите также
- Методы Монте-Карло , алгоритмы, используемые в физическом моделировании и вычислительной статистике, основанные на отборе случайных выборок.
- Алгоритм Атлантик-Сити
- Алгоритм Лас-Вегаса
Рекомендации
Цитаты
- ^ Каргер, Дэвид Р .; Стейн, Клиффорд (июль 1996 г.). «Новый подход к проблеме минимального сокращения». J. ACM . 43 (4): 601–640. DOI : 10.1145 / 234533.234534 . ISSN 0004-5411 . S2CID 5385337 .
- ^ Куделич, Роберт (2016-04-01). «Рандомизированный алгоритм Монте-Карло для задачи о множестве дуг с минимальной обратной связью». Прикладные программные вычисления . 41 : 235–246. DOI : 10.1016 / j.asoc.2015.12.018 .
- ^ Метрополис, Н. (1987). «Начало метода Монте-Карло» (PDF) . Los Alamos Science (специальный выпуск 1987 г., посвященный Станиславу Уламу): 125–130. CS1 maint: обескураженный параметр ( ссылка )
Источники
- Мотвани, Раджив ; Рагхаван, Прабхакар (1995). Рандомизированные алгоритмы . Нью-Йорк : Издательство Кембриджского университета. ISBN 0-521-47465-5.
- Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001). «Глава 5. Вероятностный анализ и рандомизированные алгоритмы». Введение в алгоритмы (2-е изд.). Бостон : MIT Press и McGraw-Hill. ISBN 0-262-53196-8.
- Берман, Кеннет А .; Пол, Джером Л. (2005). "Глава 24. Вероятностные и рандомизированные алгоритмы". Алгоритмы: последовательный, параллельный и распределенный . Бостон : Технология курса. ISBN 0-534-42057-5.