외판원 순회 문제(Traveling Salesman problem)

외판원 순회 문제

2098번 - 외판원 순회(https://www.acmicpc.net/problem/2098)

• 다이나믹 프로그래밍
• 비트마스킹
• 비트필드를 이용한 다이나믹 프로그래밍
• 외판원 순회 문제

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

풀이

도시간에 이동하는 비용이 모두 다르기 때문에 방문하는 순서에 따라 모두 다른 경우가 된다.
예를 들어 도시가 1, 2, 3, 4, 5 이렇게 5개 있을 때, 1-2-3-4-5-1 과 1-2-3-5-4-1은 다른 경우이다. (예시의 경로가 연결 되어 있다고 가정)
또한 비용이 대칭적이지 않기 때문에 1-2-3-4-5-1 과 역순인 1-5-4-3-2-1도 다른 경우이다.

즉, N개의 도시가 있을 때 N의 모든 순열이 문제의 모든 경우의 수가 된다. Brute Force로 풀면 시간복잡도는 O(N!).

연산을 줄이기 위해서 중복되는 연산을 메모이제이션을 통해 반복하지 않아야한다.

메모이제이션을 사용하기 위한 전제는 특정 상태에서는 결과 값이 항상 같다는 것인데 이는 상태를 어떻게 정의하느냐가 중요하다.
이 문제에서는 지금까지 방문한 도시들 정보와 현재 위치한 도시가 메모이제이션을 위한 상태가 된다.

여기에서 부터 외판원 문제에 비트마스킹이 도입된 이유가 나온다.

지금까지 현재 위치한 도시를 포함해서 지금까지 방문한 도시의 개수를 X(1 ≤ X ≤ N)개라고 할 때, O(N!) 문제에서 각 연산이 상태를 표시하기 위해 X개 변수를 가지고 있다면 너무 많은 메모리를 요구하게 된다.

그리고 Memoization 배열의 Indexing 또한 어렵기 때문에, X개의 정보를 압축시켜 표현해야 할 필요가 있다.

상태는 특정 도시에 방문한적 있는지 없는지에 대한 boolean 정보이기 때문에 n자리의 2진수에서 k번째 도시에 방문한적이 있다면 k번째 bit를 1로 설정해 상태를 나타낼 수 있다.

비트마스킹으로 상태를 표현하기 위한 하나의 조건이 더 있는데 바로 상태의 개수이다. 문제의 조건에서 2 ≤ N ≤ 16 이기 때문에 적용할 수 있다는 점도 기억하고 있어야한다. (N개의 도시가 있을 때, 상태의 최댓값은 2^(N+1)-1이 된다.)

코드

from sys import stdin
INF = 10**9
n = int(stdin.readline())
cost = []
for i in range(n): cost.append(list(map(int, stdin.readline().split())))
cache = [[0] * (2**n) for _ in range(n)] 
def tsp(now, visited):
    if(visited == (1 << n)-1): #(1 << n)-1 은 모든 도시가 1로 표시 되어있어 모두 방문했다는 것을 의미한다.
        if(cost[now][0] > 0): return cost[now][0]
        else: return INF
    #cache[now][visited]에서 now은 현재 도시 위치, visited는 방문했던 도시들의 정보
    if(cache[now][visited] > 0): return cache[now][visited]
    result = INF
    for next in range(n):
        if(visited & (1 << next)): continue
        if(cost[now][next] == 0): continue
        result = min(result, tsp(next, visited | (1 << next)) + cost[now][next])
    cache[now][visited] = result
    return result

print(tsp(0, 1))