TSP

외판원 순회 문제 (Traveling Salesperson Problem)는 조합 최적화 문제의 일종으로, NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다.

외판원 문제는 다음과 같이 설명할 수 있다. 어떤 외판원이 n개의 도시를 방문할 계획을 수립하고 있다고 가정하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위하여 외판원이 거주하고 있는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 일주여행 경로를 찾고자 한다.


<파이썬 알고리즘 인터뷰> p.320, 책만, 2020

그림과 같이 각 도시의 위치가 표시된 미국 지도가 있다. 각 도시를 한 번씩 방문한다고 했을 때, 어떤 순서로 방문해야 가장 짧은 거리가 될까?만약 도시가 20개라고 할 때 이 문제의 정답을 찾기 위해 다녀야 하는 총 경로의 수는 $20!$다. 이 값은 얼마나 될까? $20!=2,432,902,008,176,640,000$이다. 그러니까 약 240경 번의 경로를 다녀봐야 가장 짧은 경로를 찾을 수 있다. 문제는 단순하지만 정답은 실로 엄청나다.

외판원 순회 문제는 다음과 같이 그래프 이론의 용어로 엄밀하게 정의할 수 있다.

주어진 완전 그래프 G=(V, E)가, 연결되어 있고(connected) 가중치가 있는(weighted) 완전한(complete) 그래프라고 가정하자. 이 그래프에서 출발 정점에서 다른 모든 정점들을 방문하고 원래의 출발 정점으로 되돌아 오는 순환 경로들 중에서 가중치의 합이 최소가 되는 순환 경로를 찾아라.

외판원 순회 문제는 NP-난해 집합에 속하는 문제라는 것이 증명되었다. 다항 시간에 이 문제를 해결할 수 있는 해결책을 아무도 찾지 못했으며, 다항 시간에 문제를 해결하지 못한다는 것도 아무도 증명하지 못했다. 그래서 난해하다고 하는 것이다.

외판원 순회 문제의 최적해는 동적 계획(Dynamic Programming)으로 지수 시간에 풀 수 있다. 다음은 동적 계획으로 외판원 순회 문제를 해결하는 파이썬 소스 코드이다.

def travel (W):
    n = len(W) - 1
    size = 2 ** (n - 1)
    D = [[0] * size for _ in range(n + 1)]
    P = [[0] * size for _ in range(n + 1)]
    for i in range(2, n + 1):
        D[i][0] = W[i][1]
    for k in range(1, n - 1):
        for A in range(1, size):
            if (count(A, n) == k):
                for i in range(2, n + 1):
                    if (not isIn(i, A)):
                        D[i][A], P[i][A] = minimum(W, D, i, A)
    A = size - 1
    D[1][A], P[1][A] = minimum(W, D, 1, A)
    return D, P

def minimum (W, D, i, A):
    minValue = INF
    minJ = 1
    n = len(W) - 1
    for j in range(2, n + 1):
        if (isIn(j, A)):
            m = W[i][j] + D[j][diff(A, j)]
            if (minValue > m):
                minValue = m
                minJ = j
    return minValue, minJ

위 풀이법에 대한 자세한 해설과 소스 코드에 대한 설명은 이 영상을 참고하면 된다. [1]

외판원 순회 문제의 최적해는 분기 한정(Branch-and-Bound)으로 지수 시간에 풀 수 있다. 다음은 동적 계획으로 외판원 순회 문제를 해결하는 파이썬 소스 코드이다.

def travel2 (W):
    global minlength, opttour
    n = len(W) - 1
    PQ = PriorityQueue()
    v = SSTNode(0)
    v.path = [1]
    v.bound = bound(v, W)
    minlength = INF
    PQ.put((v.bound, v))
    while (not PQ.empty()):
        v = PQ.get()[1]
        if (v.bound < minlength):
            for i in range(2, n + 1):
                if (v.contains(i)): 
                    continue
                u = SSTNode(v.level + 1)
                u.path = v.path[:]
                u.path.append(i)
                if (u.level == n - 2):
                    for k in range(2, n + 1):
                        if (not u.contains(k)):
                            u.path.append(k)
                    u.path.append(1)
                    if (length(u.path, W) < minlength):
                        minlength = length(u.path, W)
                        opttour = u.path[:]
                else:
                    u.bound = bound(u, W)
                    if (u.bound < minlength):
                        PQ.put((u.bound, u))

def bound(v, W):
    n = len(W) - 1
    total = length(v.path, W)
    for i in range(1, n + 1):
        if (hasOutgoing(i, v.path)):
            continue
        min = INF
        for j in range(1, n + 1):
            if (i == j): continue
            if (hasIncoming(j, v.path)): continue
            if (j == 1 and i == v.path[len(v.path) - 1]): continue
            if (min > W[i][j]): min = W[i][j]
        total += min
    return total

위 풀이법에 대한 자세한 해설과 소스 코드에 대한 설명은 이 영상을 참고하면 된다. [2]