몬테카를로 알고리즘
Monte Carlo algorithm |
컴퓨팅에서 몬테카를로 알고리즘은 출력이 특정(일반적으로 작은) 확률로 부정확할 수 있는 무작위화된 알고리즘이다. 그러한 알고리즘의 두 가지 예로는 최소 피드백 호 집합에 대한 카거-슈타인 알고리즘과[1] 몬테카를로 알고리즘이 있다.[2]
이 이름은 몬테카를로 모나코 공국의 그랜드 카지노를 일컫는 말로 전 세계적으로 도박의 아이콘으로 잘 알려져 있다. 몬테카를로(Monte Carlo)라는 용어는 니콜라스 메트로폴리스가 1947년 처음 도입했다.[3]
라스베이거스 알고리즘은 오답은 절대 돌려주지 않는 몬테카를로 알고리즘의 이중이다. 그러나 그들은 일의 일부로서 무작위 선택을 할 수도 있다. 결과적으로, 동일한 입력에도 불구하고 런에 걸리는 시간은 달라질 수 있다.
몬테카를로 알고리즘이 제시한 정답이 맞는지 검증하는 절차가 있고, 정답 확률은 0 이상으로 제한돼 있다면, 답을 시험하는 동안 알고리즘을 반복적으로 구동하는 확률로 결국 정답이 나온다. 이 과정이 라스베이거스 알고리즘인지 여부는 확률 1로 중지하는 것이 정의를 충족하는 것으로 간주되는지에 달려 있다.
단측 오차 vs 양측면 오차
결정론적 알고리즘에 의해 반환되는 답은 항상 정확할 것으로 예상되지만, 몬테카를로 알고리즘의 경우는 그렇지 않다. 의사결정 문제의 경우, 이러한 알고리즘은 일반적으로 거짓 편향 또는 참 편향으로 분류된다. 거짓 편향 몬테카를로 알고리즘은 거짓을 반환할 때 항상 정확하고, 참 편향 알고리즘은 참을 반환할 때 항상 정확하다. 이것이 일방적인 오류가 있는 알고리즘을 설명하는 반면, 다른 알고리즘은 편견이 없을 수 있다. 이러한 알고리즘은 양면 오류를 가지고 있다고 한다. 그들이 제공하는 답(참 또는 거짓)은 어떤 한정된 확률로 부정확하거나 정확할 것이다.
예를 들어, Solovay-Strassen 소수점 테스트는 주어진 숫자가 소수인지 여부를 결정하는 데 사용된다. 소수 입력의 경우 항상 참으로 답하고, 복합 입력의 경우 최소한 확률로 거짓으로 답한다. 1/2 및 1/2 미만의 확률로 참. 따라서 알고리즘의 오답은 정확하다고 확신하는 반면, 참답은 불확실하다. 이는 ½-정확한 거짓 편향 알고리즘이라고 한다.
증폭
단측 오류가 있는 몬테카를로 알고리즘의 경우 알고리즘 k번을 실행하면 고장 확률을 줄일 수 있고(그리고 성공 확률을 증폭시킬 수 있다). 1⁄2-정확한 거짓 편향된 솔로베이-스트라센 알고리즘을 다시 생각해 보십시오. 이 알고리즘이 k 반복 내에서 거짓 응답에 도달하면 거짓 답변을 반환하고, 그렇지 않으면 참으로 되돌아오는 경우 이 알고리즘을 실행할 수 있다. 따라서 숫자가 소수일 경우 답은 항상 정확하고, 숫자가 복합적일 경우 답은 최소 1-(1-1⁄2) k= 1-2의−k 확률로 정확하다.
양면 오차가 있는 몬테카를로 의사결정 알고리즘의 경우 알고리즘 k번을 실행하고 답안의 다수 함수를 반환함으로써 고장 확률을 다시 낮출 수 있다.
복잡도 클래스
복잡도 등급 BPP는 양면오차의 경계가 있는 다항시간 몬테카를로 알고리즘으로 해결할 수 있는 의사결정 문제를 기술하고 있으며, 복잡도 등급 RP는 단면오차의 경계가 있는 몬테카를로 알고리즘으로 해결할 수 있는 문제를 기술하고 있다:정답이 거짓이면 알고리즘 al.방법은 그렇게 말하지만, 정답이 사실인 일부 경우에는 거짓으로 잘못 대답할 수 있다. 이와는 대조적으로, 복잡도 등급 ZPP는 다항식 기대 시간 라스베가스 알고리즘으로 해결할 수 있는 문제를 설명한다. ZPP ⊆ RP ⊆ BPP. 그러나 이러한 복잡성 등급들 중 어느 것이라도 서로 구별되는지는 알 수 없다. 즉 몬테카를로 알고리즘은 라스베가스의 알고리즘보다 더 많은 연산 능력을 가질 수 있지만, 이것은 증명되지 않았다. 또 다른 복잡도 등급인 PP는 동전 던지기보다 더 정확하지만 오류 확률을 반드시 1/2로 제한할 수 없는 다항 시간 몬테카를로 알고리즘으로 의사결정 문제를 설명한다.
연산수 이론의 응용
잘 알려진 몬테카를로 알고리즘에는 솔로웨이-스트라센 원시성 테스트, 빌리-가 포함된다.PSW 원시성 테스트, 밀러-라빈 원시성 테스트 및 컴퓨터 그룹 이론에서 슈레이어-심스 알고리즘의 특정 빠른 변형.
참고 항목
- 몬테카를로 방법, 무작위 샘플 채취에 기초한 물리적 시뮬레이션 및 계산 통계에 사용되는 알고리즘
- 애틀랜틱 시티 알고리즘
- 라스베이거스 알고리즘
참조
인용구
- ^ 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 (2016-04-01). "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 (2nd ed.). 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.
