문제
[문제]
외판원 순회 문제는 영어로 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로 가기 위한 비용을 나타낸다.
항상 순회할 수 있는 경우만 입력으로 주어진다.
[출력]
첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.Traveling Salesman Problem
여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것
= 가중치가 있는 완전 그래프에서 가장 작은 가중치를 가지는 순환 경로를 구하는 문제
아이디어
브루트포스 vs. 다이나믹 프로그래밍
브루트포스 O(N!)
모든 도시의 방문 순서(순열)를 구하고 각 비용을 계산해보는 방법 = O(N!)
- 문제에서 N의 최대는 16이므로 제한 시간 내에 풀이할 수 없다.
다이나믹 프로그래밍 O(N^2*2^N)
슈도코드
-
w[도시1][도시2]= 도시1에서 도시2까지 가는 비용 저장. 가는 길이 없을 경우 0으로 표시. -
dp[현재 도시][도시 방문 상태]= 특정도시 방문 상태를 거친 후현재 도시에 위치할 때, 현재 상태에서 순회 여행을 하는 데 드는 최소 비용을 저장
def TSP(현재 도시, 도시 방문 상태):
if dp[현재 도시][도시 방문 상태] 값이 존재한다면:
return dp[현재 도시][도시 방문 상태]
if 모든 도시 방문 완료:
if 현재 도시에서 시작 도시로 가는 길이 있으면:
return w[현재 도시][시작 도시]
else:
return ∞
# 현재 상태에서 다음 도시를 방문했을 때 순회 여행을 하는 데 걸리는 최소 비용을 구해보자
for 다음 도시 in 모든 도시:
if 이미 방문한 도시 continue
if 다음 도시로 가는 길이 없으면 continue
다음 도시를 방문했을 때, 시작 도시로 돌아가는 데 드는 최소 비용
= w[현재 도시][다음 도시] + TSP(다음 도시, 다음 도시를 추가한 도시 방문 상태)
if 위에서 계산한 비용이 dp[현재 도시][도시 방문 상태]보다 적다면 갱신
return ∞
슈도코드를 기반으로 시간 복잡도를 계산하면
-
TSP 함수에서
- 도시 방문 상태가 가질 수 있는 상태 = 2^N
- 현재 도시가 가질 수 있는 상태 = N
- 현재 상태에서 다음 도시를 방문했을 때 순회 여행을 하는 데 걸리는 최소 비용을 구하는 동작의 시간 복잡도 = O(N)
-
따라서, O(N^2 * 2^N)
- 문제에서 N의 최대는 16, 제한 시간 내에 풀이 가능
비트마스킹
도시 방문 상태를 표시할 때, 비트마스킹을 이용한다.
-
방문 상태를 배열로 표시하면 메모리를 너무 많이 먹는다.
-
비트마스킹을 이용하면 정수 형태로 방문 표시가 가능해진다.
-
예시
0b001= 0번째 방문0b101= 0번째와 2번째 방문방문 상태 & 0b001을 통해 0번째 방문 여부를 체크할 수 있음방문 상태 | 0b001을 통해 0번째 방문 표시를 할 수 있음
-
제출 코드
Python
유의사항
-
dp 표시 시, 갈 수 없는 경우는 INF로, 값이 아직 없는 경우는 0으로 표시했다.
-
메모리 크기를 줄여주기 위해, 방문 표시 시 주어진 도시가 N개인 경우 (N-1)개의 비트를 사용했다.
-
TSP를 풀 때, 시작 도시는 고정해도 된다.
1->2->3->1이 최소 비용을 갖는 경로라고 할 때,3->1->2->3또한 그렇다.- 즉, 최소 비용을 갖는 순회 경로를 찾는 것이므로 시작점은 어디가 되든 상관이 없다.
-
나의 풀이 방법에서는 시작점을 0번째 도시로 고정했다.
-
나머지 도시들에 대한 방문 표시만 하면 되므로 (N-1)개의 비트를 사용해도 된다.
-
import sys
input = sys.stdin.readline
n = int(input())
w = [list(map(int, input().split())) for _ in range(n)]
# dp[city][history] = 현재 위치가 city이고, 방문 기록이 history일 때, **이 시점에서 다시 출발점인 0까지 순회할 때**의 최소 비용을 저장한다.
# 방문 기록 = 비트마스크
dp = [[0] * (1 << n - 1) for _ in range(n)]
INF = float('inf')
def dfs(city, history):
# print("city:", city, "history:", bin(history))
# 최소 비용이 존재할 때
if dp[city][history] != 0:
return dp[city][history]
# 모든 경로를 방문했을 때
if history == (1 << (n-1)) - 1:
# 다시 출발 도시 0으로 돌아갈 수 없는 경우
if not w[city][0]:
return INF
# 현재 위치에서 출발 도시 0으로 돌아가는 경우의 비용을 반환
return w[city][0]
# 다음 방문 도시 결정
min_cost = INF
for next_city in range(1, n): # 시작점은 제외하자
# 경로가 없는 경우
if not w[city][next_city]:
continue
# 이미 방문한 경우
if (history & (1 << (next_city - 1))) > 0 :
continue
# 방문할 수 있는 도시인 경우
# 현재 위치에서 next_city까지의 이동 비용 + next_city에서 출발점 0으로 돌아가는 이동 비용 합산
current_cost = w[city][next_city] + dfs(next_city, (1 << (next_city - 1)) | history)
min_cost = min(min_cost, current_cost)
dp[city][history] = min_cost
return min_cost
ans = dfs(0, 0)
print(ans)참고 사이트
코뉴로그