몬테카를로 알고리즘(MonteCarlo Algorithm)

몬테카를로 알고리즘

 

몬테카를로 알고리즘은 무작위로 문제를 해결하거나 탐색하는 기법으로, 랜덤한 선택을 통해 해답을 찾고,

해당 해답이 올바른지 여부를 평가하는 과정을 반복하는 확률적 또는 추정 기반문제 해결에 사용한다.

그렇기에 결과가 항상 정확하지는 않지만 빠르게 근사치 해를 찾을 수 있는 경우가 많다.

백트래킹과 DFS는 체계적인 탐색을 통해 최적의 답을 보장하지만, 몬테카를로는 무작위 탐색을 통해 빠른 근사 해를 찾는 방식이다. 따라서 백트래킹은 완전 탐색방식이라면, 몬테카를로 알고리즘은 불확실성과 확률에 기반한 방식이다.

 

조건

상태 공간 트리에서 같은 수준(Level)에 있는 모든 노드에서는 같은 유망함수를 사용해야 한다.

상태 공간 트리에서 같은 수준에 있는 모든 노드들은 같은 수의 자식노드들을 가지고 있어야 한다.

 

예시

 

몬테카를로 알고리즘의 예시로는 원주율 구하기가 있다.

1. 정사각형을 그링 후 그 안에 사분면을 삽입한다.

2. 정사각형 위에 일정한 개수의 점을 균일하게 분포한다.

3. 사분면 내부의 점, 즉 원점으로 부터 1만의 개수를 센다.

4. 내부의 개수와 전체 개수의 비율은 두 영역의 비율을 나타내므로 그 값에 4를 곱하여 파이를 만든다.

 

코드 구현