알고리즘: 몬테칼로 알고리즘을 이용한 효율성 추적!

알고리즘: 되추적(Backtracking) 공부하기! (N-Queens problem을 풀어보자)

 

이 전의 포스팅에서 되추적 알고리즘의 효율성에 대해서 문제 삼았고 이를 해결하지 못했다. 

 

되추적 알고리즘이 어떤 특정 사례를 얼마나 효율적으로 처리하는지에 대한 추정치가 있다면

 

그 사례에 대해서 그 알고리즘을 사용하는게 타당한 지 결정할 수 있다.

 

몬테칼로 알고리즘은 확률 알고리즘이기 때문에 표본공간의 무작위 표본의 평균치를

 

가지고 표본공간에서 정의된 무작위변수의 기대치를 추정한다. 

 

몬테칼로 알고리즘은 가지친 상태공간트리에서 마디 개수의 추정치를 찾는다.

 

이 알고리즘을 적용하기 위해서는 다음 조건을 반드시 만족해야한다. 

 

 

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

 

2. 상태공간트리에서 같은 수준에 있는 모든 노드들은 같은 수의 자식노드들을 

가지고 있어야 한다. 

 

 

 

mi를 수준 i에 있는 노드의 유망한 자식노드의 개수

ti를 수준 i에 있는 한 노드의 자식 노드의 총 개수라고 할때

 

되추적 알고리즘이 해답을 모두 찾기 위해서 검사한 마디의 총 개수 추정치는 다음과 같다.

 

 

 

이를 수도코드로 구현한다면 다음과 같다. 

 

int estimate(){

	node v;
	int m, mprod, t, numnodes;
    
    v = root of state space tree;
    numnodes = 1;
    m = 1;
    mprod = 1;
    
    while(m != 0){
    t = number of childern of v
    mprod = mprod * m;
    numnodes = numnodes + mprod* t;
    m = number of promising childern of v;
    if(m!=0)
    	v = randromly selected promising child of v;
    
    }
    return numnodes;

}

 

 

 

 

몬테칼로 알고리즘을 n-여왕문제에 적용시켰을 경우

 

int estimate_n_queen(int n){
	index i, j, col[1..n];
    in m, mprod, numnodes;
    set_of_index prom_childern;
    i = 0; numnodes =1; m = 1; mprod = 1;
    while(m != 0 && i!=n){  // i가 끝까지 가기전
    	mprod = mprod*m;
        numnodes = numnodes + mprod*n;  //자식마디의 개수는 t
        i++; m = 0; prom_children = 공집합;  //유망한 자식마디의 집합을 공집합으로 초기화
        for(j = 1; j <= n; j++){
        col[i] = j;
        if(promising(i)){
			m++;
            prom_children = prom_childrn U {j};
            }
		}
        if(m!=0){
        	j = random selection from prom_children; //무작위로 자식노드에서 선택
            col[i] = j
        }
    
    }
    return numnodes
}

 

 

몬테칼로 알고리즘을 사용할 때는 두 번이상 실행하여 추정치를 구해야 하고,

그 결과의 평균을 실제 추정치로 사용해야 한다.

 

경험적으로 보면 20번 정도 시도가 적당하다고 한다. 

 

 

출처 : Foundations of Algorithms, Using C++ Pseudocode