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

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

В вычисление, а Алгоритм Монте-Карло это рандомизированный алгоритм чей вывод может быть неправильным с определенным (обычно маленьким) вероятность. Два примера таких алгоритмов: Алгоритм Каргера – Стейна[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, то Тест на простоту Миллера – Рабина, и некоторые быстрые варианты Алгоритм Шрайера – Симса в вычислительная теория групп.

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

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

Цитаты

  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.CS1 maint: ref = harv (ссылка на сайт)

Источники