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

외판원 순회란?

도시들이 존재하며 도시로 이동할 때 드는 비용이 주어졌을 때 불특정 한 도시에서 출발하여 모든 도시를 돌고 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제입니다.

 

외판원이 가장 적은 비용으로 모든 도시를 방문하면서 자기 집으로 돌아온다고 하여 외판원 순회라는 이름이 붙었습니다.

https://shoark7.github.io/programming/algorithm/introduction-to-tsp-and-solve-with-exhasutive-search

 

 

이 문제의 특징은 비트 연산, DFS, DP를 모두 활용해서 해결해야 합니다.

만약 해당 개념을 활용하지 않고 가장 일반적으로 떠오르는 '각 도시를 잇는 모든 경로를 탐색하고 그중 최솟값을 찾자'라는 완전 탐색으로 푸는 방법도 있지만 이는 O(N!)의 시간 복잡도로 인해 시간 초과가 발생할 수 있습니다.

 

만약 0번째 도시에서 출발하고 남은 도시들을 어떤 순서로 방문할지만 정하면 되기 때문에 남은 n-1개의 도시를 나열하는 방법으로는 (n-1)! 가지가 있습니다.

 

완전 탐색방법

def tsp(D):
    N = len(D)
    inf = float('inf')
    ans = inf
    VISITED_ALL = (1 << N) - 1

    def find_path(start, last, visited, tmp_dist):
        nonlocal ans
        if visited == VISITED_ALL:
	    return_home_dist = D[last][start] or inf
            ans = min(ans, tmp_dist + return_home_dist)
            return

        for city in range(N):
            if visited & (1 << city) == 0 and D[last][city] != 0:
                find_path(start, city, visited | (1 << city), tmp_dist + D[last][city])

    for c in range(N):
        find_path(c, c, 1 << c, 0)

    return ans

비트 마스킹을 활용하여 방문을 기록합니다.

비트 마스킹이 이해가 되지 않는다면? 해당 부분을 boolean visited [N]으로 생각하셔도 됩니다.

 

밑에서도 설명하겠지만 비트 마스킹에 대해 설명해보겠습니다.

VISITED_ALL = ( 1  << N) -1이라고 합니다.

 

왜 이렇게 표기할까요?

우선 비트 마스킹이란 비트(1,0)를 활용하여 마킹을 하는 의미인데 여기서는 1은 방문됨을 의미하고 0은 방문되지 않음을 의미합니다.

1 << N의 경우는 비트 1을 왼쪽으로 SHIFT(=왼쪽으로 N칸 이동) 시킵니다.

만약 N = 4라면 1<<4 = 10000(2)가 됩니다.  만약 여기에 1을 빼면 어떻게 될까요? 1111(2)이 됩니다.

즉, 1은 방문됨을 의미하기 때문에 0번째 도시, 1번째 도시, 2번째 도시, 3번째 도시가 모두 방문됨을 의미합니다.

 

여기까지 왔다면 VISITED_ALL에 대해서는 납득하셨을 겁니다.

 

하지만 visited & ( 1 << city) ==0 조건에 대해서는 왜 이렇게 하는지 이해가 안 될 수 있습니다.

일단 의미론적으로는 '현재 city가 방문되었니?'입니다.

 

우선 비트의 & 연산에 대해 알아야 합니다.

10000 & 10000 = 10000입니다.

01010 & 10101 = 00000입니다.

11111 & 11110 = 11110입니다.

11111 & 00000 = 00000입니다.

 

만약 비트의 자릿수가 모두 1이면 1 그렇지 않으면 0입니다.

따라서 비트의 & 연산을 활용하여 방문 체크를 할 수 있습니다.

visited는 0001(2)라고 생각해 보겠습니다. 이는 현재 0번째 도시만 방문했구나를 의미합니다.

그리고 지금 0번째 도시를 다시 방문한다면 1 <<0 은 0001(2)입니다.

0001(2) & 0001(2)를 하면 1이 나오게 되고 이는 0이 아니기 때문에 방문할 수 없습니다.

 

만약에 visited가 1000(2)라고 생각해 보겠습니다. 이는 현재 3번째 도시만 방문했구나를 의미합니다.

그리고 지금 2번째 도시를 방문하려고 하면 (1 << 2)는 100(2)입니다.

1000(2) & 0100(2) = 0입니다. 따라서 방문할 수 있습니다.

 

또한 이 문제의 포인트는 순회 경로(사이클)를 만들 수 있다면 시작점은 중요하지 않다는 것입니다.

https://loosie.tistory.com/272

 

1번에서 출발하던 2번에서 출발하던 3번에서 출발하던 사이클이 같다면 결국 최적의 경로는 똑같이 할 수 있습니다.

 

 

1. 비트 연산의 활용

방문 체크를 확인하기 위해 사용하면 좋습니다.

즉, n번째 비트의 on/off 여부로 n번째 도시를 방문했는지의 여부를 표현합니다.

도시의 수 N이 4일 때, 현재 방문 비트가 1001(2)라고 하면 어떤 의미일까요?

이것은 0번 도시 3번 도시는 방문하였기 때문에 1(비트의 on), 1번 도시, 2번 도시는 방문하지 않았다면 0(비트의 off)을 표현합니다.

 

2. DFS를 활용하여 가장 적은 비용의 순회 여행 경로를 탐색하고 중복되는 경로를 줄이기 위해 DP를 활용합니다.

DP를 활용하면 이전에 계산했던 최소 비용의 순회 경로를 다시 계산하기 않게 되어 시간 복잡도를 줄일 수 있습니다.

DP를 활용하기 위해서 cache [][] 또는 DP [][] 리스트를 통해 표현합니다. 

index에는 탐색한 경로가 저장되고 value에는 탐색한 경로의 최단 거리를 저장하게 됩니다.

 

DP [N][visited]는
N번 도시가 visited < 어떤 도시들을 방문했는지를 의미합니다.

예를 들어 DP [3][11] = 15라면?

3번째 도시 기준으로 11을 2진수로 표현하면 1011(2)이므로 2번 도시만 방문하지 않았고 나머지 도시를 전부 방문했음을 의미합니다.

즉, 3번 도시 -> 2번 도시 -> 0번 도시의 최단 경로가 15라는 의미입니다.

 

3. DFS를 통해 DP값을 어떻게 기록해야 할까요?

https://maivve.tistory.com/306

 

여기서 보면, 5번 도시까지 가는 경로는 다음과 같습니다.

1 -> 2 -> 3 -> 5

1 -> 3 -> 2 -> 5

 

이때 남은 도시들을 방문하고 1번으로 돌아가는 비용은 5 -> 4 -> 1 한 가지 경우밖에 없습니다.

 

모든 경로에 대해 계산할 때, 저렇게 남은 경로의 비용을 일일이 구하지 않고 미리 구해놓은 값을 사용합니다.

 

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

// 외판원 순회
// 다이나믹 프로그래밍
public class Main_2089_외판원순회DP {
	static int n;
	static int[][] map;
	static int[][] dp;
	static final int INF = 16_000_001;
	//Integer.MAX_VALUE를 쓰지 않은 이유는 이후에  return을 하면서 값을 더해서 비교하는 부분이 있을때
	//overFlow가 발생하는 경우가 있었음.

	public static void main(String args[]) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		// i : 현재 위치한 도시, j : 지금까지 방문한 도시 2진수
		dp = new int[n][(1 << n)]; // ex) 1 << 5 = 100000(2) = 32 -> 우리의 최대값 : 11111(2) 이므로 1 빼기

		// 1) Map 입력받아 대입하기
		StringTokenizer st;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				int weight = Integer.parseInt(st.nextToken());
				map[i][j] = weight;
			}
		}

		// dp배열 초기화
		for (int i = 0; i < n; i++) {
			Arrays.fill(dp[i], INF);
		}

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

	// 어느 도시에서 시작하든지 최소비용은 같기 때문에 편안하게 0번도시부터 시작하자
	// @param: city - 현재 위치한 도시 인덱스, visitBitMask - 지금까지 방문한 도시 2진수
	// DFS 알고리즘
	private static int dfs(int city, int visitBitmask) {

		if (visitBitmask == (1 << n) - 1) { // 모든 도시를 방문했다면

			// 현재 경로에서 0으로 도달할 수 없다면
			if (map[city][0] == 0) {
				return INF;
			}

			return map[city][0]; // 현재 도시 -> 0번쨰(시작) 도시 이동 거리
		}

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

		// 현재 도시(city)에서 각 i의 도시로 이동한 경우에 대해 DFS 수행
		for (int i = 0; i < n; i++) {
			// 한 번이라도 그 도시를 방문했는데 다시 그 도시를 방문하는 경우 예외처리
			if ((visitBitmask & (1 << i)) > 0 || map[city][i] == 0) {
				continue;
			}

			// d[i][j] = 현재 있는 도시가 i이고 이미 방문한 도시들의 집합이 j일때, 방문하지 않은 나머지 도시들을 모두 방문한 뒤 출발 도시로
			// 돌아올 때 드는 최소 비용.
			// 즉, 방문해야하는 도시(여기에 시작지점으로 돌아오는 것 포함) 들까지 가는 최소 비용
			dp[city][visitBitmask] = Math.min(dp[city][visitBitmask], dfs(i, visitBitmask | (1 << i)) + map[city][i]);
			// dfs(다음 도시, 다음도시 방문했다고 가정) + 여기서 다음 도시까지의 거리 와 최소거리 비교
		}

		return dp[city][visitBitmask];
	}
}

 

 

출처

https://maivve.tistory.com/306

(JAVA) 백준 2098번 : 외판원 순회 --- [DP, TSP, 비트마스크]

https://withhamit.tistory.com/246

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

https://red-pulse.tistory.com/29

[알고리즘 정리] 외판원 순회 문제(Traveling Salesperson Problem, TSP)