알고리즘: 해밀턴 회로문제(Hamiltonian Circuit Problem)(Backtracking 문제)

해밀턴 회로문제(HCP)를 알아보기전에 외판원 문제(TSP)에 대해 간단히 알아보자 

 

이전에 외판원 문제(TSP)에 대해 포스팅했었다. 

 

알고리즘: TSP 외판원문제 알고리즘 공부하기(동적 프로그래밍)(feat. c++, 의사코드)

 

 

외판원 문제(TSP)의 경우 가장 빠른 방법으로 20개의 도시를 모두 돌고 돌아오는데

 

걸리는 시간을 계산하면 약 45초가 소요된다.

(brute force를 이용하면 19!으로 3800년이상 걸린다)

 

TSP의 time complexity

 

 

 

이번에는 인풋이 두배일때, 즉 40개의 도시를 모두 돌고 출발점으로 돌아온다고 가정하자. 

 

동적계획 알고리즘이 단위연산을 처리하는데 걸리는 시간이 1ms이라 가정했을 때

TSP를 사용한다면 6.46년이 걸린다. 

 

 

 

시간이 너무 오래 걸리므로 다른 알고리즘을 찾아보는게 좋을 것이다. 

 

그래서 이번에는 최적 여행경로는 찾을 수 없을 것이라 판단하고,

 

그냥 아무경로나 선택하더라도 모든 도시를 한번씩 돌고 오는 경로를 찾을 것이다. 

 

이 문제를 처음 제안한 윌리암 해밀턴(William Hamilton)의 이름을 따서

해밀턴 회로 문제(Hamiltonian Circuit Problem)이라고 한다.

 

이 문제는 방향그래프로도 기술할 수 있고 비방향 그래프로도 기술할 수 있다. 

 

연결된 비방향 그래프에서 해밀턴 회로는 한 정점에서 출발하여 그래프에 있는 모든 정점을

각각 정확히 한 번씩 방문하고, 다시 출발한 정점으로 돌아오는 경로이다. 

 

 

 

예를 들어 다음과 같은 경로가 있을 때 모든 점을 지나고 출발점으로 돌아오는 경우를 구해보자

 

 

 

해답)

 

 

 

 

 

해밀턴 회로 문제는 상태공간트리에서 되추적 알고리즘을 이용하여 구할 수 있다. 

 

단, 다음과 같은 사항을 고려해서 되추적해야한다.

 

1. 경로 상의 i번째 정점은 그 경로에서 (i-1)번째 정점과 반드시 이웃해야 한다.

2. (n-1)번쨰 정점은 0번째 정점과 이웃해야 한다. 

3. i번째 정점은 처음 i-1개의 정점이 될 수 없다. 

(모든 노드가 서로 다 연결되어 있으면 안된다)

 

 

 

 

 

위 방식을 고려하여 수도코드로 나타내보면 다음과 같다.

 

void hamiltonian(index i){
	
    index j;
    if(promising(i))
    	if(i == n-1)
        	cout << vindex[0]에서 vindex[n-1]까지;
        else
        	for(j = 2; j <= n; j++){  // 시작을 제외한 모든 정점에 대해서 시도 
            	vindex[i+1] = j;
                hamiltonian(i + 1);
            }


}
bool promising(index i){
	
    index j;
    bool 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;
    else{
    	switch = true;
        j = 1;
        while (j < i && switch){  // i번째 정점이 이미 선택되었는지 검사 
        	if(vindex[i] == vindex[j])
            	switch =false
            j++;
        }
	}
    return switch;
}

 

 

 

 

HCP의 상태공간트리에서 마디의 개수는 다음과 같다. 

 

 

마디의 개수로만 보면 TSP와 복잡도가 비슷하다.

 

그런데도 불구하고 왜 우리는 HCP를 사용할까?

 

우선 해밀턴 알고리즘은 외판원 알고리즘보다 40개의 도시 사례를 푸는데 더 오래 걸릴 가능성이 존재한다.

 

몬테칼로 기술을 사용할 수 있는 조건을 만족하므로 40개의 사례에 대한 효율을 추정할 수 있다.

 

하지만 몬테칼로는 모든 회로를 찾는데 걸리는 시간을 추정한다.

 

해밀턴 회로는 하나의 가능한 경로만 찾으면 되므로 일반적으로 HCP가 TSP보다 빠르다.

 

(HCP로 얻는 solution이 마지막에 나온다면 TSP와 비슷하다.

 

그러므로 항상 빠르다고는 할 수는 없지만 일반적으로 빠른 것이다.)

 

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