tsp (travelling salesman problem)

알고리즘 2014. 6. 9. 16:13 |

1. intro

유명한 문제 tsp 는 링크에서 자세한 설명을. [link]

문제를 요약하자면,

n 개의 도시가 주어지고, 각 도시간의 거리가 주어질 때,

모든 도시를 가장 최소의 거리로 이동하는 경로를 찾는 문제이다.

이 문제는 대표적인 NP-Hard 문제이며, time complexity 는 O(2^n) 이다.

 

2. 풀이

2.1. 모든 경우의 수에 대해 값 구하기

이렇게 하면 물론 안 되겠지만, 모든 경로의 수는 입력 도시 수 n 에 대해서 n ! 이다.

입력이 10 개라면 3,628,800 개이다. 20개라면 ? 2,432,902,008,176,640,000 ... 구하기 싫어질 듯. (factorial 에 대해서는 다음 참고 : http://en.wikipedia.org/wiki/Factorial)

이렇게 하면 풀 수 없다는 것만 알고 넘어가자.

 

2.2. dynamic programming 으로 풀기

기본적으로 이 방법도 모든 경로에 대해 거리 합을 구한다.

단, 차이는 앞선 방법에서 발생하는 중복을 모두 제거하여 계산 횟수를 줄이는 방법을 사용한다.

예를 들면,

1 > 2 > 3 > 4 > 5

1 > 2 > 3 > 5 > 4

이와 같은 경로로 이동한 경우의 값을 구할 때, 1 > 2 > 3 까지는 공통이므로 중복 계산할 필요가 없다.

이런 방식으로 문제를 풀면, 입력 도시 수가 10개이면 계산해야 하는 경로의 경우의 수는 2048 (2^11) 개로 아까보다 현저히 줄어들었다.

도시 수가 20개 이면, 약 200 만 번만 계산하면 된다. ㅎㅎ

 

문제 풀이

이 문제는 다음과 같이 나누어 풀 수 있다.

도시 {1, 2, 3, 4, 5} 가 있다고 했을 때, 최소 경로를 min {1, 2, 3, 4, 5} 이라고 정의하자.

그렇다면 최소 값은,

min {1, 2, 3, 4, 5} = min (

1 > min {2, 3, 4, 5}, // 1 에서 출발하여 {2, 3, 4, 5} 를 순회하는 최소값

2 > min {1, 3, 4, 5}, // 마찬가지로 2 에서 출발하여 나머지를 순회하는 최소값

3 > min {1, 2, 4, 5},

4 > min {1, 2, 3, 5},

5 > min {1, 2, 3, 4}

)

 

1 > min {2, 3, 4, 5} 은 다음과 같은 의미를 가진다.

1 > min {2, 3, 4, 5} = min (

distance(1, 2) + min (2 > {3, 4, 5}), // "1 에서 2까지 거리" + 2 에서 출발하여 나머지 도시를 순회하는 최소값

distance(1, 3) + min (2 > {2, 4, 5}),

distance(1, 4) + min (2 > {2, 3, 5}),

distance(1, 5) + min (2 > {2, 3, 4})

)

 

이렇게 반복해서 전개하면 마지막에는 4 > {5} 와 같이 가장 단순한 형태로 귀결된다. 이 값은 distance(4 ,5) 이다.

 

자료구조

위 내용을 코드로 변경하려면, 순회하고자 하는 도시들의 집합을 간단히 표현할 수 있어야 한다.

집합을 표현할 때, 가장 간단한 방법은 bit flag 를 이용하는 방법이다.

예를 들어 2진수 11111 은 집합 {1, 2, 3, 4, 5} 를 나타낸다.

 

그렇다면, 1 에서 출발하여 {2, 3, 4, 5} 를 순회하는 최소값은 다음과 같이 코드로 표현할 수 있다.

tsp (1, 0x1E) // 16 진수 1E 는 2진수로 11110 이 된다.

따라서 tsp 함수의 원형은 다음과 같이 쓰면 된다.

int tsp (int from, int toFlag);

 

함수 tsp 는 재귀적으로 호출된다.

1
2
3
4
5
6
7
8
9
10
int tsp (int from, int toFlag) {
    int m = INT_MAX;
    for (int i = 0; i < _n /* the nuber of cities */; i++) {
        if (!(toFlag & (1 << i))) continue;
 
        int v = _distance[from][i] + tsp(i, (toFlag & ~(1<<i)));
        m = min(m, v);
    }
    return m;
}

비트 플래그 연산에 익숙하지 않다면 다음을 참고 : http://forum.codecall.net/topic/56591-bit-fields-flags-tutorial-with-example/

4 번 라인은 toFlag 에 포함되지 않은 index 를 걸러낸다.

그래서 실제 계산 부분은 6 라인이다.

7 라인에서는 6 라인에서 계산된 값 중 가장 최소값을 저장한다.

 

이 코드에서는 종료 조건과 memoization 코드가 없다. 완성된 코드는 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int tsp (int from, int toFlag) {
    int &memo = _memory[from][toFlag]; // _memory[][] 가 0 로 초기화 되어 있어야 함.
    if (memo != 0) {
        return memo;
    }
    if (bitCount(toFlag) == 1) {
        int to = getIndex(toFlag);
        return _distance[from][to];
    }
 
    memo = INT_MAX;
    for (int i = 0; i < _n /* the nuber of cities */; i++) {
        if (!(toFlag & (1 << i))) continue;
 
        int v = _distance[from][i] + tsp(i, (toFlag & ~(1<<i)));
        memo = min(memo, v);
    }
    return memo;
}

종료 조건은 toFlag 에 단 하나의 도시만 남는 경우이다. 

이 경우는 바로 distance(from, to) 를 반환하면 된다. to 는 알아서 구현해서 계산 하시기를 ... 

gcc 컴파일러를 사용한다면 bitCount() 를 구현할 필요 없이 __builtin_popcount() 를 사용할 수 있다.

역시 마찬가지로 getIndex() 대신 __builtin_ctz() 를 사용할 수 있다.

이에 대한 자세한 내용은 다음 링크를 참고 : http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

 

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstring>
using namespace std;
 
 
int _n; // num
const int MAX_SIZE = 15; // 입력 크기에 따라 충분히 (32 이상 될 수 없음)
int _distance [MAX_SIZE][MAX_SIZE]; // _distance
int _memory [MAX_SIZE][1<<MAX_SIZE]; // for memoization
 
 
 
void getInput() {
    cin >> _n;
    for (int i = 0; i < _n; i++) {
        for (int j = 0; j < _n; j++) {
            cin >> _distance[i][j];
        }
    }
    memset(_memory, 0, sizeof(int) * MAX_SIZE * (1<<MAX_SIZE));
}
 
  
int tsp (int from, int toFlag) {
    int &memo = _memory[from][toFlag]; // _memory[][] 가 0 로 초기화 되어 있어야 함.
    if (memo != 0) {
        return memo;
    }
    if (__builtin_popcount(toFlag) == 1) {
        int to = __builtin_ctz(toFlag);
        return _distance[from][to];
    }
 
    memo = INT_MAX; // 그냥 충분히 큰 수를 사용해도 된다
    for (int i = 0; i < _n /* the nuber of cities */; i++) {
        if (!(toFlag & (1 << i))) continue;
 
        int v = _distance[from][i] + tsp(i, (toFlag & ~(1<<i)));
        memo = min(memo, v);
    }
    return memo;
}
 
int main() {
    getInput();
    int m = INT_MAX;
    int allFlag = (1<<_n) - 1;
    for (int i = 0; i < _n; i++) {
        int v = tsp(i, allFlag & ~(1<<i));
        m = min(m, v);
    }
    cout << m << endl;
    return 0;
}
# 입력 
15
0 29 82 46 68 52 72 42 51 55 29 74 23 72 46
29  0 55 46 42 43 43 23 23 31 41 51 11 52 21
82 55  0 68 46 55 23 43 41 29 79 21 64 31 51
46 46 68  0 82 15 72 31 62 42 21 51 51 43 64
68 42 46 82  0 74 23 52 21 46 82 58 46 65 23
52 43 55 15 74  0 61 23 55 31 33 37 51 29 59
72 43 23 72 23 61  0 42 23 31 77 37 51 46 33
42 23 43 31 52 23 42  0 33 15 37 33 33 31 37
51 23 41 62 21 55 23 33  0 29 62 46 29 51 11
55 31 29 42 46 31 31 15 29  0 51 21 41 23 37
29 41 79 21 82 33 77 37 62 51  0 65 42 59 61
74 51 21 51 58 37 37 33 46 21 65  0 61 11 55
23 11 64 51 46 51 51 33 29 41 42 61  0 62 23
72 52 31 43 65 29 46 31 51 23 59 11 62  0 59
46 21 51 64 23 59 33 37 11 37 61 55 23 59  0
 
 
# 출력
262

 

3. 약간의 개선

나중에 쓰겠습니다. ㅎㅎ


저작자표시
:

티스토리툴바