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

 

옥장판 파는 세일즈맨...?

🚶🏻‍♂Traveling Salesman Problem

외판원순회는 대표적인 CS 문제 중 하나이다.

다항 시간에 풀 수 없는 NP 문제로 유명하다. (NP는 다항시간에 풀 수 없으나 다항시간에 검산이 가능함.)

최소 비용을 가지는 원순열 을 찾는 문제이다.

결론부터 말하자면,

💡외판원 순회는 DP + DFS이다.

📌조건

1. 외판원은 모든 도시를 최소비용으로 한 번씩만 방문하여 처음 도시로 돌아와야 한다.
2. *이는 해밀턴 경로(Hamilton circuit) 라고 부르며, 한붓그리기와 같다.
3. 각각의 도시 간의 경로는 방향성이 있고, 비용이 존재하며 어떤 도시들 간에는 경로가 없을 수도 있다.
4. 항상 최적의 경로가 존재한다.

📌알 수 있는 사실

1. 최적의 경로는 어떤 정점에서 시작하든 사이클을 만들어 처음 정점으로 돌아오기 때문에 시작 정점과 상관없이 찾을 수 있다.
2. 1→2→3→4→5→1 이든, 2→3→4→5→1→2 든 같은 경로이고, 같은 결과값을 가진다. 사이클이기 때문에 어떤 정점에서 시작하든 상관이 없다.
3. 만약 모든 순열에 대해서 고려하게 된다면 팩토리얼의 시간복잡도가 발생한다. O(N!)노드의 갯수가 10개만 되어도 3628800 번 방문해야한다.
4. 팩토리얼 시간은 노드 수가 늘어나면 기하급수적으로 늘어나게 된다.

📌풀이

외판원 순회에서는 백트래킹과 dp를 혼합하여 문제를 푼다.

1. 먼저 각각의 노드를 방문 표시를 비트마스킹으로 한다.
2. 01001 → 노드갯수 N = 5이고, 1번과 4번 노드를 방문함.
3. 2차원 배열로 비용을 기록해둔다.
   dp[cur][visit] -> 현재 방문하는 노드 / 방문기록 에서의 최소비용
4. 시작노드
   시작 노드 → 알 수 있는 사실 1번으로 인해 아무 노드나 잡고 시작해도 된다.
   인덱스 0번부터 시작함을 가정한다. 0번 노드를 시작점으로 하여, dfs(0,1)을 수행한다. (00001 ⇒ 0번 노드만 방문함)
5. 현재 노드(depth 1)로부터, 다음 노드들(depth2)에 대해서 최단 경로를 탐색한다. (O(N))
6. dfs로 4번을 반복하여 탐색하고, 메모이제이션 된 값이 있는 경우 이를 사용한다.

📌DP를 사용하는 이유 (메모이제이션 이점)

순열에서 앞의 순서가 달라도, 뒤의 순서는 같은 경우들이 발생할 수 있다. 이러한 경우들에 메모이제이션 한 값들을 이용하여 시간을 단축한다. (같은 계산을 여러번 하는 것을 방지한다.)

예시1

  1→5→2→3→4→1 

  1→2→3→5→4→1 

1,2,3,5번 노드를 모두 방문했을 때, 나머지 노드를 방문하는 경로 중 최단 경로가 4->1 이라고 가정하자.
이 값은 배열에서 dp[4][11111] 과 같이 표현 할 수 있다. (현재 노드가 4이고, 모든 노드를 방문했다고 가정했을 때의 최소비용)

두 순열에서 마지막 4→1의 경로가 겹친다. 만약 4->1로 가는 최소비용이 메모이제이션 되어있다면, 탐색 시간을 감소시킬 수 있다.

첫번째 순열에서 1,2,3,5번 노드를 모두 방문했을 때, 나머지 노드를 방문하는 경로 중 최단 경로를 구했기 때문에, 두번째 순열에서는 현재 노드가 4일때 더 이상 탐색하지 않아도 된다.

예시 2

 1→2→5→3→4→1

 1→5→2→3→4→1 

확장된 예시를 보자.
1,2,5 노드를 모두 방문했을 때, 나머지 노드를 방문하는 경로 중 최단 경로가 3->4->1 이라고 가정하자.

두 순열에서 마지막 3→4→1의 경로가 겹친다.

첫번째 순열에서 현재 노드가 3이고 4번 노드를 제외한 모든 노드를 방문했다고 가정했을 때의 최소비용을 구했다. dp[3][10111]
두번째 순열에서는 현재 노드가 3일 때, 메모이제이션된 값이 있다면 그 값을 쓰고 탐색을 중단한다.

이처럼 메모이제이션 되어있는 값이 늘어난다면, 탐색은 더욱 빨리 중지된다.

📌시간복잡도

DP 배열을 모두 채우는 시간이 최종적인 시간복잡도가 된다.

1. 탐색
   총 N개 노드에 대하여 각각의 노드를 현재 노드로 하여 탐색해야 하는 횟수는 N*2^N이다 (현재 노드가 될 수 있는 노드 수 * 모든 노드의 방문여부(true,false))
2. 부분문제 (DP 배열 갱신)
   DP 배열은 매번 min으로 갱신되어야하기 때문에 현재 노드로부터 다음 노드 N개에 대해서 모두 확인해야 구할 수 있다.(다음 노드가 될 수 있는 노드 수)

두 값을 곱한 것이 최종 시간 복잡도가 된다.

⇒ O(N^2*2^N)

📌최단비용 원순열 문제의 시간복잡도 비교

	시간복잡도
브루트포스	O(N!)
단순 DFS	O(N^N)
외판원순회(DP+DFS)	O(N^2*2^N)

📌코드

#include <iostream>
#include <algorithm>
#define INF 1e9

using namespace std;

int N, W[16][16], dp[16][(1<<16)];

int TSP(int cur, int visit) {
    if (visit == (1 << N) - 1) { // 종료 조건
        if (!W[cur][0]) return INF;
        return W[cur][0];
    }
    if (dp[cur][visit]) return dp[cur][visit]; // dp 활용

    dp[cur][visit] = INF;

    for (int i = 1; i < N; i++) { // O(N)
        if (!W[cur][i]) continue; // cur->i 경로 없음
        if (visit & (1 << i)) continue; // i를 이미 방문함
        int tmp = TSP(i, visit | (1 << i)); // 부분문제 구하기(dp값). O(N*2^N)
        dp[cur][visit] = min(dp[cur][visit], tmp + W[cur][i]);
    } // O(N^2*2^N)
    return dp[cur][visit];
}

int main(void) {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> W[i][j];
        }
    }
    cout << TSP(0, 1); // 비트마스킹에서 1은 첫번째 노드만 방문한 것과 같음
}