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

Алгоритми Монте-Карло — це рандомізовані алгоритми, які дають неправильний результат із нетривіально обмеженою верхньою ймовірністю. Однак вони часто більш ефективні порівняно з детермінованими алгоритмами. Однак, повторюючи алгоритм з незалежними випадковими числами, ймовірність помилок можна зменшити (збільшення ймовірності, докладніше в статті увипадковлений алгоритм). На відміну від алгоритмів Монте-Карло, алгоритми Лас-Вегаса дозволяють обчислювати лише правильні рішення.

Алгоритми Монте-Карло служать основою для моделювання за методом Монте-Карло.

Двома прикладами таких алгоритмів є алгоритм Каргера-Штейна ^[1] і алгоритм Монте-Карло для мінімального набору дуг зворотного зв'язку ^[2].

Одностороння та двостороння помилка

Хоча відповідь, яку видає детермінований алгоритм, завжди очікується як правильна, це не стосується алгоритмів Монте-Карло. Для задач про ухвалення рішень ці алгоритми зазвичай класифікуються як упереджені до хибності (false-biased) або упереджені до істинності (true-biased). Алгоритм Монте-Карло з упередженням до “хибності” завжди є правильним, коли він повертає хибність (false); Алгоритм з упередженням до “істинності” завжди є правильним, коли повертає істинність (true). Хоча це описує алгоритми з односторонніми помилками, деякі інші можуть не мати упередженості; про них говорять, що вони мають двосторонні помилки. Відповідь, яку вони надають (або правдива, або помилкова), буде неправильною або правильною з деякою обмеженою ймовірністю.

Наприклад, тест Соловея-Штрассена на простоту використовується для визначення того, чи є дане число простим. Він завжди відповідає істиною (true) для простих чисел, а для складених чисел він відповідає хибністю (false) з ймовірністю не менше 1⁄2 і істиною з ймовірністю, меншою ніж 1⁄2. Таким чином, відповіді хибність (false) від алгоритму є достовірними (тобто гарантовано правильними), тоді як відповіді істинність (true) залишаються невизначеними. Такий алгоритм називають 1⁄2-правильним алгоритмом Монте-Карло з упередженням до хибності.

Підсилення

Для алгоритму Монте–Карло з односторонньою похибкою ймовірність помилки можна зменшити (а ймовірність успіху — підсилити), якщо запустити алгоритм k разів.

Знову розглянемо алгоритм Соловея-Штрассена, який є 1/2-правильним з упередженням до хибності. Можна запустити цей алгоритм кілька разів, повертаючи відповідь хибність (false), якщо хоча б в одній з k ітерацій результат був false, і лише якщо в усіх k ітераціях відповідь true, повернути true. Таким чином, якщо число є простим, то алгоритм завжди повертає true. А якщо число є складеним, то відповідь правильна з ймовірністю щонайменше ${\displaystyle 1-\left(1-{\frac {1}{2}}\right)^{k}=1-2^{-k}}$.

Для алгоритмів Монте–Карло з двосторонньою похибкою ймовірність помилки також можна зменшити шляхом запуску алгоритму k разів, але відповідь визначається за більшістю голосів серед отриманих результатів (majority function).

Класи складності

Клас складності BPP описує задачі прийняття рішення, які можна розв’язати за поліноміальний час за допомогою алгоритмів Монте–Карло з обмеженою ймовірністю двосторонньої похибки. Клас RP описує задачі, що можуть бути розв’язані алгоритмом Монте–Карло з обмеженою ймовірністю односторонньої похибки: якщо правильна відповідь false, алгоритм завжди повертає false, але коли правильна відповідь true, він інколи може повернути false помилково. Натомість клас ZPP описує задачі, розв’язні за поліноміальний сподіваний час алгоритмами типу Лас-Вегас (тобто алгоритмами без похибок). Відомо, що: ${\displaystyle \mathrm {ZPP} \subseteq \mathrm {RP} \subseteq \mathrm {BPP} }$, але наразі невідомо, чи ці класи справді відрізняються один від одного. Іншими словами, алгоритми Монте–Карло можуть мати більшу обчислювальну потужність, ніж алгоритми Лас-Вегас, але це ще не доведено. Ще один клас складності, PP, описує задачі прийняття рішення, для яких існує алгоритм Монте–Карло, що працює за поліноміальний час і є точнішим за випадкове вгадування (підкидання монети), але його ймовірність похибки не обов’язково може бути віддалена від 1⁄2. ^[3]

Література

• Rajeev Motwani, Prabhakar Raghavan: Randomized Algorithms. 1 Auflage. Cambridge University Press, ISBN 978-0-521-47465-8 (doi:10.1017/CBO9780511814075).
• Thomas Müller-Gronbach, Erich Novak, Klaus Ritter: Monte Carlo-Algorithmen. Springer Berlin Heidelberg, Berlin, Heidelberg, ISBN 978-3-540-89140-6 (doi:10.1007/978-3-540-89141-3).
• Adrian Barbu, Song-Chun Zhu: Monte Carlo Methods. Springer Singapore, Singapore, ISBN 9789811329708 (doi:10.1007/978-981-13-2971-5).
• Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized Algorithms. New York: Cambridge University Press. ISBN 0-521-47465-5.
• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 5. Імовірністий аналіз й увипадковлені алгоритми. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
• Berman, Kenneth A.; Paul, Jerome L. (2005). Ch 24. Probabilistic and Randomized Algorithms. Algorithms: Sequential, Parallel, and Distributed. Boston: Course Technology. ISBN 0-534-42057-5.