Алгоритм Монте-Карло - Monte Carlo algorithm
 | Эта статья включает в себя список общих использованная литература, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. (Август 2011 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
В вычисление, а Алгоритм Монте-Карло это рандомизированный алгоритм чей вывод может быть неправильным с определенным (обычно маленьким) вероятность. Два примера таких алгоритмов: Алгоритм Каргера – Стейна[1] и алгоритм Монте-Карло для минимальная уставка дуги обратной связи.[2]
Название относится к великому казино в Княжестве Монако на Монте-Карло, который известен во всем мире как икона азартных игр. Термин «Монте-Карло» впервые был введен в 1947 г. Николай Метрополис.[3]
Алгоритмы Лас-Вегаса являются подмножеством алгоритмов Монте-Карло, которые всегда дают правильный ответ. Поскольку в процессе работы они делают случайный выбор, время, затрачиваемое на запуск, может варьироваться даже при одном и том же вводе.
Если существует процедура для проверки правильности ответа, данного алгоритмом Монте-Карло, и вероятность правильного ответа ограничена выше нуля, то с вероятностью один повторное выполнение алгоритма при проверке ответов в конечном итоге даст правильный ответ. Является ли этот процесс алгоритмом Лас-Вегаса, зависит от того, считается ли остановка с вероятностью 1 удовлетворяющей определению.
Односторонняя или двусторонняя ошибка
В то время как ответ, возвращенный детерминированный алгоритм всегда ожидается, что он будет правильным, это не относится к алгоритмам Монте-Карло. Для проблемы решения эти алгоритмы обычно классифицируются как ложный-смещенный или правдапредвзято. А ложный-смещенный алгоритм Монте-Карло всегда верен, когда возвращает ложный; а правда-смещенный алгоритм всегда верен, когда возвращается правда. Хотя это описывает алгоритмы с односторонние ошибкидругие могут не иметь предвзятости; говорят, что они двусторонние ошибки. Ответ, который они предоставляют (либо правда или ложный) будет неверным или правильным с некоторой ограниченной вероятностью.
Например, Тест на простоту Соловея – Штрассена используется, чтобы определить, является ли данное число простое число. Всегда отвечает правда для вводов простых чисел; для составных входов он отвечает ложный с вероятностью не менее1⁄2 и правда с вероятностью меньше чем1⁄2. Таким образом, ложный ответы алгоритма наверняка будут правильными, тогда как правда ответы остаются неопределенными; это называется 1⁄2-правильный ложно-смещенный алгоритм.
Усиление
Для алгоритма Монте-Карло с односторонними ошибками вероятность отказа можно уменьшить (и увеличить вероятность успеха), запустив алгоритм k раз. Рассмотрим снова алгоритм Соловея – Штрассена, который 1⁄2-правильный ложно-смещенный. Этот алгоритм можно запускать несколько раз, возвращая ложный ответьте, если он достигнет ложный ответ в k итераций, и иначе возвращение правда. Таким образом, если число простое, то ответ всегда правильный, а если число составное, то ответ правильный с вероятностью не менее 1− (1−1⁄2)k = 1−2−k.
Для алгоритмов принятия решений Монте-Карло с двусторонней ошибкой вероятность отказа снова может быть уменьшена путем запуска алгоритма k раз и вернув функция большинства ответов.
Классы сложности
В класс сложности BPP описывает проблемы решения которая может быть решена с помощью полиномиальных алгоритмов Монте-Карло с ограниченной вероятностью двусторонних ошибок, а класс сложности RP описывает проблемы, которые могут быть решены алгоритмом Монте-Карло с ограниченной вероятностью односторонней ошибки: если правильный ответ ложный, алгоритм всегда так говорит, но может ответить ложный неправильно для некоторых случаев, когда правильный ответ правда. Напротив, класс сложности ЗПП описывает задачи, решаемые с помощью алгоритмов Лас-Вегаса с полиномиальным ожидаемым временем. ЗПП ⊆ РП ⊆ БПП, но не известно, отличается ли какой-либо из этих классов сложности друг от друга; то есть алгоритмы Монте-Карло могут иметь большую вычислительную мощность, чем алгоритмы Лас-Вегаса, но это не было доказано. Другой класс сложности, PP, описывает проблемы решения с помощью алгоритма Монте-Карло с полиномиальным временем, который более точен, чем подбрасывание монеты, но где вероятность ошибки не обязательно может быть отделена от1⁄2.
Приложения в вычислительной теории чисел
Хорошо известные алгоритмы Монте-Карло включают тест на простоту Соловея – Штрассена, Тест на простоту Baillie – PSW, то Тест на простоту Миллера – Рабина, и некоторые быстрые варианты Алгоритм Шрайера – Симса в вычислительная теория групп.
Смотрите также
- Методы Монте-Карло, алгоритмы, используемые в физическом моделировании и вычислительная статистика на основе случайных выборок
- Алгоритм Атлантик-Сити
- Алгоритм Лас-Вегаса
использованная литература
Цитаты
- ^ Каргер, Дэвид Р .; Стейн, Клиффорд (июль 1996 г.). «Новый подход к проблеме минимального сокращения». J. ACM. 43 (4): 601–640. Дои:10.1145/234533.234534. ISSN 0004-5411.
- ^ Куделич, Роберт (2016-04-01). «Рандомизированный алгоритм Монте-Карло для задачи о множестве дуг с минимальной обратной связью». Прикладные мягкие вычисления. 41: 235–246. Дои:10.1016 / j.asoc.2015.12.018.
- ^ Метрополис, Н. (1987). «Начало метода Монте-Карло» (PDF). Лос-Аламос Сайенс (Специальный выпуск 1987 г., посвященный Станиславу Уламу): 125–130.CS1 maint: ref = harv (ссылка на сайт)
Источники
- Мотвани, Раджив; Рагхаван, Прабхакар (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.