Алгоритм Монте-Карло
Перейти до навігації
Перейти до пошуку
| Алгоритм Монте-Карло | |
| Названо на честь | Монте-Карло |
|---|---|
| Протилежне | Лас-Вегас |
Алгоритми Монте-Карло — це рандомізовані алгоритми, які дають неправильний результат із нетривіально обмеженою верхньою ймовірністю. Однак вони часто більш ефективні порівняно з детермінованими алгоритмами. Однак, повторюючи алгоритм з незалежними випадковими числами, ймовірність помилок можна зменшити (збільшення ймовірності, докладніше в статті увипадковлений алгоритм). На відміну від алгоритмів Монте-Карло, алгоритми Лас-Вегаса дозволяють обчислювати лише правильні рішення.
Алгоритми Монте-Карло служать основою для моделювання за методом Монте-Карло.
Двома прикладами таких алгоритмів є алгоритм Каргера-Штейна [1] і алгоритм Монте-Карло для мінімального набору дуг зворотного зв'язку [2].
- 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.
- ↑ Karger, David R.; Stein, Clifford (July 1996). A New Approach to the Minimum Cut Problem. J. ACM. 43 (4): 601—640. doi:10.1145/234533.234534. ISSN 0004-5411. S2CID 5385337.
- ↑ Kudelić, Robert (1 квітня 2016). Monte-Carlo randomized algorithm for minimal feedback arc set problem. Applied Soft Computing. 41: 235—246. doi:10.1016/j.asoc.2015.12.018.