순회하는 외판원 문제(Traveling Salesperson Problem, TSP)

외판원 문제는 NP문제로 유명한 문제이다. 

여러 도시들이 주어져 있고, 모든 도시들에 대한 가중치가 주어졌을때, 단일 시작점부터 시작해서 모든 도시를 단 한번씩만 방문하여 다시 시작점으로 돌아오는데 드는 최단 거리를 구하는 문제이며, 말은 그냥 일반 그래프 문제인거 같아 그리 어려워 보이지 않지만, 무려 NP-hard 문제에 속한다.

이 문제가 어려운게 완전 연결 그래프라는 점인데, 단순히 완전 탐색으로 진행을 하면 무려 O(N!)라는 시간복잡도가 나온다.

이는 10개만 탐색해도 3,628,800이라는 값이 나오며,  20개는 2,432,902,008,176,640,000개라는 상상하기도 힘든 값이 나온다. 

완전 탐색으로도 풀이는 가능하지만 왠만하면 지양해야 하는 방법이다.

DP로도 생각보다 빠른 시간으로 탐색이 안되서, 실제로는 그리디로 '최단 거리'는 못구해도 '그나마 괜찮은 거리'를 구하는 정도로 사용하는 듯 하다.

<C++ 완전 탐색 TSP>

0번 도시부터 시작해서 모든 도시를 순회한 후 최종적으로 다시 0번으로 돌아오는 코드이다.

무식하게 모든 경우의 수를 일일히 다 계산하는 방법이다.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int n;
//가중치를 저장하기 위핸 배열 
int dist[15][15];
int TSP(vector<int> path, vector<bool> visited, int len){
    //모든 도시 다 방문했을 경우 
    if(path.size() == n) return len+dist[path.back()][0];
    int ret = 987654321;
    
    for(int next=0; next<n;next++){
        //방문 했다면 패스 
        if(visited[next]==true) continue;
        
        int cur = path.back();
        path.push_back(next);
        visited[next] = true;
        ret = min(ret,TSP(path,visited,len+dist[cur][next]));
        visited[next] = false; 
        path.pop_back();
    }
    return ret; 
}
int main(){
        cin >> n;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                cin >> dist[i][j];
            }
        }
        vector<int> path(1, 0); // 경로를 저장할 벡터, 시작 도시 0번도시 선택. 
        vector<bool> visited(n, false); // 방문 여부를 저장할 벡터. false로 초기화. 
        visited[0] = true; // 출발 도시 방문여부 체크.
        double ret = TSP(path, visited, 0);
        cout << ret << endl;
}

하지만 앞서 말했듯이 이 코드는 15개 이상부터는 어마어마한 시간이 걸린다.

그래서 완전 탐색 말고 DP를 사용하는 방법을 보도록 하자.

<C++ TSP 동적계획법>

동적계획법으로 구현하려면 이를 부분 문제로 쪼개야 한다.

완전 탐색으로 구현했을 때 쓰는 값들은 지금까지의 경로를 저장한 벡터, 방문여부를 저장한 벡터, 지금까지 연결된 거리이다.

동적계획법은 기본적으로 각각 독립적인 부분 문제로 쪼개지므로 지금까지 연결된 거리는 필요가 없고, 현재점을 기준으로 연산을 해야한다.

즉 

라는 점화식으로 풀 수 있다.(여기서 n은 0부터 next까지로, visited를 검사해서 방문한 적이 없는 값으로만 조사를 진행해야된다.)

시작점과, 현재 방문한 도시를 기준으로 모든 도시를 순회해서 얻을 수 있는 최소 거리를 출력하는 식이다.

그럼 거리에 대한 정보를 어떻게 메모이제이션을 할까? 해당 시작점으로 출발하는 경로는 메모이제이션 할때 어떻게 표현할까?

이에 대한 답은 비트마스킹이다. 비트로 도시의 방문 여부를 체크하는 것이다.

예를 들어 0번 도시와 2번 도시를 방문했다면, 00000101 = 3으로 체크가 될 것이고,  0번,3번,5번 도시를 방문했다면 00101001 = 41이 될것이다.

즉 1번 건물에서 1,2,3번 건물을 방문한 것은 cache[1][7]에 메모이제이션 하면 될 것이다.

int형은 4바이트, 총 32비트이기 때문에 int형 변수만으로도 32개 도시를 표현 할 수 있다.

코드를 작성하기전에 비트 연산을 간단하게 보도록 하자.

1<<n : 1을 n만큼 왼쪽으로 시프트한다. 즉 1<<4이면 10000이다.

a = a | (1<<n) : a라는 변수의 n번째 비트를 켠다.

a & (1<<n) : a라는 변수의 n번째 비트가 켜있으면 1<<n을, 꺼있으면 0을 반환한다.

a -=(1<<n) : a라는 변수의 n번째 비트를 끈다(1->0). 단 무조건 켜져 있을 때만 사용해야한다.

a &=~(1<<n) : a라는 변수의 n번째 비트를 끈다. 꺼져 있으면 꺼진 상태로 유지한다.

a ^=(1<<n) : a변수의 n번째 비트를 토글한다. 켜있으면 끄고, 꺼있으면 킨다.

즉 위 비트연산을 이용하면 visited&(1 << next)는 next번째 도시의 방문 여부를 확인하는 것이고.

또한 재귀 호출의 visited인자로 visited | (1 << next)를 전달 하는 것은, 해당 도시의 방문 여부를 체크해서 전달하는 것이다.

밑은 비트마스킹 DP를 이용해 구현한 코드이다.

#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAX_VALUE 987654321.0
using namespace std;
int n;
//경로를 저장할 dp 
int cache[17][65536], dist[17][17];
int TSP(int cur, int visited) {
    //점이 10개라면, 100000000000-1 =011111111111;
    if (visited == (1 << n)-1)  return dist[cur][0];
    
    int& ret = cache[cur][visited];
    if (ret != 0) return ret;
    ret = MAX_VALUE;
    for (int next = 0; next <= n; next++) {
        if (visited&(1 << next))continue;
        if (dist[cur][next]==0) continue;
        ret = min(ret,TSP(next, visited | (1 << next)) + dist[cur][next]);
    }
    return ret;
}
int main(){
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&dist[i][j]);
        }
    }
    printf("%d",TSP(0,1));
} 

완전 탐색으로 푸는 TSP는 O(N!)인것에 반해 DP는 O(2^N*N^2)이다. DP로 풀어도 빠른 속도는 아니지만 완전 탐색에 비해 현저하게 빨라지긴 했다.

<경로 추적하기>

위 소스 코드에서 메모이제이션한 값으로 경로를 추적해보았다.

방법은 간단하다. 이 소스코드는 0이라는 위치부터 시작하므로,

 전체 거리 - 0부터 다른 경로까지의 거리 = cache[k][masking + (1 << k)](k에서 masking에 켜져있는 비트의 도시들과 k번째 도시를 방문한 값)을 만족하는 것을 찾으면, k가 바로 다음 경로가 되는 것이다.

이 k를 경로를 저장하기 위한 벡터에 저장하자.  그 후k를 다음 경로를 찾기 위해 비교하기 위한 변수 piv에 넣는다.

그리고 비교할 거리를 masking에 켜진 도시들과 k를 방문했으며, k부터 시작하는 거리인 cache[k][masking + (1 << k)]으로 바꾼 후, k번째 비트를 방문했다는 표시로 켜준뒤 전과 같은 연산을 반복적으로 진행하면 된다.

void printPath(long double distance){
    int piv = 0, masking = 1;
    //cache 배열을 탐색해가며 다음 경로를 찾는다. 
    for(int j = 0; j<=n;j++){
        for(int k = 0; k <= n; k++){
            if(masking&(1 << k)) continue;
            if (distance - dist[piv][k] == cache[k][masking + (1 << k)]) {
                //다음 경로 저장 
                path.push_back(k);
                distance = cache[k][masking + (1 << k)];
                piv = k; masking += (1 << k);
            }
        }
    }
    //경로 출력 
    for(int i=0; i<path.size();i++)
        printf("(%d)->",path[i]);
    printf("(0)");
}