В вычислительной технике алгоритм Монте-Карло — это рандомизированный алгоритм , выход которого может быть неверным с определенной (обычно небольшой) вероятностью . Двумя примерами таких алгоритмов являются алгоритм Каргера–Штейна [1] и алгоритм Монте-Карло для минимального набора дуг обратной связи . [2]
Название отсылает к казино Монте-Карло в княжестве Монако , которое известно во всем мире как икона азартных игр. Термин «Монте-Карло» был впервые введен в 1947 году Николасом Метрополисом . [3]
Алгоритмы Лас-Вегаса являются дуалами алгоритмов Монте-Карло и никогда не возвращают неправильный ответ. Однако они могут делать случайный выбор в ходе своей работы. В результате время выполнения может различаться между запусками, даже при одинаковых входных данных.
Если существует процедура проверки правильности ответа, выдаваемого алгоритмом Монте-Карло, и вероятность правильного ответа ограничена выше нуля, то с вероятностью единица многократное выполнение алгоритма при проверке ответов в конечном итоге даст правильный ответ. Является ли этот процесс алгоритмом Лас-Вегаса, зависит от того, считается ли остановка с вероятностью единица удовлетворяющей определению.
Хотя ответ, возвращаемый детерминированным алгоритмом , всегда должен быть правильным, это не относится к алгоритмам Монте-Карло. Для задач принятия решений эти алгоритмы обычно классифицируются как либо с ложной , либо с истинной ошибкой. Алгоритм Монте-Карло с ложной ошибкой всегда верен, когда возвращает false ; алгоритм с истинной ошибкой всегда верен, когда возвращает true . Хотя это описывает алгоритмы с односторонними ошибками , другие могут не иметь никакой ошибки; говорят, что они имеют двусторонние ошибки . Ответ, который они предоставляют (либо true , либо false ), будет неверным или правильным с некоторой ограниченной вероятностью.
Например, тест простоты Соловея-Штрассена используется для определения, является ли заданное число простым числом . Он всегда отвечает true для входных данных простых чисел; для составных входных данных он отвечает false с вероятностью не менее 1 ⁄ 2 и true с вероятностью менее 1 ⁄ 2 . Таким образом, ложные ответы алгоритма наверняка будут правильными, тогда как истинные ответы остаются неопределенными; это называется 1 ⁄ 2 -корректным алгоритмом с ложной предвзятостью .
Для алгоритма Монте-Карло с односторонними ошибками вероятность неудачи может быть уменьшена (а вероятность успеха увеличена) путем запуска алгоритма k раз. Рассмотрим снова алгоритм Соловея–Штрассена, который является 1 ⁄ 2 -корректным ложно-смещенным . Можно запустить этот алгоритм несколько раз, возвращая ложный ответ, если он достигает ложного ответа в течение k итераций, и в противном случае возвращая true . Таким образом, если число простое, то ответ всегда правильный, а если число составное, то ответ правильный с вероятностью не менее 1−(1− 1 ⁄ 2 ) k = 1−2 −k .
Для алгоритмов принятия решений Монте-Карло с двусторонней ошибкой вероятность отказа можно снова уменьшить, запустив алгоритм k раз и вернув функцию большинства ответов.
Класс сложности BPP описывает задачи принятия решений , которые могут быть решены с помощью алгоритмов Монте-Карло с полиномиальным временем решения с ограниченной вероятностью двусторонних ошибок, а класс сложности RP описывает задачи, которые могут быть решены с помощью алгоритма Монте-Карло с ограниченной вероятностью односторонней ошибки: если правильный ответ — false , алгоритм всегда так говорит, но он может ответить false неверно для некоторых случаев, когда правильный ответ — true . [4] Напротив, класс сложности ZPP описывает задачи, решаемые с помощью алгоритмов Лас-Вегаса с полиномиальным ожидаемым временем. ZPP ⊆ RP ⊆ BPP , но неизвестно, отличается ли какой-либо из этих классов сложности друг от друга; то есть алгоритмы Монте-Карло могут иметь большую вычислительную мощность, чем алгоритмы Лас-Вегаса, но это не было доказано. [4] Другой класс сложности, PP , описывает задачи принятия решений с помощью алгоритма Монте-Карло с полиномиальным временем решения, который точнее, чем подбрасывание монетки, но где вероятность ошибки не обязательно может быть ограничена 1 ⁄ 2 . [4]
Рандомизированные алгоритмы в основном делятся на два основных типа: Монте-Карло и Лас-Вегас, однако они представляют собой лишь вершину иерархии и могут быть далее классифицированы. [4]
«И Лас-Вегас, и Монте-Карло имеют дело с решениями, т. е. проблемами в их версии решений ». [4] «Однако это не должно создавать неправильного впечатления и ограничивать эти алгоритмы такими проблемами — оба типа рандомизированных алгоритмов могут использоваться и для числовых задач, задач, где выход — это не просто «да»/«нет», а где нужно получить результат, который является числовым по своей природе». [4]
Предыдущая таблица представляет собой общую структуру для рандомизированных алгоритмов Монте-Карло и Лас-Вегаса. [4] Вместо математического символа можно использовать , таким образом делая вероятности в худшем случае равными. [4]
К известным алгоритмам Монте-Карло относятся тест простоты Соловея–Штрассена, тест простоты Бейли–ПСВ , тест простоты Миллера–Рабина и некоторые быстрые варианты алгоритма Шрайера–Симса в вычислительной теории групп .
Для алгоритмов, входящих в группу алгоритмов стохастической оптимизации (SO), где вероятность заранее неизвестна и определяется эмпирически, иногда можно объединить Монте-Карло и такой алгоритм, «чтобы иметь как вычисленную заранее границу вероятности, так и компонент стохастической оптимизации». [4] «Примером такого алгоритма является Монте-Карло, вдохновленный Ant ». [4] [5] Таким образом, «недостатки SO были смягчены, и была установлена уверенность в решении». [4] [5]
