1. Brute-Force - TSP 문제 알고리즘

TSP(Traveling Salesman Problem)

어떤 나라에 n개의 큰 도시가 있다고 하자. (2<=n<=10)

한 영업 사원이 한 도시에서 출발해 다른 도시들을 전부 한 번씩 방문한 뒤 시작 도시로 돌아오려고 한다.

이때 가능한 모든 경로 중 가장 짧은 경로를 구하는 문제이다.

// TSP 문제를 해결하는 재귀 호출 알고리즘

int n; // 도시의 수

double dist[MAX][MAX];  //  두 도시간의 거리를 저장하는 배열

// path : 지금까지 만든 경로

// visited : 각 도시의 방문 여부

// currentLength : 지금까지 만든 경로의 길이

// 나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.

double shortestPath(vector<int>& path, vector<bool>& visited, double currentLength){

// base case : 모든 도시들을 다 방문했을 때는 시작 도시로 돌아가고 경로 길이를 반환한다.

if(path.size() == n) return currentLength + dist[path.back()][path[0]];

double ret = INF; // 경로 길이를 맨 처음 비교할 때를 대비해서 매우 큰 값으로 초기화한다.

// 다음 방문할 도시를 전부 시도해 본다.

for(int next = 0; next < n; next++) {

if(visited[next]) continue;  // 이미 방문한 도시이면 넘어감

int here = path.back();

path.push_back(next);

visited[next] = true;

// 현재 고른 도시를 방문하고 남은 도시들을 모두 방문하는 모든 방법들 중 가장 짧은 경로를 재귀 호출을 통해 반환받는다.

double candidate = shortestPath(path, visited, currentLength + dist[here][next]);

ret = min(ret, candidate);  // 반복문을 돌면서 나온 경로의 최저 길이 후보들 중 가장 작은 값을 고른다.

visited[next] = false;

path.pop_back();

}

return ret;

}

이 문제를 해결할 때 결국 모든 경로를 찾는 방법은 n개의 원소의 순열을 찾는 것과 같다.

따라서 n이 10을 넘어가면, 즉 도시의 개수가 10개가 넘어가게 되면 이 알고리즘을 쓰기에는 시간이 너무 오래 걸리게 된다.

그 때는 다른 알고리즘을 적용하여야 한다.