[알고리즘] Traveling Salesman Problem

ㅋㅋ

 

개요

 따로 알고리즘 포스팅을 하는건 union-find 이후 1년만이다

사실 코테에 나올 확률이 매우 드문 알고리즘이라고 생각해 본인이 코테 대비만 한다면 굳이 알 필요는 없을 것 같지만.. 개인적인 호기심으로 작년 말부터 정리해야겠다 생각은 했는데, 그동안 놓았던 ps를 다시 감을 잡고 돌아오는데 시간이 많이 걸렸다.

 

위키를 보면 Travelling Salesman Problem(이하 TSP)를 다음과 같이 설명하고 있다.

"Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"

 

즉 가중치가 존재하는 양방향 그래프에서, 모든 노드를 한 번씩 방문하고 출발점으로 돌아오는 경우의 수 중 가장 가중치의 합이 작은 경로를 찾는 문제이다. 

 

 

브루트 포스

 가장 쉬운 방법은 모든 도시를 순회하는 모든 경우의 수를 구하는 것이다. 도시(정점)가 n개라고 하면, n개의 점을 순차 방문하는 경우의 수는 n!개임을 알 수 있다. 물론 팩토리얼의 시간복잡도를 가지는 만큼 매우 비효율적이다. 대신 동적 계획법을 사용할 수 있다.

 

 

동적 계획법

아이디어

위와 같은 브루트포스 문제는 대부분의 경우 동적 계획법을 사용하여 시간복잡도를 줄일 수 있다고 알려져 있다.

TSP에도 일반적으로 동적 계획법이 사용된다. dp의 핵심이 점화식인 이유는 n값에 상관없이 일정한 규칙을 찾는 것이 핵심이기 때문이다. 점화식을 찾아보자.

 

이해를 위해 쉽게 A~E까지 5개의 도시가 있을 때, 1, 2번째 도시를 방문하는 최적값이 A, B 순서라고 하자. 3번째 도시를 방문하려면 다음 세가지 경우의 수가 존재하며, 이 중 최소의 가중치를 가지는 경우의 수가 답이 된다.

1. C를 방문하고, 이후 D, E를 최소 가중치로 방문
2. D를 방문하고, 이후 C, E를 최소 가중치로 방문
3. E를 방문하고, 이후 C, D를 최소 가중치로 방문

 

위 문장을 살펴보면, *를 방문하고, 이후 남은 도시를 방문하는 최소 가중치의 합이 최종적인 답이 된다.

다시 말하면 (방문하지 않은 점들 중 하나를 방문했을 때 가중치) + (그 점을 제외한 나머지 점들을 방문했을 때의 가중치)가 된다.

 

점화식 도출

dp[i][visited]를 현재 위치가 i이고, 방문 상태가 visited일때 남은 점들을 최소 거리로 돌았을 떄의 남은 이동 거리라고 하자.

visited는 방문 상태를 의미하므로, 비트 마스킹을 이용하여 0-1로 방문 상태를 표시할 것이다. (당연히 리스트로도 표현할 수 있다)

예를 들어, 현재 위치가 3이고 1,2번쨰 도시를 방문했다면 i=3, visited=00011(2) = 24가 된다.
2^(n-1)번째 자리가 n번 도시를 방문했는지 여부를 나타내는 것.

 

 

따라서 다음과 같은 점화식이 나온다.

dp[i][visited] = min(dp[next][visited | (1 << next)] + graph[i][j]), dp[i][visited])

 

앞서 말했듯이 (방문하지 않은 점들 중 하나를 방문했을 때 가중치) + (그 점을 제외한 나머지 점들을 방문했을 때의 가중치)와 기존값을 비교하여 가중치가 더 작은 값을 적용하는 것이다.

 

시작점을 어디로 잡는가는 중요하지 않다

어떤 도시에서 시작하든, TSP의 핵심은 모든 도시의 탐색을 마치고 '재방문 없이 시작 도시로 돌아오는 것', 즉 사이클에 속해 있다.

 

구현

이제 구현이다. 위에서 구한 점화식에다 dfs를 통해서 다음에 방문할 도시를 검사할 것이다.

문제는 백준에 있는 대표적인 TSP문제를 사용하였다.

 

private static int dfs(int cur, int visited) {
    if(visited == (1<<N)-1) { // 모든 도시를 방문한 경우
        // 출발도시로 가는 경로가 존재해야 돌아갈 수 있음 (존재하지 않으면 이 방법은 불가능)
        if(W[cur][0] == 0) return INF;
        return W[cur][0];
    }

    // 현재노드에서 탐색한 내역이 있다면, 중복탐색 방지
    if(dp[cur][visited] != -1) {
        return dp[cur][visited];
    }
    
    dp[cur][visited] = INF;
    for(int i=0; i<N; i++) {
        // 현재 노드에서 아직 방문하지 않는 i번 도시 가는 경로가 있는 경우
        if((visited & (1<<i))==0 && W[cur][i]!=0) {
            // 방문해야하는 도시로 가는 최소 비용
            dp[cur][visited] = Math.min(dfs(i, visited | (1 << i)) + W[cur][i], dp[cur][visited]);
        }
    }
    return dp[cur][visited];
}

 

 

dp[cur][visited] = INF;
for(int i=0; i<N; i++) {
    // 현재 노드에서 아직 방문하지 않는 i번 도시 가는 경로가 있는 경우
    if((visited & (1<<i))==0 && W[cur][i]!=0) {
        // 방문해야하는 도시로 가는 최소 비용
        dp[cur][visited] = Math.min(dfs(i, visited | (1 << i)) + W[cur][i], dp[cur][visited]);
    }
}

 

이 부분을 보면 dfs 실행시마다 현재 노드에서 아직 방문하지 않은 도시가 있는지(visited & (1<<i))==0)와 그 도시로 가는 경로가 있는지(W[cur][i]!=0)를 검사한 후, 있다면 모든 도시들에 대해서 최소 비용을 갱신한다. 이 때 dfs함수를 비용을 반환하도록 만들어서 모든 도시를 재귀탐색한 비용을 받도록 한다.