DP - TSP(Traveling Salesman Problem) 최소 여행 경비 c++ [컴공과고씨]

TSP

한 정점에서 출발하여 다른 정점을 각각 한번씩만 방문하고 다시 처음 정점으로 돌아오는 가장 짧은 경로를 결정하는 것.

*음이 아닌 가중치가 있는, 방향성 그래프를 대상으로 함.

 

여행을 다 한 후 정점 1로 돌아오는 것으로 가정했을 때

아이디어는 dp[i][A]를 i에서 A에 속한 각 정점을 한번씩 거쳐서 정점 1로 가는 최단 경로의 길이라고 정의하는 것이다.

 자 그럼 dp[1][A-{1}] = min(w[1][j] + dp[j][v-{1,j}) j는 2부터 나머지 정점 , w[i][j]는 i부터 j까지 거리. 

무슨 말이냐면  정점 1에서 1를 제외하고 나머지 정점을 돌고 1로 돌아오는 것은?

1에서 다음 정점으로 이동한 가중치 + 다음 이동한 정점에서 출발하여 정점 1과 자신을 제외한 정점을 여행한 후 1로 돌아가는 정점이다. 이때 다음 정점이 여러개이기 때문에 모든 다음 정점에 대해서 구한 후 최소값을 구하는 것이다.

그렇다면 이것을 반복하여 다음 정점에 다음 정점 다음 정점 쭉쭉 들어가서 더 작은 문제로 분해가 가능하게 된다.

 

이때 이미 방문한 정점은 방문 처리를 해 중복으로 방문하는 것을 막아야하는데 이때는 bit mask를 이용하여 막아준다. 

비트 마스크 연산을 모른다면 https://hagisilecoding.tistory.com/54 여기서 간단히 보고 오시면 된다.

0000 0000 이런식의 비트가 있고 2번 정점을 방문했다면 0000 0100 이런식으로 표시를 하는 방법이다.

 

코드로 풀어보면 

#define MAX 17
#define INF 98765432
int dp[MAXN][1<<MAX]; // 부분집합의 개수2^MAX(1<<MAX)
int w[MAX][MAX];
 
int TSP(int st, int visit){
    int &ret = dp[st][visit];
    if(ret != -1) return ret; // 방문 했으면 값 그대로 리턴
    
    ret = INF;
    if(visit == (1 << N) - 1) // 모든 마을 방문 하면 ( (1<<5)-1= 1 0000 - 1 => 0 1111)  
        return ret = w[st][0]; //0번 마을로 돌아옴
    
    for(int j = 1; j < N; j++){
        if(!(visit & (1 << j))){ // 다음 정점이 방문을 안한 곳이면
            int nvisit = (visit | (1<<j)); // 다음 방문할 장소 표시
            ret = MIN(ret, TSP(j, nvisit) + w[st][j]);
        }
    }
    return ret;
}
 
int main(){
    memset(dp, -1, sizeof(dp));
    cout << TSP(0,1) << " "; // 0번에서 시작, 0번 방문 상태 체크 
    return 0;
}

 

 

시간 복잡도 

코드를 보면 TSP 함수를 보면 각 함수는 dp의크기인 n*2^n번 호출이 된다. 

여기서 각 마을을 돌았는지 확인해야해서 n-1번 돌아야하니 

시간 복잡도는 O(n*n*2^n)이다.

 

이게 이 문제를 풀 때 가장 빠른 알고리즘이지만 n =40 정도만 되어도 6년 이상 걸린다고 한다.