외판원 순회(Traveling Salesman Problem)

TSP

어떤 한 도시에서 출발해 모든 도시들을 거친 후
출발했던 도시로 돌아올 수 있는 최소 비용이 요구되는 방법

이러한 도로가 존재한다고 가정해보자.

어떤 순서로 순회해야 최소 비용으로 모든 도시를 방문하고 돌아올 수 있을까?
완전 탐색으로 그 해를 구하는 방법이 가장 간단하다.

단순히 DFS를 통해 해를 구할 수 있다.
이 때, 모든 정점을 시작점으로 DFS를 구할 필요는 없다.
무작위로 하나의 시작점에서 DFS를 진행한다.

여기서 의문점이 생길 수 있다.

0 - 1 - 2 - 3 경로와 2 - 3 - 0 - 1 경로는 서로 다른 경로인데요?
하나의 시작점에서만 DFS를 진행하면 이러한 경우는 고려하지 않게 되는데?

둘의 경로를 구성하는 순서가 일치하는 것은 아니다.
하지만 두 경로를 이동하는데 요구되는 비용도 다를까?

최소 비용이 요구되는 유일한 경로가 있고,
그 경로가 위와 같다고 가정하자.

이 경로의 시작점에 따라 비용이 달라질까?
어디서 시작하든, 요구되는 비용은 15이다.

해당 그림의 정점들을 모두 잇는 간선을 무작위 시작점에서 그려보자.
시작점은 비용에 영향을 미치지 않는다.

위의 경우에는 0 - 1 - 2 - 3과 1 - 0 - 2 - 3을 같은 경로라고 볼 수 있지만,
이는 두 도시를 잇는 간선이 양방향이기 때문이다.

간선이 단방향이면 0에서 1, 1에서 0 도시로 가는 비용이 다를 수 있기 때문에 두 경로를 다르게 봐야 하지만,
그래도 DFS를 한 정점에서만 실행하면 된다는 것은 동일하다.

따라서 이러한 방법으로 해를 구하면
첫번째 예시를 기준으로 대략 $(n-1)!$

$O(n!)$일 경우, $n$이 조금만 큰 값으로 설정되어도 어마어마한 시간이 소요된다.
외판원 순회와 같은 문제는 $n$이 최대 16이기 때문에
이러한 방법으로 풀어낼 수 없다.

최적화

$O(n^22^n)$

앞서 사용한 방법은 연산의 중복이 존재한다.
이미 계산해서 구한 값을 또 다시 계산해서 구하고 있다.

예시를 살짝 변경하였다.

어느 구간을 중복해서 계산하고 있는지 확인해보자.

아래는 도시 0에서 DFS를 실행해서 탐색한 결과 중 일부이다.

0 - 1 - 3 - 2 - 4 - 0
0 - 3 - 1 - 2 - 4 - 0

이 경로들은 2 - 4 - 0 이라는 중복된 경로를 갖고 있다.

2 - 4 - 0 경로를 이동하는 데 요구되는 비용은 14이다.
부분 경로에 대한 비용을 한 번 계산하고 어딘가에 따로 저장하면,
그 부분 경로를 굳이 탐색하지 않아도 쉽게 비용을 계산할 수 있게 된다.
DP를 이용하면 해결이 가능하다.

중복된 경로가 2 - 4 - 0이 아니라
2 - 3 - 4 - 5 - ... - 16이라고 생각하면
중복 계산 해결은 필수적이다.

그렇다면,

2 - 4 - 0 경로를 탐색하려면, 비용 14가 요구된다.
1 - 3 - 5 - 7 - 9 경로를 탐색하려면, 비용 X가 요구된다.

이러한 값을 어떻게 효율적으로 기록할 수 있을까?
비트마스크를 이용하면 해결이 가능하다.

도시가 0부터 4까지 5개가 있다고 하고,
2 - 4 - 0경로를 방문했다고 하면 이를 $10101_{(2)}$

방문한 경로의 자릿수를 1로 바꿔주는 것이다.
(0, 2, 4 자릿수를 1로 변경)

그러면 10101은 10진수로 21이고
14의 비용이 요구되므로 
dp[21] = 14 라고 저장하면 될까?

dp[$10101_{2}$

dp[방문 기록] = 비용이 아니라
dp[현재 정점][방문 기록] = 비용과 같은 형태로 저장해야 한다.

1차원 배열의 dp를 사용한다고 해보자.

정점 1에서 시작하고, 1 - 2 - 3 - 1 경로를 탐색해보면 비용은 9이고,
dp[$011_2$

그 다음으로 1 - 3 - 2 - 1 경로를 탐색할 때,

2 - 3 - 1 경로의 비용이 사용되어 버린다.

2와 3은 단방향 간선 2개로 이루어져 있기 때문에

1 - 2 - 3과 1 - 3 - 2의 비용은 다르다.

단방향 간선을 전혀 고려하지 않은 메모이제이션이다.

dp[현재 정점][방문 기록] = 비용을 보면

구하려는 정답은 dp[시작점으로 돌아가기 직전의 정점][모든 정점에 방문했다는 기록]

이라고 생각할 수도 있는데,

정답은 dp[시작점][시작점에 방문했다는 기록]에 있다.

0번째 정점에서 시작하고 정점이 총 4개라면 정답은 dp[0][1]에 있는 것이지,

dp[3][15]에 있는 것이 아니다.

단순히 방문했다는 기록이 아니라,

dp 배열을

이만큼 방문했는데, 방문하지 않은 다른 정점들에 가려면 비용이 얼마나 필요해?

라는 의미를 갖고 있는 배열이라 생각하면 하단에 등장할 코드를 이해하기 수월할 것이다.

풀이 과정 및 코드

과정은 다음과 같다.

1. 한 시작점에서 dfs를 실행한다.
2. 다른 탐색 정점을 방문하지 않았고, 해당 정점으로 가는 길이 있으면 이동한다.
3. 정점을 다 방문했으면, 그 시점의 정점에서 시작 정점으로 돌아갈 수 있는지 확인한다.

편의상 0번째 정점에서 시작하도록 하고,

실행하려는 함수를 tsp(현재 정점, 방문 기록)이라고 하자.

tsp(0, 1)이 수행된다.

정점이 4개면 모든 정점을 방문했을 때의 방문 기록은 $1111_2$

(1 << 4) - 1 와 같이 비트 연산자를 이용해 나타낼 수 있다.

해당 정점의 방문 여부를 확인하기 위해서는

방문 기록 & (1 << i)의 값이 0인지를 체크하고,
방문하지 않았으면 방문 기록 | (1 << i)와 같이 작성한다.

tsp 함수 코드는 다음과 같다.

static int tsp(int currentVertex, int visited) {
		if(visited == (1 << n) - 1) {
			if(w[currentVertex][0] != 0)
				return w[currentVertex][0];
			
			return MAX;
			
		}
		
		if(dp[currentVertex][visited] != MAX)
			return dp[currentVertex][visited];
		
		for (int i = 0; i < n; i++) {
			if(w[currentVertex][i] != 0 && ((visited & (1 << i)) == 0)) {
				dp[currentVertex][visited] = Math.min(dp[currentVertex][visited], tsp(i, visited | (1 << i)) + w[currentVertex][i]);
			}
		}
		
		return dp[currentVertex][visited];
	}

여기서

if(dp[currentVertex][visited] != MAX)
			return dp[currentVertex][visited];

처럼 나타내기 위해서는 main 함수에서

for (int i = 0; i < n; i++)
			Arrays.fill(dp[i], MAX);

와 같이 dp의 값을 큰 값으로 초기화해 주어야 한다.

아니면 굳이 처음에 main 함수에서 큰 값으로 초기화해 주지 않고

if(dp[currentVertex][visited] != 0)
			return dp[currentVertex][visited];
		
 dp[currentVertex][visited] = MAX;

처럼 나타내도 된다.

참고로 MAX = Integer.MAX_VALUE와 같이 값을 초기화하는 실수를 만들지 않아야 한다.

dfs를 수행하는 과정에서 오버플로우가 발생할 위험이 있다.

적당히 큰 값으로 대체하자.

전체 코드

import java.util.*;
import java.io.*;

public class Main {
	static int n;
	static int[][] w;
	static int[][] dp;
	static final int MAX = 12345678;
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		
		w = new int[n][n];
		dp = new int[n][1 << n];
		
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < n; j++) {
				w[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		System.out.println(tsp(0, 1));
	}
	
	static int tsp(int currentVertex, int visited) {
		if(visited == (1 << n) - 1) {
			if(w[currentVertex][0] != 0)
				return dp[currentVertex][visited] = w[currentVertex][0];
			
			return MAX;
			
		}
		
		if(dp[currentVertex][visited] != 0)
			return dp[currentVertex][visited];
		
		dp[currentVertex][visited] = MAX;
		
		for (int i = 0; i < n; i++) {
			if(w[currentVertex][i] != 0 && ((visited & (1 << i)) == 0)) {
				dp[currentVertex][visited] = Math.min(dp[currentVertex][visited], tsp(i, visited | (1 << i)) + w[currentVertex][i]);
			}
		}
		
		return dp[currentVertex][visited];
	}
}

visited의 경우의 수가 $2^n$, 정점의 개수가 $n$개이고
tsp 함수가 $n$번의 루프를 돌고 있으므로

$O(n^22^n)$