TSP

TSP(Travelling Salesman Problem) : 여행하는 외판원 문제

- 개념 : 도시의 개수와 각 도시간 연결되있는 거리들이 주어질 때, 

모든 도시를 한 번씩 방문하고 원래 도시로 돌아올 수 있는 최단 거리 경로를 구하는 문제

-풀이

 1. 완전탐색 : 각 도시를 잇는 모든 경로를 다 확인해보는 방법.

 재귀 혹은 순열을 이용해서 푸는 방법인데 현실적으로 이 방법을 사용하지 않는다.

 도시의 수가 N일때 시간복잡도가 O(N!)으로 엄청난 시간을 필요로 하기 때문이다.

 2. dp : memoization으로 풀 수 있다.

점화식

dp[i][j] = i번째 도시까지 j상태의 도시를 지나쳐 왔을 때의 최소 비용

 (j상태는 몇번 몇번 도시를 방문했었는지 즉, 각 도시의 방문 여부 상태)

+) dp를 사용할 때 모든 도시 각각부터 시작할 필요가 없다.

   시작 도시 위치는 중요하지 않다. 왜? 정답 경로는 사이클이기 때문이다.

   정답 경로를 한번 만들면 어차피 모든 점을 다 돌아보기 때문에 어디서 시작하든 정답 경로를 반드시 지나친다.

   

    ex) N = 5, 최단거리경로가 1→2→3→4→5→1 일때 2→3→4→5→1→2 

 3→4→5→1→2→3   ... 도 모두 같은 비용

TSP문제

백준 2098번 외판원 순회

문제)https://www.acmicpc.net/problem/2098

풀이)

dp와 dfs를 이용해서 최소비용을 구하는 문제이다.

경로 확인시 방문처리는 비트마스크를 이용했다.

ex) N = 4 이면 0~3번 도시들이 있다고 하자. 맨 뒤에서부터 각각의 비트는 0번 부터 각각의 도시를 가리킨다.

    1111(2) = 모든 도시 방문 = (1 << N) - 1

    0001(2) = 0번 도시 방문

    0101(2) = 2번 도시, 0번 도시 방문

    ...

코드)

#include <stdio.h>
#include <algorithm>
using namespace std;
 
#define INF 20000000
int N;
int adj[16][16];
int dp[16][1<<16]; //dp[i][j] = 현재 i정점까지, j개상태 정점을 지나쳐왔을때 든 최소 비용
int all_visited;
 
int dfs(int end, int visit) { // end = 현재 마지막으로 방문한 도시 end, visit = end까지 왔을 때 현재 도시들의 방문 상태
    
    if (visit == all_visited) {//모두 방문했을 경우
        if (adj[end][0] == 0) return INF;//마지막 도시에서 0번 도시로 향하는 길이 없다면 INF 반환
        else return adj[end][0];
    }
 
    if (dp[end][visit] != -1) return dp[end][visit];//이미 이전에 계산한 값이 있으면 또 다시 계산 x(중복처리)
    
    int temp = INF;
    for (int i = 0; i < N; i++) {
        if ((visit & (1 << i)) == 0 && adj[end][i] != 0) {
            temp = min(temp, adj[end][i] + dfs(i, visit | (1 << i)));
        } 
    }
    dp[end][visit] = temp;
 
    return dp[end][visit];
 
}
int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < (1 << 16); j++) {
            dp[i][j] = -1;
        }
        for (int j = 0; j < N; j++) {
            scanf("%d", &adj[i][j]);
        }
    }
    all_visited = (1 << N) - 1; //모든 정점들을 다 방문했을 경우의 상태값
 
    //몇번 도시부터 시작하는지 상관없으니깐 0번 도시부터 시작한다.
    printf("%d", dfs(0,(1<<0)));
 
    return 0;
}