Monte Carlo 알고리즘은 backtracking 알고리즘의 성능을 추정할 때 사용하는 알고리즘이다. Monte Carlo 알고리즘은 어떤 입력이 주어졌을 때 그에 따라 생성되는 상태공간트리의 전형적인 경로를 무작위로 생성하고 그 경로상에 있는 노드의 수를 센다. 이 과정을 여러 번 반복하여 나오는 결과의 평균치가 곧 추정치가 된다. 이처럼 Monte Carlo 알고리즘은 무작위 표본의 추정치를 사용하여 무작위 변수의 기대치를 측정하는 확률적 알고리즘이다. 이 알고리즘을 사용하기 위해 만족해야할 조건 2가지는 아래와 같다. ① 상태공간트리에서 같은 수준(level)에 있는 모든 노드에서는 같은 유망함수를 사용해야 한다. ② 상태공간트리에서 같은 수준에 있는 모든 노드들은 같은 수의 자식노드들을 가지..
