TSP (Traveling Salesman Problem): 외판원 순회

Traveling Salesman Problem, TSP, 외판원 순회, 외판원 문제

정의

N 개 도시를 정확히 한 번씩 방문 후 시작점으로 돌아오는 최소 비용 경로. NP-hard.

Bitmask DP (N ≤ 20)

상태: dp[mask][i] = “방문 집합 = mask, 현재 도시 i” 상태의 최소 비용.

int dp[1<<20][20];  // INF 초기화

dp[1][0] = 0;   // 도시 0 에서 출발
for (int mask = 1; mask < (1<<n); mask++) {
    for (int i = 0; i < n; i++) {
        if (!(mask & (1<<i)) || dp[mask][i] == INF) continue;
        for (int j = 0; j < n; j++) {
            if (mask & (1<<j)) continue;
            int nm = mask | (1<<j);
            dp[nm][j] = min(dp[nm][j], dp[mask][i] + cost[i][j]);
        }
    }
}

int ans = INF;
int all = (1<<n) - 1;
for (int i = 1; i < n; i++)
    ans = min(ans, dp[all][i] + cost[i][0]);

시간 O(2^N · N²), 공간 O(2^N · N).

근사

• MST + DFS: 2-approximation
• Christofides: 1.5-approximation (metric TSP)
• LKH (Lin-Kernighan): 휴리스틱, 실전 최강

참고

• Hamiltonian Path
• DP Bitfield
• MST