무작위 알고리즘은 유명한 도박 도시의 이름을 딴 두 가지 범주로 나뉩니다:
- 라스베이거스 알고리즘은 정답을 찾는 것이 보장되지만, 실행에 비결정적인 시간이 필요합니다. 예를 들어, Quicksort가 이러한 알고리즘입니다.
- 몬테카를로 알고리즘은 결정적인 실행 시간을 필요로 하지만, 어느 정도의 확률로 잘못된 답을 낼 수 있습니다. 예를 들어, 소수 판별은 거의 항상 어느 정도의 오류 확률을 수반합니다.
수치 해석 분야에서 몬테카를로 알고리즘은 높은 정확도가 필요하지 않은 경우에 어떤 값을 계산하는 데 자주 사용됩니다.
#넓이 계산
다음 문제를 살펴봅시다. 도시의 지도(간단히 하기 위해 단위 정사각형이라고 가정합니다)와 기지국들의 좌표 및 각 기지국의 통신 반경 목록이 주어집니다. 이 도시의 커버리지 넓이, 즉 도시의 점들 중 적어도 하나의 기지국의 통신 반경 안에 있는 점들의 비율을 구해야 합니다.
이 문제는 단위 정사각형과 원들의 합집합의 교집합 넓이를 구하는 문제로 바꾸어 말할 수 있습니다. 이 문제에는 정확하지만 매우 복잡한 해법이 있습니다. 이 해법은 두 도형이 교차하는 모든 ‘관심 지점’을 구하고, 그 지점들을 따라 스위프 라인을 진행시키며, 교차점이 없는 각 구간마다 자명하지 않은 적분을 한 무더기(힙)씩 계산해야 합니다. 이 해법은 실수 연산이 허용하는 만큼 정확하지만, 느리고 계산 기하학 비전문가가 구현하기에는 매우 까다롭습니다.
이 모든 것 대신 다음과 같이 할 수 있습니다. 정사각형 위에서 무작위 점을 여러 개 뽑고, 각 점이 어떤 원에든 덮여 있는지를 간단한 술어를 사용하여 독립적으로 확인하는 것입니다.
$$ (x-x_i)^2 + (y-y_i)^2 \leq r_i^2 $$그러면 덮인 점의 비율이 답의 추정값이 되며, 점을 충분히 많이 뽑았다면 이 추정값은 실제 값에 가까워집니다.
답의 정확도에 대해 어떤 형식적인 요구 사항이 있다면, 예를 들어 적어도 99%의 경우에 3자리의 정확한 유효 숫자를 얻어야 한다면, 몇 개의 점을 확인해야 합니까?
임의로 1에 가까운 확률로 $k$개의 올바른 자릿수를 얻으려면 $n = \Theta(10^{2k})$개의 점이 필요하다는 것을 보일 수 있습니다.
이 사실의 증명은 확률론 단원을 참고하십시오.