Traveling Salesman Problem

Traveling Salesman Problem

외판원 문제(Traveling Salesman Problem)는 조합 최적화 문제의 일종으로 정의는 다음과 같다.

여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구해라.

우선 이 문제를 단순 브루트 포스로 해결하려면 방법은 간단하다. 도시가 $n$개 있다고 할 때, $n!$개의 방문 순서 순열을 미리 구해놓고 일일이 해당 경로들을 따라가며 최소 거리를 구하는 것이다. 이 방법은 시간 복잡도 $O((n-1)!)$로 도시의 수가 조금만 커져도 매우 비효율적인 알고리즘이 된다.

Dynamic Programming & Bitmask

DP(Dynamic Programming)를 활용하면 중복 연산을 제거하여 수행 시간을 줄일 수 있다.

만약 $n$개의 도시가 있을 때, 1번 도시부터 시작해서 현재 $i$개의 도시를 거쳐 현재 $k$번 도시에 있다고 하자. 이제 남은 $n-i$개의 도시를 모두 방문하고 다시 1번 도시로 돌아와야 한다. 이 시점에서 남은 $n-i$개의 도시를 방문하고 1로 돌아오는 방법은 여러가지가 있을 것이다. 이 중에서 최소값을 찾아 저장해둔다면, 현재까지 방문한 도시들을 거쳐 $k$에 도달하는 경로들 중 현재와는 다른 경로로 $k$에 오게 되었을 때, 남은 $n-i$개의 도시가 동일하므로 다시 계산할 필요 없이, 저장해둔 값을 그대로 사용할 수 있다.

따라서 우리는 dp를 활용할 때 2차원 배열로 현재 위치, 그리고 지금까지 방문한 도시 리스트에 대해서 왕복을 위해 남은 최소 거리를 저장하면 된다. 즉, dp[k][visited]의 형태이다.

이때 visited를 표현하기 위해 bitmask를 사용할 것이다. 0과 1로 방문 여부를 표시하여 만약 5개의 도시가 있다고 할 때, 01010은 오른쪽 부터 1번 도시로 하여 2번과 4번 도시를 방문한 것이라 할 수 있다. 이렇게 하면 도시가 $n$개라 할 때 visited를 bitmask로 표현하기 위해 0...000부터 1...111($2^n-1$)까지 $2^n$의 크기가 필요하다.

현재 위치에서 남아있는 도시들 중 $j$번 도시를 방문한다는 것을 표현하기 해서는 or 연산을 사용한다. visited|(1<<j)로 1을 $j$번 shift하여 or 연산을 해주면 된다. 코드로 구현 시에는 편의상 1번 도시가 아닌 0번 도시부터 시작한다고 설정하여 j-1이 아닌 j번 shift하여 or을 해주면 visited의 j번째 도시 bit가 1이 되어 방문처리 된다.

DP를 topdown으로 구현한다고 했을 때 앞서 설명한 점화 관계를 코드로 구현하면 아래와 같다.

for(int i=0; i<n; i++){
    if(!(visited&(1<<i)) && map[here][i]!=0){
        dp[here][visited]=min(map[here][i]+TSP(i, visited|(1<<i)), dp[here][visited]);
    }
}

아직 방문하지 않은 도시들에 대해서 다음으로 방문할 도시 i까지 가는데 드는 비용(map[here][i])에 다음 도시에서의 TSP(TSP(i, visited|(1<<i)))와 현재 dp에 저장되있는 값 중 최소를 저장하여 최소값을 구한다.

TSP의 최종 코드 구현은 다음과 같다.

int TSP(int here, int visited){
    if(visited==(1<<n)-1) return (map[here][0])?map[here][0]:inf;
    if(dp[here][visited]!=-1) return dp[here][visited];
    dp[here][visited]=inf;
    for(int i=0; i<n; i++){
        if(!(visited&(1<<i)) && map[here][i]!=0){
            dp[here][visited]=min(map[here][i]+TSP(i, visited|(1<<i)), dp[here][visited]);
        }
    }
    return dp[here][visited];
}

모든 도시를 방문한 경우(if(visited==(1<<n)-1)) 0번 도시로 돌아가야 하는데, 해당 도시로의 경로가 없는 경우는 불가능한 경로이므로 매우 큰 값을 return한다. 추가적으로 모든 도시를 방문하고 출발 도시로 돌아오는 순환 사이클이기 때문에 출발 도시를 0번으로 고정하고 문제를 풀어도 된다.

마지막으로 시간 복잡도를 따져보면 현재 위치인 here로 가능한 경우의 수가 $n$가지, visited 비트마스크로 가능한 경우의 수가 $2^n$가지 이고, 각 상태에 대해서 다음 도시로 가기 위해 for 문으로 $n$번 반복하므로 총 시간 복잡도는 $O(n^2 \times 2^n)$이 된다.