사용자:Sepiabrown/몬테카를로 알고리즘
컴퓨팅에서 몬테카를로 알고리즘은 정해진 (일반적으로 적은) 확률만큼만 부정확한 결과를 도출하게끔 할 수 있는 무작위 알고리즘이다. 이러한 알고리즘의 두 가지 예로 Karger–Stein 알고리즘[1]과 minimum Feedback arc set에 대한 Monte Carlo 알고리즘이 있다. [2]
몬테카를로(Monte Carlo)라는 이름은 폴란드 출신 수학자 스타니스와프 울람이 모나코의 유명한 도박의 도시 몬테카를로의 이름을 본따 명명하였다. 몬테카를로라는 용어는 1947년 Nicholas Metropolis에 의해 처음 소개되었다. [3]
라스베가스 알고리즘 은 절대 오답을 반환하지 않는 몬테카를로 알고리즘의 듀얼 이지만 작업의 일부로 무작위 선택을 할 수 있습니다. 결과적으로 동일한 입력을 사용하더라도 실행 간에 소요되는 시간이 다를 수 있습니다.
몬테카를로 알고리즘에 의해 주어진 답이 정확한지 검증하는 절차가 있고 정답일 확률이 0보다 크다면, 답을 테스트하면서 알고리즘을 반복적으로 실행하는 프로세스가 결국 정답을 줄 사건은 거의 확실하게 발생한다. 이 프로세스가 라스베가스 알고리즘인지는 라스베가스 알고리즘의 정의에 프로세스가 중지되는 사건이 거의 확실하게 발생하는 프로세스를 포함시키는지 여부에 따라 다르다.
단측 오류 대 양측 오류[편집]
결정적 알고리즘에 의해 반환된 답은 항상 정확할 것으로 예상되지만 몬테카를로 알고리즘의 경우는 그렇지 않다. 결정 문제의 경우 이러한 알고리즘은 일반적으로 거짓 편향 또는 참 편향으로 분류된다. 거짓 편향된 Monte Carlo 알고리즘은 거짓을 반환할 때 항상 정확하다. 참 편향된 Monte Carlo 알고리즘은 참을 반환할 때 항상 정확하다. 이것은 단방향 오류가 있는 알고리즘을 설명하지만 다른 알고리즘은 편향이 없을 수도 있고 이들은 양측 오류 가 있다고 한다. 양측 오류들이 제공하는 대답( true 또는 false )은 어느 정도 제한된 확률로 부정확하거나 정확하다.
예를 들어, Solovay-Strassen 소수성 검정은 주어진 숫자가 소수 인지 여부를 결정하는 데 사용됩니다. 소수 입력에 대해 항상 true로 응답합니다. 복합 입력의 경우 최소한 확률로 거짓으로 답합니다.1⁄2 이고 확률이 다음보다 낮을 때 참1⁄2 . 진정한 답은 여전히 불확실 반면 따라서, 알고리즘에서 거짓 답변, 정확한 것으로 확신한다; 이것은 라고 한다1⁄2 올바른 거짓 편향 알고리즘 .
단측 오류가 있는 Monte Carlo 알고리즘의 경우 알고리즘을 k 번 실행하여 실패 확률을 줄이고 성공 확률을 높일 수 있습니다. Solovay-Strassen 알고리즘을 다시 고려하십시오.1⁄2 - 잘못된 편향 수정 . 하나는이 알고리즘을 여러 번이 K 반복에서 거짓 반응에 도달하면 잘못된 대답을 반환하고, 그렇지 않으면 진정한 반환을 실행할 수 있습니다. 따라서 숫자가 소수이면 답은 항상 정확하고 숫자가 합성이면 답은 최소한 1 − (1 −1⁄2 ) k = 1 − 2 − k .
양측 오류가 있는 Monte Carlo 결정 알고리즘의 경우 알고리즘을 k 번 실행하고 답변 의 다수 함수 를 반환하여 실패 확률을 다시 줄일 수 있습니다.
복잡성 클래스[편집]
복잡도 클래스 BPP 는 양면 오류의 유계 확률을 사용하여 다항식 시간 몬테카를로 알고리즘으로 해결할 수 있는 결정 문제 를 설명하고, 복잡도 클래스 RP 는 유계 확률이 1인 몬테카를로 알고리즘으로 해결할 수 있는 문제를 설명합니다. 양면 오류: 정답이 false 이면 알고리즘은 항상 그렇게 말하지만 정답이 true 인 경우에 따라 false 로 잘못 응답할 수 있습니다. 대조적으로, 복잡도 클래스 ZPP 는 다항식 예상 시간 라스베가스 알고리즘으로 해결할 수 있는 문제를 설명합니다. ZPP ⊆ RP ⊆ BPP, 그러나 이러한 복잡성 클래스가 서로 구별되는지 여부는 알려져 있지 않습니다. 즉, 몬테카를로 알고리즘은 라스베가스 알고리즘보다 더 많은 계산 능력을 가질 수 있지만 이것은 입증되지 않았습니다. 또 다른 복잡성 클래스인 PP 는 동전을 던지는 것보다 더 정확하지만 오류 확률이 반드시 경계를 벗어날 수 없는 다항식 시간 몬테카를로 알고리즘의 결정 문제를 설명합니다.1⁄2 .
계산 정수론에서의 응용[편집]
잘 알려진 Monte Carlo 알고리즘에는 Solovay-Strassen 소수성 테스트, Baillie-PSW 소수성 테스트, Miller-Rabin 소수성 테스트 및 계산 그룹 이론 에서 Schreier-Sims 알고리즘 의 특정 빠른 변형이 포함됩니다.
- Monte Carlo 방법, 물리적 시뮬레이션에 사용되는 알고리즘 및 무작위 샘플 채취를 기반으로 하는 계산 통계
- 애틀랜틱시티 알고리즘
- 라스베가스 알고리즘
참고문헌[편집]
인용[편집]
출처[편집]
- Motwani, Rajeev; Raghavan, Prabhakar (1995). 《Randomized Algorithms》. New York: Cambridge University Press. ISBN 0-521-47465-5.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). 〈Ch 5. Probabilistic Analysis and Randomized Algorithms〉. 《Introduction to Algorithms》 2판. Boston: MIT Press and McGraw-Hill. ISBN 0-262-53196-8.
- 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.
- ↑ Kudelić, Robert (2016년 4월 1일). “Monte-Carlo randomized algorithm for minimal feedback arc set problem”. 《Applied Soft Computing》 41: 235–246. doi:10.1016/j.asoc.2015.12.018.
- ↑ Metropolis, N. (1987). “The beginning of the Monte Carlo method” (PDF). 《Los Alamos Science》 (1987 Special Issue dedicated to Stanislaw Ulam): 125–130.