[알고리즘] 되추적(Backtracking) - Part 3 해밀토니안 회로문제(Hamiltonian Circuit Problem)

* 해밀토니안 회로 
 - 연결된 비방향성 그래프에서 어떤 한 정점에서 출발하여 그래프사으이 각 정점을 정확히 한번씩만 경유하여
   다시 출발 정점으로 돌아오는 경로 
 ex)
 

* 해밀토니안 회로문제
 - 연결된 비방향성 그래프에서 해밀토니안 회로를 찾아라
 - 상태공간트리
  > 시작 정점을 트리의 수준(level) 0에 놓는다.
  > 수준 1에 시작 정점이 아닌 정점들을 놓는다.
  > 다른 수준에도 같은 방식으로 시작 정점이 아닌 정점들을 놓는다.
  > 마지막 수준에는 시작 정점을 놓는다.
 - 되추적 방법을 적용하기 위해서 다음 사항을 고려해야한다.
  > 경로상의 i번째 정점은 그 경로상의 (i-1)번째 정점과 반드시 인접해야한다.(인접하지 않으면 패스)
  > (n-1)번째 정점은 반드시 시작 정점과 인접해야한다.(마지막(n번째 level)에는 시작정점이 와야한다)
  > i번째 정점은 첫 (i-1)개의 정점들의 하나가 될 수 없다.(이미 거쳐온 노드는 갈수 없다)
 
* 알고리즘
 void hamiltonian(index i){
   index j;
   if ( promising(i) )
     if ( i == n - 1 ) system.out.print(vindex[0] through vindex[n-1]);
     else
       for ( j = 2 ; j <= n ; j++ ) {
         vindex[i+1] = j;
         hamiltonian(i+1);
      }
   }
   boolean promising(index i){
     index j;
     boolean switch;
     if ( i == n-1 && !W[vindex[n-1]][vindex[0]]) switch = false; // 첫번째 정점은 마지막 정점과 인접
     else if ( i > 0 && !W[vindex[i-1]][vindex[i]]) switch = false; // i번째 정점은 i-1번째 정점과 인접
     else{
       switch = true;
       j = 1;
       while ( j < i  && switch ) { 
         if ( vindex[i] == vindex[j] ) switch = false;
         j++;
       }
     }
     return switch;
   }

 보면 m-coloring 문제와 알고리즘이 비슷하고 효율또안 거의 비슷하다.