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

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

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

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

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

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

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

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

Усиление

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

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

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

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

Классы алгоритмов Монте-Карло и Лас-Вегаса

Рандомизированные алгоритмы в основном делятся на два основных типа: Монте-Карло и Лас-Вегас, однако они представляют собой лишь вершину иерархии и могут быть далее классифицированы. ^[4]

Вегас
- Шервуд — «результатный и эффективный особый случай Лас-Вегаса».
- Численный — «цифровой Лас-Вегас».
Монте-Карло
- Атлантик-Сити — «особый случай ограниченной ошибки Монте-Карло»
- Численный - «числовая аппроксимация Монте-Карло».

«И Лас-Вегас, и Монте-Карло имеют дело с решениями, то есть с проблемами в их версии решения ». ^[4] «Однако это не должно создавать неправильное впечатление и ограничивать эти алгоритмы такими задачами — оба типа рандомизированных алгоритмов могут использоваться и для числовых задач, задач, где результат не является простым «да» / «нет», но где нужно получить результат, который имеет числовой характер». ^[4]

Сравнение алгоритмов Лас-Вегаса и Монте-Карло
	Эффективность	Оптимум	Сбой (LV) / Ошибка (MC)
Лас-Вегас (LV)	Вероятностный	Определенный	$<{\tfrac {1}{2}}$
Шервуд	Определенный, или Шервудский вероятностный (более сильная связь, чем обычный LV)	Определенный	0
Числовой	Вероятностный, определенный или Шервудский вероятностный	Определенный	$<{\tfrac {1}{2}}$ или 0
Монте-Карло (ПЦ)	Определенный	Вероятностный	$<1$ (вероятность того, что при повторных прогонах растет субэкспоненциально) будет препятствовать полезности алгоритма; типичный случай $<{\tfrac {1}{2}}$ )
Атлантик-Сити	Определенный	Вероятностный	$<{\tfrac {1}{4}}$
Числовой	Определенный	Вероятностный	$<1$ (зависит от типа алгоритма)

Предыдущая таблица представляет собой общую структуру рандомизированных алгоритмов Монте-Карло и Лас-Вегаса. ^[4] Вместо математического символа $<$ можно было бы использовать $\leq$ , что делает вероятности в худшем случае равными. ^[4]

Приложения в вычислительной теории чисел и других областях.

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

Для алгоритмов, которые являются частью группы алгоритмов стохастической оптимизации (SO), где вероятность неизвестна заранее и определяется эмпирически, иногда возможно объединить метод Монте-Карло и такой алгоритм, «чтобы иметь как границу вероятности, рассчитанную заранее, так и компонент стохастической оптимизации». ^[4] «Примером такого алгоритма является Ant Inspired Monte Carlo». ^[4]^[5] Таким образом, «недостаток SO был смягчен и установлена уверенность в правильности решения». ^[4]^[5]

См. также

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

Ссылки

Цитаты

^ Каргер, Дэвид Р.; Штейн, Клиффорд (июль 1996 г.). «Новый подход к проблеме минимального разреза» . Дж. АКМ . 43 (4): 601–640. дои : 10.1145/234533.234534 . ISSN 0004-5411 . S2CID 5385337 .
^ Куделич, Роберт (01 апреля 2016 г.). «Рандомизированный алгоритм Монте-Карло для решения задачи набора дуг минимальной обратной связи». Прикладные мягкие вычисления . 41 : 235–246. дои : 10.1016/j.asoc.2015.12.018 .
^ Метрополис, Н. (1987). «Начало метода Монте-Карло» (PDF) . Los Alamos Science (специальный выпуск 1987 г., посвященный Станиславу Уламу): 125–130.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Куделич, Роберт; Ивкович, Никола; Шмагук, Тамара (2023). Чоудри, Джиоти; Махалле, Парикшит Н.; Перумал, Тинагаран; Джоши, Амит (ред.). «Краткий обзор рандомизированных алгоритмов» . Интернет вещей с интеллектуальными системами . Сингапур: Springer Nature: 651–667. дои : 10.1007/978-981-99-3761-5_57 . ISBN 978-981-99-3761-5 .
^ Jump up to: ^а ^б Куделич, Роберт; Ивкович, Никола (2019). «Алгоритм Монте-Карло, вдохновленный муравьями, для минимального набора дуг обратной связи» . Экспертные системы с приложениями . 122 : 108–117. дои : 10.1016/j.eswa.2018.12.021 . ISSN 0957-4174 .

Источники

Мотвани, Раджив ; Рагхаван, Прабхакар (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 .

[1] Каргер, Дэвид Р.; Штейн, Клиффорд (июль 1996 г.). «Новый подход к проблеме минимального разреза» . Дж. АКМ . 43 (4): 601–640. дои : 10.1145/234533.234534 . ISSN 0004-5411 . S2CID 5385337 .

[2] Куделич, Роберт (01 апреля 2016 г.). «Рандомизированный алгоритм Монте-Карло для решения задачи набора дуг минимальной обратной связи». Прикладные мягкие вычисления . 41 : 235–246. дои : 10.1016/j.asoc.2015.12.018 .

[3] Метрополис, Н. (1987). «Начало метода Монте-Карло» (PDF) . Los Alamos Science (специальный выпуск 1987 г., посвященный Станиславу Уламу): 125–130.

[:0-4] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Куделич, Роберт; Ивкович, Никола; Шмагук, Тамара (2023). Чоудри, Джиоти; Махалле, Парикшит Н.; Перумал, Тинагаран; Джоши, Амит (ред.). «Краткий обзор рандомизированных алгоритмов» . Интернет вещей с интеллектуальными системами . Сингапур: Springer Nature: 651–667. дои : 10.1007/978-981-99-3761-5_57 . ISBN 978-981-99-3761-5 .

[:1-5] Jump up to: ^а ^б Куделич, Роберт; Ивкович, Никола (2019). «Алгоритм Монте-Карло, вдохновленный муравьями, для минимального набора дуг обратной связи» . Экспертные системы с приложениями . 122 : 108–117. дои : 10.1016/j.eswa.2018.12.021 . ISSN 0957-4174 .

[1]

[2]

[3]

[4]

[5]