몬테카를로 알고리즘
비슷한 이름의 몬테카를로 방법에 관해서는 해당 문서를 참조하십시오.컴퓨팅에서 몬테카를로 알고리즘은 항상 유한한 시간 안에 멈추지만, 특정 확률(주로 낮은 확률)로 부정확할 수도 있는 결과를 도출하는 무작위 알고리즘이다. 이러한 알고리즘의 두 가지 예로 카거-스테인 알고리즘[1]과 최소 피드백 아크 집합에 대한 몬테카를로 알고리즘이 있다.[2]
몬테카를로(Monte Carlo)라는 용어는 1947년 니콜라스 메트로폴리스가 제안한 이름이다.[3] 그의 동료였던 폴란드 출신 수학자 스타니스와프 울람에게는 삼촌이 있었는데, 그는 모나코의 유명한 도박의 도시 몬테카를로에서 도박을 하기 위해 친척들의 돈을 종종 빌려갔다. 몬테카를로 알고리즘 또한 무작위성이 있으므로 이로부터 이름이 유래된 것이 지금까지 이어져 내려왔다.
라스베가스 알고리즘은 부정확할 수도 있는 결과를 절대 반환하지 않는 몬테카를로 알고리즘의 듀얼이다. 이 때문에 라스베가스 알고리즘은 몬테카를로 알고리즘과 다르게 무작위 선택을 하지 않는다고 오해할 수 있다. 그러나 라스베가스 알고리즘 또한 시행의 일부로 무작위 선택을 할 수 있다. 그 결과, 동일한 입력을 사용하더라도 실행 간에 소요되는 시간이 다를 수 있다.
만약 몬테카를로 알고리즘에 의해 주어진 답이 정확한지 검증하는 절차가 있고 정답일 확률이 0보다 크다면, 답을 테스트하면서 알고리즘을 반복적으로 실행하는 프로세스가 결국 정답을 줄 사건은 거의 확실하게 발생한다. 이 프로세스가 라스베가스 알고리즘인지는 라스베가스 알고리즘의 정의에 프로세스가 중지되는 사건이 거의 확실하게 발생하는 프로세스를 포함시키는지 여부에 따라 다르다.
단측 오류 대 양측 오류[편집]
결정적 알고리즘에 의해 반환된 답은 항상 정확할 것으로 예상되지만 몬테카를로 알고리즘의 경우는 그렇지 않다. 결정 문제의 경우 몬테카를로 알고리즘은 일반적으로 거짓 편향 또는 참 편향으로 분류된다. 거짓 편향된 몬테카를로 알고리즘은 거짓을 반환할 때 항상 정확하다. 반대로 참 편향된 몬테카를로 알고리즘은 참을 반환할 때 항상 정확하다. 이러한 거짓 편향과 참편향이 있는 몬테카를로 알고리즘을 단측 오류가 있다고 한다. 반면, 거짓 편향과 참편향의 두 분류에 속하지 않는, 즉 편향이 없는 몬테카를로 알고리즘 또한 존재할 수 있다. 이들은 양측 오류가 있다고 한다. 양측 오류가 있는 몬테카를로 알고리즘이 도출하는 참 또는 거짓의 답은 어느 정도 제한된 확률로 부정확할 수 있다.
예를 들어, 솔로바이-슈트라센 소수판별법은 주어진 숫자가 소수인지 여부를 결정하는 데 사용된다. 이 검정은 소수 입력에 대해 항상 참으로 답한다. 합성수 입력의 경우 1⁄2 이상의 확률로 거짓으로 답하고 1⁄2 이하의 확률로 참으로 답한다. 따라서 이 검정이 거짓으로 도출한 답은 그 답이 정확하다고 확신할 수 있는 반면에, 참으로 도출한 답은 정확한지 확신할 수 없다. 이런 방식의 알고리즘을 1⁄2-옳은 거짓 편향 알고리즘이라 부른다.
증폭[편집]
단측 오류가 있는 몬테카를로 알고리즘의 경우 알고리즘을 k 번 실행하여 실패 확률을 줄이고 성공 확률을 증폭시킬 수 있다. 솔로바이-슈트라센 알고리즘의 1⁄2-옳은 거짓 편향 알고리즘을 다시 고려하자. 솔로바이-슈트라센 알고리즘으로 시행을 k번 반복하는 동안 거짓 반응에 도달하면 거짓이라는 답을 반환하고, 그렇지 않으면 참이라는 답을 반환하면서 알고리즘을 여러번 실행한다고 하자. 만약 숫자가 소수이면 답은 항상 옳고 숫자가 합성수이면 답은 최소한 1 − (1 −1⁄2 ) k = 1−2−k 이상의 확률로 옳다.
양측 오류가 있는 몬테카를로 결정 알고리즘의 경우 한 시행에서 k번 실행하고 도출된 답의 다수 함수를 반환하여 실패 확률을 다시 줄일 수 있다.
복잡성 클래스[편집]
복잡도 클래스 BPP는 양측 오류에 대한 유계 오류 확률을 갖는 다항 시간 몬테카를로 알고리즘으로 해결할 수 있는 결정 문제를 표현한다. 복잡도 클래스 RP는 단측 오류에 대한 유계 오류 확률이 1인 몬테카를로 알고리즘으로 해결할 수 있는 문제를 표현한다. 즉, 만약 정답이 거짓이면 알고리즘 또한 항상 거짓을 반환하지만, 정답이 참이면 경우에 따라 옳지 않은 답인 거짓을 잘못 반환할 수 있다. 대조적으로, 복잡도 클래스 ZPP는 다항 기대 시간 라스베가스 알고리즘으로 해결할 수 있는 문제를 표현한다. 따라서 위 복잡도 클래스들의 관계는 ZPP ⊆ RP ⊆ BPP로 나타낼 수 있다. 그러나 이러한 복잡성 클래스들이 서로 구별되는지 여부는 알려져 있지 않다. 즉, 몬테카를로 알고리즘은 라스베가스 알고리즘보다 더 큰 계산 능력을 가질지도 모르지만 이는 아직 증명되지 않았다. 또 다른 복잡도 클래스인 PP는 동전을 던지는 것보다는 더 정확하지만 오류 확률이 모든 시행에서 1⁄2 보다 낮다고는 할 수 없는 다항 시간 몬테카를로 알고리즘의 결정 문제를 표현한다.
계산 정수론에서의 응용[편집]
잘 알려진 몬테카를로 알고리즘에는 솔로바이-슈트라센 소수판별법, 베일리–PSW 소수판별법, 밀러-라빈 소수판별법 및 계산적 군론에서 Schreier-Sims 알고리즘의 실행속도를 높인 특정 변형이 포함된다.
같이 보기[편집]
- 몬테카를로 방법 : 물리 시뮬레이션과 계산 통계에서 사용되는 무작위 샘플 채취를 기반으로 수치적 계산의 근사를 위한 알고리즘
- 애틀랜틱시티 알고리즘
- 라스베가스 알고리즘
참고 문헌[편집]
인용[편집]
- ↑ 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.
출처[편집]
- 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.