외판원 순회 문제 (Traveling Salesman Problem)는 조합 최적화 문제의 일종이다.

알고리즘의 배경은 다음과 같다.

여러 지역을 돌면서 물건을 판매해야 하는 판매원이, 모든 지역을 돌고 다시 출발점으로 돌아와야 한다고 할 때, 가장 최적의 경로를 찾는 문제

얼핏 보기에도 까다로워 보인다. 단순히 기준점에서부터 가장 가까운 점으로만 이동하면 되는 것이 아니라, 그 점으로 이동했을 때 다음 상황까지 함께 고려해 주면서 점을 선택해야 하기 때문이다.

브루트 포스로 해결

한가지 정말정말 무식한 방법이 있긴 하다. n개의 점들을 도는 순서를 순열을 통해 구해놓고, 그 경로를 따라 가면서 거리를 구하는 것이다.

하지만 알다시피, n개 점들의 순열의 경우의 수는 n!개이다... n이 20만 되어도 2,432,902,008,176,640,000가지, 한국말로 '243경' 개의 경우의 수를 따져 주어야 한다. '해결'법이라고 하기도 좀...

---

동적 계획법으로 해결

그럼 조금 더 머리를 쓰자.

1~n번 도시가 있고, 이 중 몇 개의 도시를 거친 후에 지금 판매원이 i번 도시에 있다.
그럼, 이 중에서 거쳐오지 않았던 도시들 중에서 다음 도시를 정해야 한다.

우리는 다음 도시로 이동했다고 '가정' 하는 방식을 사용할 것이다.

좀 더 이해하기 쉽게 n 개수를 줄여서, 5개 도시를 돌아야 하고, 이 중 1, 2번 도시를 돌았다고 하자. 3, 4, 5번 도시가 남았다. 이 때 우리는 3가지 경우의 수를 생각할 수 있다.

• 3번 도시를 방문 + 나머지 4, 5번 도시를 최적으로 해결
• 4번 도시를 방문 + 나머지 3, 5번 도시를 최적으로 해결
• 5번 도시를 방문 + 나머지 3, 4번 도시를 최적으로 해결

이 중에서 최솟값을 가지는 친구가 우리가 찾는 그 도시가 된다.

방금 구한 게 뭐지? 현재 상태에서 남은 점들을 최적 경로로 돌았을 때의 총 거리 이다. 즉 나머지 3, 4, 5번 도시를 최적으로 해결 하는 방법이다. 여기서 강조 표시한 부분이 반복되는 것이 보이는가? 이제 조금 점화식이 보일 것도 같다.

즉, 아직 방문하지 않은 점들 중 하나를 방문했다고 '가정' 하고, 그 점을 제외한 나머지 점들을 마저 돌았을 때의 거리를 구해 본다. 이 거리와, 현재 점과 가정한 그 점 사이의 거리의 합이 최소인 점!
그 점이 우리가 찾는 최적 경로의 다음 점이다.

---

이제, 2차원 리스트 dp를 만들자.

dp[i][visited]을 정의하기를,

현재 방문 상황은 visited 이고, 현재 위치는 i라고 할 때, 남은 점들을 최소 거리로 돌았을 때의 남은 이동 거리

로 정의하자.

이 때 우리는 인덱스로 접근하기 쉽게 하기 위해서 두 번째 visited 인자로 숫자를 사용할 것이고, 각각의 비트를 각각의 도시에 매핑해서 0과 1로 방문 여부를 표시할 것이다.

즉, 5개의 도시 중 visit 이 00110 이라면 2, 3번 도시를 방문한 것이고
00001 이라면 1번 도시만 방문한 것이고
11111 이라면 모두 방문한 것이다.

그러면 00000부터 11111 (2^n-1) 까지, 총 2^n칸이 필요할 것이고 이것이 각각 현재 위치 i마다 다 필요하므로 dp 리스트는 n by n^2의 크기가 될 것이다.

그리고 앞서 언급했던 다음 도시로 이동했다고 '가정' 하는 것은 해당 도시 번호만큼 비트 시프트를 한 값을 | (or) 연산 해서 1로 만들어주는 것으로써 가능하다.

이제 점화식을 세워 보면,

dp[i][visited] = min(dp[i][visited], 
					dp[j][visited | (1 << j) + graph[i][j])

가 될 것이다.

파이썬 구현 코드

n = int(f.readline())
INF = 999999

pos = [list(map(int, f.readline().split())) for _ in range(n)] # 점 좌표
graph = [[0 for _ in range(n)] for _ in range(n)] # graph[i][j] = graph[j][i] = 점 i와 점 j 사이의 거리
dp = [[INF] * (1 << n) for _ in range(n)]
# dp[i][j] : i = 내 위치, j : 아직 방문하지 않은, 방문해야 할 노드 정보
# 들어가는 값은 남은 점들을 최적 경로로 돌았을 때의 총 거리

def getDist(Ax, Ay, Bx, By) : # 유클리드 거리 반환
    return round(math.sqrt((Ax - Bx) ** 2 + (Ay - By) ** 2), 3)

def dfs(start, visited) :
    # start : 현재 내 위치
    # visited : 방문 여부 정보를 담고 있음. 해당 비트가 0이면 방문하지 않은 것, 1이면 방문한 것
    if visited == (1 << n) - 1 : # 모든 정점 방문
        dp[start][visited] = graph[start][0]
        return graph[start][0]
    
    if dp[start][visited] != INF :
        return dp[start][visited]
    
    for i in range(1, n) :
        if visited & (1 << i) : # 0번 점은 시작점이니까 패스하고 1부터 본다. 방문한 점이라면 pass
            continue
        # 그 다음 점까지의 거리 + 그 다음 점에 방문하고 나서 남은 점들을 최적 경로로 돌았을 때의 거리
        # 의 합이 가장 작은 점이 현재 visited 상태 최적 경로 상의 다음 점이 될 것이다.
        dp[start][visited] = min(dp[start][visited], dfs(i, visited | (1 << i)) + graph[start][i]) 
    
    return dp[start][visited]

출발점을 0으로 고정했다.
다시 출발점으로 돌아와야 하기 때문에 visited가 꽉 차있을 때 dp 값, 즉 남은 최적 경로는 그 마지막 경로의 점에서 출발점까지의 거리이다.

이러고 dfs(0, 1)을 호출해 주면, 전체 순환 경로의 최소 거리가 나온다.
출발점을 바꾸자면 dfs(s, 1 << s)가 되겠다.

번외 : 경로 구하기

총 거리 말고, 어떻게 돌아야 최소가 나오는지 경로 정보를 알고 싶으면 다음처럼 구현할 수 있다.

def printPath(k, visited) :
    # visited 상태에서, 남은 점들을 최적으로 돌 때, 다음으로 방문하는 점을 찾는다.
    path.append(k)
    
    if visited == (1 << n) - 1 :
        return
    
    nextvalue = [INF, 0]
    for i in range(n) :
        if visited & (1 << i) :
            continue
        # dp[i][visited] 현재 visited에서의 최적이 들어있고, 우리가 찾는건 다음의 최적 점이다.
        # 현재의 visited에 하나씩 비트 붙여가면서 값을 구했을 때, 그 값들 중 최솟값이 다음 최적 점이다. 
        if (graph[k][i] + dp[i][visited | (1 << i)]) < nextvalue[0] :
            nextvalue[0] = graph[k][i] + dp[i][visited | (1 << i)]
            nextvalue[1] = i
    
    # for loop 종료 시, nextvalue[0]에는 남은 점들을 최적으로 돌았을 때의 최소 거리가
    # nextvalue[1]에는 다음 점이 들어 있다
    
    printPath(nextvalue[1], visited | (1 << nextvalue[1])) # 반복.

현재 점이 k이고, 다음 방문하는 점은 위에서 설명했듯 그 점까지의 거리 + 그 점에서의 dp 값이 최소가 되는 점이다.

이것을 초기값 INF인 최솟값 변수를 갱신하면서 인덱스를 찾아 준 후,

그 인덱스를 OR 연산해서 채워넣고 다시 동일 함수를 호출하면 된다.

시간 복잡도는?

TSP(visited, currentVertex) =
if(visited == U) then dist(currentVertex, 0)
else then min(TSP(visited∪{k}, k) + dist(currentVertex, k),k ∈ U-visited)

visited의 경우의 수는 2^n, 현재 위치한 currentVertex가 n개가 있으므로, 부분 문제는 n*2^n 개이다. 그리고 각각의 부분 문제 안에서 n 만에 풀기 때문에 전체 시간 복잡도는 O(n^2*2^n)이다.