[DP] 외판원 문제 (Traverling Salseman Problem)

References

• Algorithms (Sanjoy Dasgupta)

Contents

• TSP (Traverling Salseman Problem)

---

The Traverling Salseman Problem

이번 포스팅에서 다루어 볼 내용은 컴퓨터 공학 분야에서 유명한 외판원 순회 문제(TSP)입니다. 많은 변종 문제들이 존재하지만, 가장 기본적인 문제를 살펴보도록 하겠습니다. 문제는 다음과 같습니다.

 

외판원은 대규포 판매 투어를 준비하고 있습니다. 가방을 들고 외판원의 고향부터 시작하여 다시 고향으로 돌아오기 전에 그가 목표로 하는 도시를 정확히 한 번만 방문하도록 여행합니다. 각 도시 간의 거리가 주어졌을 때, 전체 이동 거리를 최소화하기 위한 여행 계획을 세워야 합니다. 여기서 이동 거리는 비용이 되며, 즉, 비용을 최소화하는 이동 경로를 찾아야 합니다.

 

도시를 \(1, \cdots, n\)으로 표기하도록 하겠습니다. 그리고 외판원의 고향은 1이 됩니다. \(D = (d_{ij})\)는 도시 사이의 거리를 나타내는 행렬이라고 합니다. 외판원의 목적은 비용은 최소화하면서 고향에서 출발하여 다른 도시들을 정확히 한 번만 방문하고 다시 고향으로 돌아오도록 여행을 설계하는 것입니다. 예를 들어, 아래 그림은 5개의 도시 간의 거리(비용)을 보여줍니다.

위 그림에서 최소 거리는 10이 되며, A-C-E-B-D-A 순으로 여행하게 됩니다.

 

이 문제는 컴퓨터에게도 꽤 어려운 문제입니다. 사실 외판원 문제는 가장 악명 높은 computational task 중의 하나입니다. 이 문제를 해결하기 위한 시도는 오래 전부터 있었고, 많이 실패도 했지만 부분적인 성공도 있었습니다. 시행착오를 거치면서 알고리즘과 복잡도 측면에서 개선이 많이 되었습니다. 하지만 TSP에 대한 가장 기본적은 bad news는 TSP가 다항 시간에 해결될 가능성이 매우 낮다는 것입니다.

 

그렇다면 문제를 해결하려면 얼마나 많은 시간이 걸릴까요?

브루트포스(brute-force) 방법은 모든 가능한 투어를 평가하고 최적의 투어를 반환합니다. (n-1)!의 가능한 투어가 있기 때문에 이러한 접근 방식은 O(n!) 시간이 걸립니다. 따라서, 다항 시간은 아니지만 브루트포스보다는 더 빠른 동적 프로그래밍을 살펴보겠습니다.

 

외판원 문제를 해결하기 위한 적절한 하위 문제는 무엇일까요? 하위 문제들은 부분 솔루션들을 참조합니다. 그리고 이 문제에서 가장 확실한 부분 솔루션은 여행의 초기 단계입니다. 문제의 요구 사항처럼 도시 1에서 출발하여 몇 개의 도시들을 방문한 후 현재 도시 j에 있다고 가정해봅시다.

여기서 경로를 연장하려면 어떠한 정보가 필요할까요? 다음 번에 방문하기에 가장 편한 도시를 결정해야하기 때문에 우리는 도시 j에 대해 아는 것이 확실히 필요합니다. 그리고 여태까지 방문한 모든 도시들에 대한 정보를 알아야 합니다. 그래야 이미 방문했던 도시를 다시 방문하지 않습니다.

그렇다면 하위 문제는 다음과 같이 정리할 수 있습니다.

도시 1을 포함하고 \(j \in S\)인 도시들 \(S \in \{1, 2, \cdots, n\}\)의 부분집합에서 C(S, j)는 S의 각 도시를 정확히 한 번만 방문하면서 1에서 시작하여 j에서 끝나는 최단 경로의 길이가 된다.

\(|S| < 1\)일 때는 경로의 시작과 끝이 모두 1이 될 수 없기 때문에 \(C(S, 1) = \infty\)로 정의합니다.

 

더 작은 하위 문제를 C(S, j)로 표현해보도록 하겠습니다. 여기서 우리는 1부터 출발해서 j에서 끝나야 합니다. 그럼 마지막에서 두 번째 방문하는 도시로 어떤 도시를 선택해야 할까요? 어떤 \(i \in S\)가 이 도시가 된다면, 전체 경로 거리는 1부터 i까지의 거리 C(S - {j}, i)에 마지막 간선의 길이 \(d_{ij}\)가 더해져야 합니다. 여기서 우리는 최적의 i를 선택해야 합니다.

\[C(S, j) = \underset{i \in S: i \neq j}{min}C(S - \{j\}, i) + d_{ij}\]

하위 문제들은 \(|S|\)에 의해 순서가 지정되며, 알고리즘의 의사코드는 다음과 같습니다.

이 알고리즘에서 하위 문제의 수는 거의 \(2^n \cdot n\)개 입니다. 그리고 각 하위 문제는 문제를 풀기 위해 선형 시간이 걸립니다. 따라서 총 실행 시간은 O(\(n^2 2^n\))이 됩니다.

 

---

C++ 구현

백준에 기본적인 TSP 알고리즘을 사용하는 문제가 있습니다.

https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

대부분의 풀이를 살펴보면, 재귀와 메모이제이션을 사용해서 문제를 해결한 것으로 보입니다.

저는 위에서 살펴본 알고리즘을 그대로 구현해보고자 bottom-up 방식으로 재귀없이 구현해봤습니다. 물론 부분 집합을 나타내기 위해서 비트마스크를 사용한 것은 동일합니다.

#include <iostream>
#include <vector>
#include <algorithm>

const int INF = 123456789;

int tsp(const std::vector<std::vector<int>>& dist, const int s)
{
    const int N = dist.size();
    std::vector<int> path(1, s);
    std::vector<std::vector<int>> C(2 << (N - 1), std::vector<int>(N, INF));
    C[1][0] = 0;
    for (int s = 2; s <= N; s++) {
        std::vector<bool> S(N - s, false);
        S.insert(S.end(), s - 1, true);
        do {
            int subset = 1;
            for (int i = 0; i < N - 1; i++) {
                if (S[i] == true)
                    subset |= (1 << (i + 1));
            }

            for (int j = 0; j < N - 1; j++) {
                if (!S[j])
                    continue;

                for (int i = -1; i < N - 1; i++) {
                    if (i == -1 || (S[i] && i != j)) {
                        if (dist[i + 1][j + 1] != 0)
                            C[subset][j + 1] = std::min(C[subset][j + 1], C[subset - (1 << (j + 1))][i + 1] + dist[i + 1][j + 1]);
                    }
                }
            }
        } while (std::next_permutation(S.begin(), S.end()));
    }

    int subset = (1 << N) - 1;
    int min_val = INF;
    for (int j = 0; j < N; j++) {
        if (dist[j][s] != 0)
            min_val = std::min(min_val, C[subset][j] + dist[j][s]);
    }

    return min_val;
}

int main(int argc, char* argv[])
{
    int N;
    std::vector<std::vector<int>> dist;

    scanf("%d", &N);
    dist.resize(N, std::vector<int>(N, 0));
    int val;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &val);
            dist[i][j] = val;
        }
    }
    /*std::vector<std::vector<int>> dist{
        {0, 2, 2, 1, 4},
        {2, 0, 3, 2, 3},
        {2, 3, 0, 2, 2},
        {1, 2, 2, 0, 4},
        {4, 3, 2, 4, 0}
    };*/

    std::cout << tsp(dist, 0) << "\n";
}

TSP 알고리즘 부분에 조금 부연 설명을 하자면, 1을 포함하는 모든 부분 집합을 구하기 위해 C++의 next_permutation 함수를 사용했습니다. 어짜피 1은 무조건 포함이기 때문에 1을 제외한 도시들에 대해서만 수행하면 되므로 총 N-1개에 대해 permutation을 수행합니다. 위에서 살펴본 의사 코드와 최대한 맞추기 위해서 변수 이름을 알고리즘에서 사용한 용어에 맞추어서 사용했으므로 의사 코드와 실제 C++ 코드와 비교해보면 쉽게 이해하시리라 생각합니다.

 

(개인적으로 set과 map을 사용하면 조금 더 코드가 깔끔해지지 않을까 생각만 해봅니다...)