Traveling Salesperson Problem (TSP) - 0

외판원문제(TSP)에 대해 살펴보도록 하겠습니다.

 

외판원문제는 난해한 문제로 잘 알려져있지요. 

간단히 말하면 "모든 도시들을 한 번씩 방문하는데 드는 최소 비용을 구하라" 정도가 될 것같습니다.

 

예를 들어볼까요?

 

위와 같은 도시들이 있다고 합시다. 1,2,3이 도시의 번호이고 가운데 숫자는 도시간 이동비용이 되겠습니다.

어떻게 가야 비용이 덜 들까요? 1->2->3의 순서로 가면 되겠네요. (총 비용 30) 

3->2->1의 순서로 가도 같은 비용이군요. 3->1->2와 같은 최악의 선택만 하지 않으면 됩니다.

 

외판원 문제가 어려운 이유는 "가능한 모든 경로를 조사해야 한다"는 사실에 있습니다.

 

위 그림에서 가능한 경로는

1->2->3

1->3->2

2->1->3

2->3->1

3->1->2

3->2->1

이렇게 6가지가 됩니다. 3! 과 같네요.

 

외판원 문제의 시간복잡도는 O(n!) 입니다.

도시 수가 적을때야 문제 없겠지만 많아지면 문제가 된다.

 

도시가 15개 일때는...? 계산기를 두드려보니 1307674368000 이라는 값이 나오는군요.

(늙어 죽을 때까지 계산해도 안될 것같습니다..)

 

일일이 다 해보는 방법 말고 조금 더 좋은 방법은 없을까요?

---

외판원 문제에 동적계획법(DP: Dynamic Programming)을 적용해보자!

여기 재미있는 문제가 있습니다.

문제링크: TSP2

 

알고스팟(algospot.com)이라는 곳에서는 tsp1부터 tsp3까지 문제를 제시하고 있습니다. 

 

문제 자체에 차이는 없는데 도시 수가 늘어난다는게 문제입니다. 도시수가 늘어날수록 효율적인 방법을 생각해야 합니다.

외판원 문제에 동적계획법을 적용해보도록 하지요.

동적계획법이란 새로운 해를 구하는데 그 전 과정에서 구한 부분 해를 이용하는 방법입니다.

그렇다면 어떤 값을 부분 해로 이용해야 할까요?

예를 들어보겠습니다. 5개 도시가 있다고 했을 때 다음과 같은 경로들이 있을 수 있겠지요.

1->2->3->4->5

1->2->3->5->4

..

2->1->3->4->5

..

빨간 부분을 보니 한 번 방문했던 경로(3->4->5)를 다시 방문하고 있군요.

이렇게 겹쳐지는 부분에 대한 해를 구해놓고, 나중에 다시 같은 경로가 등장하면 저장한 값을 이용할 수 있을 것 같습니다.

 

여기서 좀 더 범위를 넓혀봅시다.

 

3->4->5, 3->5->4의 경우 이렇게 표현 해볼 수 있지요. 

// 3에서 4, 5로 구성되는 도시를 방문하는데 드는 비용.

3->{4,5} (중괄호는 set을 의미합니다.)

위의 예를 좀 더 일반적인 식으로 대충 정리해보면 다음과 같습니다.

 

// N에서 출발해서 모든 도시를 방문할 때 드는 비용.

f(N, {N-1, N-2, ...., 1}) = cost(N, N-1) + f(N-1, {N-2, N-3, .... , 1})

구현한다면 재귀함수 형태가 되겠네요.

 

식에서 구한 f값 중 최소 값을 취하면 원하는 결과를 얻을 수 있을 것같습니다.

 

그리고 중간중간 구해진 최소 값(부분해)을 저장해두면 되겠네요.

(ex: 3->4->5에 대한 답은 f(3, {4,5})에서 얻어지므로 이 결과를 어딘가에 저장)

---

자, 이제 구현 단계로 넘어가봅니다. 

문제는 "1에서 {2,3,4...}로 가는 비용"을 저장해야 하는데 그 방법을 생각해봐야합니다.

 

다른 방법도 있겠지만 저는 경로를 표현하는데 bit열을 이용하기로 했습니다.

 

문제에서 최대 도시수가 15를 넘어가지 않으므로 정수형 변수에 모든 경로를 저장할 수 있겠군요. (아래 그림참고)

  그림. bit를 이용한 경로 저장의 예

 

즉, 가장 오른쪽 bit부터 왼쪽 bit 순서로 도시 번호가 됩니다. 이렇게 해서 경로 표현을 좀 단순화 시켰습니다.

 

그리고 경로에 대한 최소비용은 이차원 배열을 이용해서 저장해둡니다. 

bit열인 경우 임의의 경로에 대한 값이 유일하므로 다른 경로에서 구한 해와 겹쳐지지않고 사용할 수 있습니다.

 

예를 들면, {1,2,3}, {1,2,4}에 대한 해는 다른 경로이므로 따로 저장되어야 합니다.

 

이 경로를 bit로 표현해보면 각각 0000 0111(=7), 0000 1011(=11)이 됩니다. 

 

이 두 값은 다르므로, 이 값들을 배열의 index로 사용한다면, 결국 각기 다른 경로에 대한 해를 따로 저장해둘 수 있는 것입니다.

 

dp를 저장공간 이름이라고 하면 아래와 같이 되겠네요.

 

dp[1][0000 1110(=14)] = f(1, {2,3,4}) ==> 도시 1에서 2,3,4를 순회하는 최소비용

dp[2][0000 1101(=13)] = f(2, {1,3,4}) ==> 도시 2에서 1,3,4를 순회하는 최소비용

...

말로 하려니 힘드네요. =_= 아래 코드와 주석을 이용하겠습니다.

#include <stdio.h>
#include <string.h>
#include <math.h>
 
const int MAX_NODE = 16;
const double INF = (double)MAX_NODE * 1500.0; 
 
#define min(a,b) ((a)<(b)?(a):(b))
 
double cost[MAX_NODE][MAX_NODE];
    // 중간 해를 저장할 공간. dp[from][경로(도시들의 집합)]
double dp[MAX_NODE][1<<16];
 
int bitarr[MAX_NODE];
 
double tsp(int from, int path, int len)
{
    if (len == 1) {
        int to = (int)log2(path);
        return cost[from][to];
    }
// 저장한 값을 이용
    if (dp[from][path]) {
        return dp[from][path];
    }
 
    double ans = INF;
 
   for(int i = 1; i < MAX_NODE; i++)
   {
       if (bitarr[i] & path) 
       {
           int node = bitarr[i];
           // 새로운 경로는 목적지 node를 제외한 나머지 도시들
           int npath = (path & ~node);
           // 다음 목적지 지정. node는 2^n 값만 존재
           int to = (int)log2(node);
           // f(N,{N-1,N-2...1}) = cost[N][N-1] + f(N-1, {N-2,N-3...1})
           
           double fcost = tsp(to, npath, len-1);
           double newcost = cost[from][to] + fcost;
 
           ans = min(ans, newcost);
       }
    }
// 최소비용을 저장
    dp[from][path] = ans;
 
    return ans;
}
 
int main()
{
    int t, N;
    // bit에서의 도시 위치를 배열에 저장
    // bit[1] = 0000 0001 ==> 1번 도시를 표시
    // bit[2] = 0000 0010 ==> 2번 도시를 표시
    // bit[3] = 0000 0100 ==> 3번 도시를 표시
    //...
    for(int i = 1; i < MAX_NODE; i++) {
        bitarr[i] = 1<<i;
    }
 
    scanf("%d", &t);
 
    while(t--)
    {
        // 도시간 비용 입력
        scanf("%d", &N);
 
        for(int i = 1; i <= N; i++) 
        {
            for(int j = 1; j <= N; j++) {
            scanf("%lf", &cost[i][j]);
        }
    }
 
    double ans = INF, result = 0.0; 
 
    memset(dp, 0, sizeof(dp));
 
    int path = 0;
    // 경로 저장. path에는 모든 도시가 저장됨
    
    for(int i = 1; i <= N; i++) 
    {
        path |= 1<<i;
    }
    
    // 출발지점을 차례대로 바꿔서 해를 구한다.
    for(int i=1; i<=N; i++) {
        int npath = (path & ~bitarr[i]);
        result = tsp(i, npath, N-1);
        ans = min(ans, result);
    }
 
    printf("%.10lf\n", ans);
    return 0;
}

[출처] 외판원문제(TSP: Traveling Salesman Problem)에 대한 고찰|작성자 moon knight