[알고리즘] Monte Carlo Algorithm, 몬테카를로 알고리즘

  Monte Carlo 알고리즘은 backtracking 알고리즘의 성능을 추정할 때 사용하는 알고리즘이다. Monte Carlo 알고리즘은 어떤 입력이 주어졌을 때 그에 따라 생성되는 상태공간트리의 전형적인 경로를 무작위로 생성하고 그 경로상에 있는 노드의 수를 센다. 이 과정을 여러 번 반복하여 나오는 결과의 평균치가 곧 추정치가 된다.

  이처럼 Monte Carlo 알고리즘은 무작위 표본의 추정치를 사용하여 무작위 변수의 기대치를 측정하는 확률적 알고리즘이다. 이 알고리즘을 사용하기 위해 만족해야할 조건 2가지는 아래와 같다.

 

<Monte Carlo 알고리즘을 사용하기위해 만족해야할 조건 2가지>

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

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

 

  무작위 표본에 대해 확률적 값을 구하는 만큼 각각의 표본들이 동등한 조건에 놓여져있어야하기 때문이다. 위 조건을 모두 만족한다면 이제 Monte Carlo 알고리즘을 사용하여 알고리즘의 수행시간을 추정할 수 있다.

 

<Monte Carlo 알고리즘을 사용한 backtracking 알고리즘 수행시간 추정 방법>

①  상태공간트리의 각 수준 i 에 있는 노드의 유망한 자식 노드의 개수를 m_i라고 한다. 수준 i의 유망한 자식 노드들 중 유망한 노드 하나를 무작위로 정하고, 그 노드의 유망한 자식 노드의 개수를 다시 m_i+1이라고 한다. 이를 수준 0 에서부터 더 이상 유망한 자식노드가 없을 때까지 이 과정을 반복한다.

② 위 과정을 반복하면서 각 수준 i 에 대해 다양한 값의 m_i가 나오는데, 이 값들의 평균값을 m_i에 다시 저장한다.

③ ti에 수준 i에 있는 한 노드의 자식 노드의 총 개수를 저장한다.

④ 노드의 총 개수의 추정치 = 1 + t₀ + m₀t₁ + m₀m₁t₂ + ··· + m₀m₁···m_i-1t_i + ···(더 이상 유망한 자식노드가 없거나 트리의 끝에 도달할 때 까지) 

 

표본, m_i, t_i에 대한 이해를 돕기 위해 아래 그림을 첨부하였다. 아래 그림의 상태공간트리의 노드는 모두 4개의 자식 노드를 갖고있으며 상태공간트리의 일부가 생략되어있다.

 

 

알고리즘 수도코드

int estimate() {
  node v;
  int m, mprod, t, numnodes;
  
  v = root of state space tree; //초기에는 root
  numnodes = 1;
  m = 1;
  mprod = 1;
  
  while ( m!=0 ) {
    t = number of children of v; //v의 자식의 개수
    mprod = mprod*m;
    numnodes = numnodes + mprod*t;
    m = number of promising children of v; //유망한 것의 개수 
    if ( m!=0 ) //유망한 노드가 하나라도 있으면 계속 검사
      v = randomly selected promising child of v;
    }
    return numnodes;
  }