[Algorithm] 외판원 순회 문제(Traveling Salesman Problem)

외판원 순회 문제(TSP)

외판원 순회 문제(TSP)는 조합 최적화 문제 일종으로, NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다. 즉, 아직까지 다항 시간에 해결할 수 있는 해결책을 못찾았으며 해결하지 못한다는 것도 증명하지 못했다.

 

외판원 문제의 내용은 다음과 같다.

예를 들어, 어떤 외판원이 n개의 도시를 방문할 계획을 갖고 있다고 하자.

각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위해 외판원이 출발하는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 경로를 찾고자 할 때, 어떻게 찾을 수 있을까?

 

만약 20개의 도시가 있을 때 정답을 찾기 위해 다녀야 하는 총 경로 수는 20! = 2,432,902,008,176,640,000이다

 

 

풀이

다음 코드는 [baekjoon] 2098: 외판원 순회을 기준으로 작성하였다.

 

동적 계획법(DP) 풀이

DP를 이용하면 지수 시간에 풀 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class TSP {

    private static int n;
    private static int[][] map;
    private static int[][] dp;
    private static final int INF = 11_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        dp = new int[n][(1 << n) - 1];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }

        System.out.println(search(0, 1));
    }

    /**
     *
     * @param city: 현재 위치한 도시 인덱스
     * @param visitBitMask: 지금까지 방문한 도시 이진수
     * @return
     */
    public static int search(int city, int visitBitMask) {
        // 모든 도시를 방문했다면
        if (visitBitMask == (1 << n) - 1) {
            if (map[city][0] > 0) {
                return map[city][0]; // 현재 도시 -> 0번째(시작) 도시 이동 거리
            }
            return INF;
        }

        if (dp[city][visitBitMask] != -1) { // dp 값이 존재하는 경우
            return dp[city][visitBitMask];
        }

        dp[city][visitBitMask] = INF;
        for (int i = 0; i < n; i++) { // 현재 도시(city)에서 각 i의 도시로 이동한 경우에 대해 dfs 수행
            if (i == city) {
                continue;
            }

            if ((visitBitMask & (1 << i)) == 0 && map[city][i] > 0) { // 방문하지 않았던 도시
                // 다음 도시까지 거리와 최소거리 비교
                dp[city][visitBitMask] = Math.min(dp[city][visitBitMask], search(i, visitBitMask | (1 << i)) + map[city][i]);
            }
        }
        return dp[city][visitBitMask];
    }
}