[Java] TSP(외판원 순회) 알고리즘

이 글에서는 TSP가 무엇인지 알아보고, TSP를 해결하 방법중 가장 널리 알려진 DP로 해결하는 방법을 학습합니다.

TSP 란

• Traveling Salesman Problem의 약자입니다.
• 외판원이 가장 효율적인 방문 판매 동선을 고민하듯, 모든 도시를 정확히 한 번씩 방문한 뒤 처음 위치로 돌아오는 최단 경로를 찾는 알고리즘입니다.

TSP 해결시 알아야 할 점

• 만약 모든 도시를 연결하는 사이클이 존재한다면, 사이클 상의 어느 지점에서 출발하더라도 모든 도시를 한 번씩 방문하고 출발지로 돌아올 수 있습니다.
• 이는 TSP가 특정한 출발 지점에 구애받지 않고 해결될 수 있음을 의미합니다. 따라서, 우리는 그래프 상의 임의의 한 정점에서 시작해 나머지 정점들을 모두 한 번씩 거치고 다시 원점으로 돌아오는 경로를 찾음으로써 TSP 문제를 해결할 수 있습니다.

TSP 해결: 브루트 포스

• 가장 직관적으로 떠오르는 방법은 N개의 도시(정점)로 가능한 모든 루트를 직접 계산하는 것입니다.

시간 복잡도

• N개의 정점이 존재하는 그래프에서 한 정점에서 시작해 나머지 N-1 개의 도시를 한 번씩 거쳐 처음 정점으로 돌아오는 경로를 브루트 포스로 계산하게 되면 최악의 경우 (N-1)! 만큼의 경로를 계산해 비교해야 합니다. $O(N!)$의 시간복잡도를 가지는 것이죠.
• 도시의 수가 13개만 되더라도 12! = 479,001,600 가지의 경로를 검토해야 합니다. 따라서 브루트 포스로 계산하는 방법은 도시의 수가 조금만 많아도 매우 비효율적이라고 할 수 있습니다.

TSP해결: Dynamic Programming (DP)

• DP란 어찌 보면 완전 탐색입니다. 다만, 이전에 계산했던 것을 기억함으로써 계산 횟수를 효과적으로 줄이는 방법인 것이죠.
• DP를 이용하면 $O(N!)$ 수준의 시간 복잡도를 $O(N^2・2^N)$ 정도로 낮출 수 있습니다.

DP의 필요성

• 5개의 도시 (0 ~ 4)에서 TSP를 해결하기 위해 0번 도시에서 시작해 1 ~ 3번 도시를 한 번씩 거친 후 0번 도시로 돌아오는 경우를 살피는 과정을 보겠습니다.

ⓐ 0 → 1 → 2 → 3 → 4 → 0
ⓑ 0 → 1 → 2 → 4 → 3 → 0
...
ⓒ 0 → 2 → 3 → 4 → 1 → 0
...
ⓓ 0 → 3 → 1 → 2 → 4 → 0
...

다음은 위 4가지 경로에서 계산이 중복되는 경우입니다.
1. ⓐ, ⓑ 경로에서 0 → 1 → 2 경로를 구하는 과정이 중복됩니다.
2. ⓐ, ⓒ 경로에서 2 → 3 → 4 경로를 구하는 과정이 중복됩니다.
3. ⓑ, ⓓ 경로에서 1 → 2 → 4 경로를 구하는 과정이 중복됩니다.

• 모든 경우도 아니고, 4가지 경우만 봤는데도 이렇게나 많은 중복이 발생함을 알 수 있습니다. $N$이 커질수록, 작고 큰 계산들이 훨씬 많이 중복됩니다. 이 중복된 과정만 메모이제이션으로 잘 기억해놓는다면 획기적으로 계산량을 줄일 수 있습니다.

점화식

TSP를 DP로 해결하기 위한 점화식은 다음과 같습니다.
(어떤 도시에서 시작해도 문제를 해결할 수 있으므로 문제를 단순화하기 위해 시작 도시를 0번 도시로 고정한 뒤 이를 기반으로 문제를 해결할 수 있도록 점화식을 설정합니다.)

• $A$: 도시의 집합
• $W$: 도시 가중치 그래프의 인접 행렬 즉, $W[u][v]$는 $u$번 도시에서 $v$번 도시로 가는 비용을 의미합니다.
• $D[i][A]$: 0번 도시에서 출발해 $A$에 속한 도시를 모두 한 번씩 거쳐 $i$번 도시로 가는 최소비용

초기값 설정

• 초기값: $D[i][∅] = W[i][0]$
• 점화식: $D[i][A] = min_{j \in A} (W[i][j] + D[j][A - \left \{ j \right \}])$

점화식 해석

• $D[i][∅] = W[i][0]$
  0번 도시에서 아무 도시도 거치지 않고 $i$번 도시로 가는 최소 비용은 직접적으로 0번 도시에서 $i$번 도시로 가는 가중치와 같습니다. 만약 두 도시가 연결되어 있지 이동이 불가하다면 이 비용은 ∞로 설정됩니다.

• $min_{j \in A} (W[i][j] + D[j][A - \left \{ j \right \}])$
  $A$에 속한 도시중 도시 하나를 선택한다. 이를 $j$번 도시라 하자. 0번 도시에서 시작해 $j$번 도시를 제외하고 $A$에 속한 도시를 한 번씩 방문해 $j$번 도시에 도달하는 최소비용을 구한다. 해당 비용에 $j$번 도시에서 $i$번 도시로 가는 비용을 구한다. 이 과정을 $A$에 속한 모든 도시에 대해 반복한 뒤 최소값을 구하는 식입니다.

시간 복잡도 계산

• 최악의 경우 $(N - 1)$ 개 도시의 모든 부분 집합을 고려해야 합니다. 이 때의 시간 복잡도는 $2^{N-1}$ 즉 $O(2^{N})$ 입니다.
• 각 부분집합에 대해 부분집합에 속한 모든 도시와, 속하지 않은 모든 도시의 조합으로 최소 거리를 구합니다. 이 경우 시간 복잡도는 $O(N^2)$ 입니다.
• 따라서 DP를 이용해 TSP를 해결하는 방법의 시간 복잡도는 $O(N^2・2^N)$이 됩니다.

TSP 구현 (with java)

전체 도시의 개수가 N개라면 $D[i][A]$는 다음과 같이 나타낼 수 있습니다.

int[][] D = new int[N][(int) Math.pow(2, n - 1)]

• 실제 코드로 이 내용을 구현할 때는 $D[i][A]$ 에서 $A$를 비트 마스크를 이용한 정수로 표현합니다. $A$의 오른쪽 $n$번째 bit가 1이라면 $n$번 도시를 나타내는 것이죠.
• 예를 들어 A가 6이라면 (이진수로 110) 이는 3번 도시와 2번 도시를 나타내고 위의 개념에 대입하면 $\left \{ 2, 3 \right \}$ 을 나타내게 됩니다.
• 첫 시작점을 제외한 나머지 $(n - 1)$ 개 도시를 나타내기 위해서는 $(n - 1)$개의 비트가 필요하고, 결론적으로 A는 0 부터 $2^{n - 1} -1$ 의 범위를 가지는 수가 됩니다.

D[i][A]를 구하는 함수는 다음과 같은 틀로 구현할 수 있습니다.

int getCost(int i, int A) {
	if (D[i][A] 값을 이미 구했다면) return D[i][A];

	D[i][A] 구해 값 저장하기
    
    return D[i][A];
}

백준에 부가적인 외판원 순회 알고리즘을 구현하는 문제가 있습니다. 해당 문제 풀이 코드를 통해 전체 TSP 알고리즘을 보여드리겠습니다.
링크: https://www.acmicpc.net/problem/2098

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

public class Main {
    static int N;
    static int Arange;  // 집합 A를 비트마스크로 표현했을 때 가질 수 있는 최대 값. 즉, 2^(N-1)
    static int[][] W;  // 인접 행렬
    static int[][] D;
    static final int INF = Integer.MAX_VALUE;  // infinite 를 대변 

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

        N = Integer.parseInt(br.readLine());
        W = new int[N][N];

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

        // tsp[i][A] 0번 도시에서 A에 속한 도시를 거친 후 i번 도시로 오는 최소 비용
        Arange = (int) Math.pow(2, N - 1);
        D = new int[N][Arange];

        // 구하지 않은 값은 모두 -1 로 초기화
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < Arange; ++j)
                D[i][j] = -1;

        // 초기값 설정
        D[0][0] = 0;
        for (int i = 1; i < N; ++i) {
            if (W[i][0] == 0) D[i][0] = Integer.MAX_VALUE;
            else D[i][0] = W[i][0];
        }

        System.out.println(tsp(0, Arange - 1));
    }

    public static int tsp(int i, int a) {
        
        // 이미 D[i][a] 값을 구했었다면, 해당 값을 반환
        if (D[i][a] != -1)
            return D[i][a];

        int minCost = INF;
        for (int j = 1; j < N; ++j) {
            // 1번 도시부터 (N-1)번 도시 중 a 에 속한 도시만 고려한다.
            if ((a & 1 << (j - 1)) == 0) continue;
            
            // prev = D[j][A - {j}]
            int prev = tsp(j, a & ~(1 << (j - 1)));
            
            // 갈 수 없는 루트인 경우 건너뛴다.
            if (prev == INF || W[i][j] == 0) continue;
            
            minCost = Math.min(minCost, W[i][j] + prev);
        }
        
        return D[i][a] = minCost;
    }
}

마무리

• 이번 포스팅에서는 TSP에 대해 알아보고, 특히 동적 계획법(DP)을 이용한 해결 방법에 초점을 맞춰 공부해 보았습니다. 사실, TSP와 같은 복잡한 최적화 문제는 직관적으로 접근하기 어렵고, 따로 공부하지 않는다면 해결 방법을 떠올리기 쉽지 않습니다.

• 하지만 한 번 시간을 들여 DP와 같은 알고리즘을 깊이 있게 이해하고, 실제 문제에 적용해 보면 이후 비슷한 유형의 문제를 훨씬 효과적으로 해결할 수 있는 기반을 마련할 수 있을 것입니다.