[알고리즘] 외판원 문제

외판원 문제란?

---

가장 유명한 최적화 문제 중 하나로 Traveling Sales-man Problem (TSP)라고 불리는 문제이다. 어떤 나라에 n(2<=n<=10)개의 큰 도시가 있다고 해보자. 한 영업 사원이 한 도시에서 출발해 다른 도시들을 전부 한 번씩 방문한 뒤 시작 도시로 돌아오려고 한다.

이때 각 도시들은 모두 직선 도로로 연결되어 있다고 했을 때, 영업 사원이 여행해야 할 거리는 어느 순서로 각 도시들을 방문하느냐에 따라 달라진다. 이때 가능한 모든 경로 중 가장 짧은 경로를 어떻게 찾아낼 수 있을까?

무식하게 풀기

---

시작한 도시로 돌아오는 경로를 찾는 것이므로, 경로의 시작점은 어떤 점으로 하든 결과는 늘 같다.

해당 문제를 무식하게 풀기 위해서는 (n-1)! 개의 경로를 직접 탐색해야만 한다. n이 최대 10이 될 수가 있으므로 탐색해야 하는 경로의 최대 수는 9! 즉, 362,880개가 된다. 따라서 안전하게 완전 탐색 방식으로 문제를 해결할 수 있다.

 

재귀호출 방식

---

각 점에서 도달할 수 있는 도시는 총 자신을 제외한 n-1개의 도시이다. 즉, 완전 탐색을 위해서는 각 점에서 n-1개의 모든 도시를 방문하여 경로의 distance를 계산한 후, 최솟값을 구하면 된다. 

n개의 도시로 구성된 경로를 n개의 조각으로 나누어서, 재귀호출 방식으로 문제를 해결하면 된다. 

코드

---

 

import java.util.LinkedList;
 
public class TSP {
    static int n = 5;
    static final int INF = 123456;
    static int dist[][] = {
            {0,3,4,5,6}, 
            {3,0,2,1,3}, 
            {4,2,0,4,3}, 
            {5,1,4,0,4}, 
            {6,3,3,4,0} };
        
 
    public static void main(String[] args) {
        LinkedList<Integer> path = new LinkedList<Integer>();
        boolean[] visited = {true,false,false,false,false};
        path.add(0);
        System.out.println(tsp(0, path, visited));
        
 
    }
    
    public static int tsp(int currentLength, LinkedList<Integer> path, boolean[] visited) {
        int ret = INF;
        
        if(path.size() == n) { // 다시 출발지로 복귀
            return currentLength + dist[path.peekFirst()][path.peekLast()];  
        }
        
        for(int i=0; i<n; i++) {
            if(visited[i]) {
                continue;
            }
            int here = path.peekLast();
            path.add(i);
            visited[i] = true;
            int now = tsp(currentLength + dist[here][i], path, visited);
            if(ret > now) {
                ret = now;
            }
            path.pollLast();
            visited[i] = false;
        }
        
        
        return ret;
    }
 
}