외판원 순회 알고리즘 TSP (Traveling Salesperson Problem)

외판원 순회 문제

NP-Hard 문제로 유명한 문제이다.

문제를 살펴보면

여러 도시들이 주어져 있고, 모든 도시들에 대한 가중치가 주어졌을 때, 

단일 시작점 부터 시작하여 모든 도시를 단 1번씩 만 방문하여 다시 시작점으로 돌아오는 데 최단 거리를 구하는 문제이다.

알고스팟에서 TSP 문제의 N을 점점 크게 하여 TSP 문제를 3개나 출제해놓았다.

https://algospot.com/judge/problem/read/TSP1

https://algospot.com/judge/problem/read/TSP2

https://algospot.com/judge/problem/read/TSP3

하지만 알고스팟에 나와있는 문제는 다시 시작점으로 돌아오는 제약 조건을 없지만 계산 복잡도는 변하지 않는다.

그래서 우선 TSP1 문제를 완전 탐색으로 수행해볼 것이다.

모든 정점에 대해 시작해보고 n개의 모든 정점을 방문하면 거리를 반환하는 방식이다. 이 문제에서 N <= 8 로 주어진다.

double shortestPath(int pos, int size, double length) {
    if(size >= n) {
        return length;
    }
    double ret = 987654321;
    for(int i=0;i<n;i++) {
        if(!visited[i]) {
            visited[i] = true;
            ret = min(ret , shortestPath(i, size + 1, length + dist[pos][i]));
            visited[i] = false;
        }
    }
    
    return ret;
}

이 함수를 모든 정점에 대해 수행하고 가장 작은 결과값을 반환하면 TSP1 문제를 풀 수 있다. 한번 함수를 호출할 때마다 O(n!)

TSP2 문제에서도 이 코드를 사용할 수 있을까? TSP2 는 N <= 15 로 커진 문제이다.

방금 제출했는데 당연히 시간 초과가 떴다. 이걸 어떻게 해결할 수 있을까? 답은 비트마스크 + DP 를 적용하면 된다.

*비트 연산은 산술 연산보다 빠르기에 사용한다!*

사실 나도 이 포스팅 하면서 비트마스크 + DP 를 적용해서 외판원 순회 문제는 처음 풀어보는 것이다ㅋㅋ

비트마스크를 사용한다면 visited 배열은 필요가 없다. 

대신 visit를 체크할 수 있는 다른 방법이 있다. 그건 바로 그냥 int형 변수를 visited 배열처럼 사용하는 것이다.

어떻게 visited 배열처럼 사용할 수 있을까? 그것은 바로 비트를 사용하는 것이다.

int는 4byte 정수형으로 32비트를 가진다. 그럼 15, 20인 N에 대해서도 int 형 변수 1개면 visited 배열을 커버할 수 있다.

산술 연산이 비트 연산보다 빠르고 + visited 배열을 모든 정점에 대해 초기화 할 필요가 없어 지기 때문에 계산 복잡도가 훨씬 줄어들 수 있다.

double dist[MAXNUM][MAXNUM];
double dp[MAXNUM][1 << MAXNUM];
double shortestPath(int pos, int visited) {
    if(visited == (1 << n) - 1)
        return 0;
    
    double &ret = dp[pos][visited];
    if(ret != -1) return ret;
    
    ret = 98765321;
    for(int i=0;i<n;i++) {
        if(visited & (1 << i))
            continue;
        ret = min(ret, shortestPath(i, (visited | (1 << i))) + dist[pos][i]);
    }
    
    return ret;
}

이러면 답이 나온다! 참고하자! 한번 할 때마다 O(2^n * n^2 ) 의 시간복잡도를 가짐

이 코드로 하면 정답이 나온당