[알고스팟] 여행하는 외판원 문제 - 완전 탐색, 재귀

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 

 

여행하는 외판원 문제(링크)

도시들과 도시들 사이의 거리가 주어지면 모든 도시를 한 번씩 방문한 뒤 출발지로 돌아오는 가장 짧은 순환을 구한다. 문제에 따라 출발한 도시로 돌아오지 않고 모든 도시를 한 번씩 방문하기만 하도록 요구할 수도 있다. 이 경우는 최소 가중치 합의 해밀턴 경로를 구하는 것이라 할 수 있다.

최적화 문제

이전의 문제들은 하나의 답을 찾지만 외판원 문제와 같은 경우 여러 개의 답 중 어떤 기준에 따라 가장 좋은 답을 찾아내는 최적화 문제이다. 이런 특성에 따라 이전 재귀 함수의 형태와 다른 점들에 유의하자. 반환해야 하는 값이 문제에서 정한 기준에 따라 다르므로 단순히 대입이나 합산으로 반환값을 결정하지 않는다.

재귀적으로 생각하기

아직 방문하지 않은 도시 목록이 주어지면 하나를 선택해 방문하는 것을 하나의 작업 조각으로 본다. 재귀 함수의 입력으로는 이미 방문한 도시의 목록, 현재 방문 중인 도시, 현재까지 이동한 거리 정보가 필요하다. 

무식하게 풀 수 있을까?

문제에서 도시의 개수는 최대 10개이고 모든 도시에 대해 방문 순서를 정하므로 최악의 경우 10! 의 경우의 수를 가진다.

C++ 코드

#include <iostream>
#include <vector>
using namespace std;

const double INF = 987654321.0;
int n; // Number of the cities.
vector<vector<double>> distances; // Distances between cities.

// 출발했던 도시로 돌아오는 최단 거리.
// 따라서, 출발지는 상관없으므로 첫 번째 도시에서 출발.
// taken[0] = true, current = 0
double tsp_circuit(bool taken[10], int current, double length) {
    bool isFinished = true;
    for (int i = 0; i < n; ++i) {
        if (taken[i] == false) {
            isFinished = false;
            break;
        }
    }
    // 마지막으로 방문한 도시에서 출발지까지 거리를 더해 반환.
    if (isFinished == true) return length + distances[current][0];

    double ret = INF;

    for (int next = 1; next < n; ++next) {
        if (taken[next] == true) continue;

        taken[next] = true;
        // 도시를 방문하는 여러 순서 중 최단 거리를 찾는 최적화 문제이므로
        // 최소값을 반환값으로 선택한다.
        ret = min(ret, tsp_circuit(taken, next, length += distances[current][next]));
        taken[next] = false;
    }

    return ret;
}

 

출발지로 돌아오지 않는 최소 거리인 해밀턴 경로를 찾는 경우 주어진 도시들 외에 모든 도시까지의 거리가 0 인 dummy city 를 만들어서 시작한다. tsp_path 호출 시 current 를 -1 로 넘겨 dummy city 에서 시작함을 나타낸다.

 

// 출발지로 돌아올 필요 없이 모든 도시를 방문하는 최단 경로.
// current = -1
double tsp_path(bool taken[10], int current, double length) {
    bool isFinished = true;
    for (int i = 0; i < n; ++i) {
        if (taken[i] == false) {
            isFinished = false;
            break;
        }
    }
    // 마지막으로 방문한 도시까지의 거리만 반환하면 된다.
    if (isFinished == true) return length;

    double ret = INF;

    // 출발지로 돌아가지 않으므로 어디서 출발하는지에 따라 경로의 길이가 달라짐.
    for (int next = 0; next < n; ++next) {
        if (taken[next] == true) continue;

        taken[next] = true;
        ret = min(ret, tsp_path(taken, next, length += distances[current][next]));
        taken[next] = false;
    }

    return ret;
}