(여행 판매자)
# 문제
외판원 순회 문제는 영어로 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로 가기 위한 비용을 나타낸다.
항상 순회할 수 있는 경우만 입력으로 주어진다.
# 출력
첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.설명
이 문제는 완전히 동일합니다. 상업 투어 2도시의 수를 나타내는 N의 범위가 다르다.
- 세일즈맨 2: (2 $\leq$ N $\leq$ 10)
- 지금 문제: (2 $\leq$ N $\leq$ 16)
모든 경우를 찾는 전수탐색으로 풀 때 시간복잡도는 $O(N!)$
최악의 경우 20922789888000(16!)을 계산하고 시간 초과됩니다.
이것을 해결하기 위해 가면을 조금수업 DP시간 복잡도를 $O(N^2 * 2^N)$로 줄일 수 있습니다.
가면을 조금
0. 비트마스킹을 사용하는 이유
이 문제를 해결하기 위해서는 도시를 방문하는 모든 경로의 수를 찾아야 하므로,
방문한 도시와 방문하지 않은 도시를 추적해야 합니다.
방문한 도시에 대한 정보 준비도시 수가 많을수록 로 저장할 때 메모리가 커집니다.
배열 대신 비트마스킹을 사용하면 단일 정수를 사용하여 방문한 도시 집합을 나타낼 수 있습니다.
어떻게…?
각 비트는 도시를 나타내며 방문 여부에 대한 값을 제공합니다.
예를 들어, 5개의 도시가 있고 도시 {1, 3, 4}를 방문했다면 $11010(2)$를 이진법으로 나타낼 수 있습니다.
이와 같이 비트 마스킹을 사용하면 공간 복잡도를 크게 줄일 수 있으며,
또한 어레이를 사용하는 것보다 훨씬 빠르게 작업을 수행할 수 있으므로 시간 복잡도를 개선할 수 있습니다.
먼저, 이 문제에 비트마스킹을 적용하기 위해 무엇이 필요한지 알아봅시다!
1교대 근무
- 비트 시프트 연산을 사용하여 비트를 왼쪽으로 시프트할 수 있습니다.
- 왼쪽 이동은 이진수의 비트를 지정된 자릿수만큼 왼쪽으로 이동하고 빈 자리는 0으로 채웁니다.
- 예를 들어 $1(2)$를 왼쪽으로 두 칸 이동하면 $100(2)$가 됩니다.
2. 방문한 도시로 추가
- 도시를 방문하면 해당 도시에 해당하는 비트의 값이 0에서 1로 변경됩니다.
- 또는 연산(|): 왼쪽 또는 오른쪽에서 1인 모든 비트의 값이 1이 됩니다.
1(2) | 100(2) == 101(2)
visited | (1 << next) # next: 현재 방문할 도시3. 방문 여부 확인
- 및 연산(&): 왼쪽과 오른쪽이 겹치지 않으면 0이 됩니다.
0을 반환하면 방문하지 않은 도시입니다.1(2) & 100(2) == 0
visited & (1 << next) # next: 현재 방문할 도시4. 모든 도시를 방문했는지 확인
- 모든 도시를 방문하면 1에서 N까지 채워지며 그 값은 $(1 << N) -1$입니다.
4개의 도시가 있고 모든 도시를 방문하면 $1111(2)$ 즉 2^4-1$15입니다.
visited == (1 << N) - 1 # N: 도시의 개수
화신
1. DFS로 검색을 시작합니다.
- 0번째 도시를 방문한 후 검색을 시작합니다.
같은 경로를 운전하면 해당 경로 내에서 어느 도시에서 시작하든 관계없이 비용이 동일합니다.
출발 도시를 0번째 도시로 설정할 수 있습니다. - 비트 마스킹을 사용하여 0번째 방문 도시를 표시하는 함수에 방문함을 전달합니다.
visited: 1(2)
dp = {}
def DFS(now, visited):
~~~
print(DFS(0, 1)) # now: 0번째 도시부터 방문, visited: 0번째 도시 방문 처리
2. 모든 도시를 방문했다면 왕복 여행 비용을 구하십시오.
- 모든 도시를 방문했다면, Visited 값은 $(1 << N) - 1$입니다.
4개의 도시가 있고 모든 도시를 방문하면 $1111(2)$ 즉 2^4-1$15입니다. - 출발지까지의 왕복 여행 비용을 반환합니다.
- 이때 출발도시로 돌아갈 수 없는 루트라면 무한대를 반환하여 최소한의 비용으로 그 루트는 받아들여지지 않도록 한다.
(여기서 반환된 값은 이 경로의 비용에 추가됩니다.)
# 모든 도시를 방문한 경우
if visited == (1 << N) - 1:
# 다시 출발 도시로 갈 수 있는 경우 출발 도시까지의 비용 반환
if world(now)(0):
return world(now)(0)
else:
# 갈 수 없는 경우 무한대 반환 (이 경로가 최소비용으로 채택되지 않게)
return int(1e9)
3. 이전에 계산된 경로의 경우 dp를 사용합니다.
- 현재 방문할 도시와 이전 경로가 동일한 경로를 이미 계산했다면,
재계산 없이 dp 테이블에서 해당 값을 가져옵니다.
# 이전에 계산된 경우 결과 반환
if (now, visited) in dp:
return dp((now, visited)) # now까지 방문한 최소 비용
4. 다음 마을을 방문할 수 없으면 무시하십시오.
- 비용이 0인 도시에는 갈 수 없습니다.
continue
- 이미 이 도시를 방문한 적이 있더라도
continue
방문했는지 확인
- 방문한 적이 있는지 확인하기 위해 그리고 (&) 수술사용
- 및 연산(&) : 좌우가 겹치는 부분이 없으면 0이 됩니다.
0을 반환하면 방문하지 않은 도시입니다.
min_cost = int(1e9)
for next in range(1, N):
# 비용이 0이어서 갈 수 없거나, 이미 방문한 루트면 무시
if world(now)(next) == 0 or visited & (1 << next):
continue
5. 방문 가능한 도시라면 DFS 검색을 계속하십시오.
- 방문할 도시와 함께 DFS 함수가 호출되고 해당 도시를 방문했음을 나타냅니다.
방문했는지 확인
- 도시를 방문하면 해당 도시에 해당하는 비트의 값이 0에서 1로 변경됩니다.
- 또는 연산(|): 왼쪽 또는 오른쪽에서 1인 모든 비트의 값이 1이 됩니다.
- 현재 도시를 방문하는 비용과 DFS를 통해 모든 도시를 방문하는 비용의 합계입니다.
cost세트,
최저가인지 확인하세요min_cost업데이트하려면
cost = DFS(next, visited | (1 << next)) + world(now)(next)
min_cost = min(cost, min_cost)
6. 현재 경로를 dp 테이블에 추가합니다.
- 현재 도시를 방문하는 방법 중 최소 비용을 얻었으므로 이 정보를 dp 테이블에 저장합니다.
dp((now, visited)) = min_cost # 현재도시까지 방문하는 방법 중 최소 비용이 드는 루트의 비용 저장
끝!
전체 코드
import sys
N = int(input())
world = ()
for _ in range(N):
world.append(list(map(int, sys.stdin.readline().split())))
dp = {}
def DFS(now, visited):
# 모든 도시를 방문한 경우
if visited == (1 << N) - 1:
# 다시 출발 도시로 갈 수 있는 경우 출발 도시까지의 비용 반환
if world(now)(0):
return world(now)(0)
else:
# 갈 수 없는 경우 무한대 반환 (이 경로가 최소비용으로 채택되지 않게)
return int(1e9)
# 이전에 계산된 경우 결과 반환
if (now, visited) in dp:
return dp((now, visited)) # now까지 방문한 최소 비용
min_cost = int(1e9)
for next in range(1, N):
# 비용이 0이어서 갈 수 없거나, 이미 방문한 루트면 무시
if world(now)(next) == 0 or visited & (1 << next):
continue
cost = DFS(next, visited | (1 << next)) + world(now)(next)
min_cost = min(cost, min_cost)
dp((now, visited)) = min_cost # 현재도시까지 방문하는 방법 중 최소 비용이 드는 루트의 비용 저장
return min_cost # 현재도시까지 방문하는 비용 리턴
print(DFS(0, 1)) # now: 0번째 도시부터 방문, visited: 0번째 도시 방문 처리