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

Не путать с Метод Монте-Карло.

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

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

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

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

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

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

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

Усиление

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

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

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

В класс сложности BPP описывает проблемы решения которая может быть решена с помощью полиномиальных алгоритмов Монте-Карло с ограниченной вероятностью двусторонних ошибок, а класс сложности RP описывает проблемы, которые могут быть решены алгоритмом Монте-Карло с ограниченной вероятностью односторонней ошибки: если правильный ответ ложный, алгоритм всегда так говорит, но может ответить ложный неправильно для некоторых случаев, когда правильный ответ правда. Напротив, класс сложности ЗПП описывает задачи, решаемые с помощью алгоритмов Лас-Вегаса с полиномиальным ожидаемым временем. ЗПП ⊆ РП ⊆ БПП, но не известно, отличается ли какой-либо из этих классов сложности друг от друга; то есть алгоритмы Монте-Карло могут иметь большую вычислительную мощность, чем алгоритмы Лас-Вегаса, но это не было доказано. Другой класс сложности, PP, описывает проблемы решения с помощью алгоритма Монте-Карло с полиномиальным временем, который более точен, чем подбрасывание монеты, но где вероятность ошибки не обязательно может быть отделена от¹⁄₂.

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

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

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

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

использованная литература

Цитаты

1. Каргер, Дэвид Р .; Стейн, Клиффорд (июль 1996 г.). «Новый подход к проблеме минимального сокращения». J. ACM. 43 (4): 601–640. Дои:10.1145/234533.234534. ISSN  0004-5411.
2. Куделич, Роберт (2016-04-01). «Рандомизированный алгоритм Монте-Карло для задачи о множестве дуг с минимальной обратной связью». Прикладные мягкие вычисления. 41: 235–246. Дои:10.1016 / j.asoc.2015.12.018.
3. Метрополис, Н. (1987). «Начало метода Монте-Карло» (PDF). Лос-Аламос Сайенс (Специальный выпуск 1987 г., посвященный Станиславу Уламу): 125–130.

Источники

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