문제
외판원 순회(TSP)는 어느 한 도시에서 출발해 다른 모든 도시를 거쳐 다시 원래 도시로 돌아올때 가장 적게 든 비용이 얼마인지를 구하는 문제이다. 출발 도시 외 다른 도시로 두번 갈 수는 없다.
접근하기
10971번 외판원 순회2는 쉬운 버전으로 도시의 개수가 10개 이하이다. 이 경우는 DFS 완탐으로 모든 경로를 다 탐색해서 풀 수 있었는데 이 문제는 도시의 개수가 16이다. 완전탐색 시 O(N!), 16!의 시간이 걸려서 완탐으로 풀 수 없다.
는 아니고
사실은 완탐인데 DP를 이용해서 중복된 계산을 줄이는 것이다.
어떻게 풀까?
1. 완탐 돌리기
- 완전탐색을 돌린다.
- 만약 unvisited가 비어있으면 모든 도시를 방문한 경우임 -> 지금 도시에서 출발지로 가는 거 더해줌 (없으면 float('inf'))
- 만약 dp 테이블에 지금 출발지에서 unvisted 도시 집합으로 갔던 경우가 있으면 dp값을 가져옴
- 아니면 포문 돌려서 지금 도시에서 unvisted도시 집합으로 가는 최소 경로를 구하고 dp에 넣어줌
2. 점화식 풀어쓰기
- 출발 지점(S)을 제외하고 남은 도시들을 한 집합(unvisited)에 넣는다
- 남은 도시 중에 하나(B)를 방문하고 집합에서 뺀다.
- 출발지 B에서 그 집합으로 갈 때의 최소 비용의 경로를 구해서 디피 테이블에 적는다.
- 나중에 그 출발지에서 다시 그 집합으로 가는 경우가 있으면 디피테이블의 값을 가져온다.
왜 여기서 비트마스크가 필요해?
여기서 중요한 건 특정 출발지에서 남은 방문할 도시 집합으로 가는 경우가 디피 테이블에 저장된다는 것이다. 즉,
지금 나는 1번 도시에 있고 남은 도시가 2,3,4 인 경우의 최적의 경로를
dp[1][집합{2,3,4}] 이렇게 저장할 것이고,
내가 1번 도시에 있고 남은 방문할 도시가 3인 경우의 최적의 경로를
dp[1][집합{3}]
이렇게 저장할 것이다.
물론 이때까지 방문한 도시를 저장해도 무관하다.
근데 저 방문하지 않은 (혹은 방문한) 도시 집합을 어떻게 인덱스화 할 것이냐가 문제다. 집합 자체를 키로, 인덱스로 쓸 수는 없다.
키로 쓸려면 해시 가능해야 하는데 파이썬의 set은 변하는 값이라서 해시 불가능하다. frozenset을 쓰면 키로 쓸 수 있지만 값을 변경하기 힘들어서 무용지물이다. 애초에 그렇게 쓰는게 좋은 방법이 아니다.
결국 방문하지 않은 도시를 0101 문자열을 이용해서 표시하고
(0101이면 0번 3번 도시를 방문해야함)
그걸 십진수로 바꿔서 리스트의 인덱스로 쓴 것이다.
그럼 dp[1][5]가 1번도시에서 0번3번도시를 방문해야 한다는 뜻이다.
비트마스크 안쓰면?
결국 그 집합을 어떻게 dp테이블의 키로 쓸 것이냐의 문제로 돌아왔다. 비트마스크가 메모리적으로나 연산적으로나 효율적이어서 결국 비트마스크를 쓰는게 맞긴하다. 하지만 안쓰는 방법도 있다.
방법은 딕셔너리와 튜플을 쓰는 것이다.
딕셔너리의 키로 지금 도시와 방문하지 않은 도시들을 튜플화 한 거 두개를 쓴다. 그리고 거기에 해당하는 값을 넣어주면 된다.
사실 방문하지 않은 도시들은 자꾸 변하기 때문에 튜플화 한다는 게 그닥 좋은 방법이 아니다. 튜플은 변하지 않는 값이기 때문에
[x for x in unvisited if x != next_city]
tuple(unvisited)
이렇게 번거로운 과정이 많다.
돌아봐도 좋은 코드는 아니지만... 그래도 이 방법을 찾아본 것에 의의가 있지 않을까 한다. 코치님이 비트마스크 안쓰고도 할 수 있다는 말에 몇시간 고민해보고.. 포기했는데 조원이 방법을 찾아줘서 이렇게 블로그에 남길 수 있게 되었다.
코드
import sys
def tsp_memo(W, current, unvisited, memo):
if not unvisited:
return (
W[current][0] if W[current][0] else float("inf")
)
if (current, tuple(unvisited)) in memo:
return memo[(current, tuple(unvisited))]
min_cost = float("inf")
for next_city in unvisited:
if W[current][next_city]:
cost = W[current][next_city] + tsp_memo(
W, next_city, [x for x in unvisited if x != next_city], memo
)
min_cost = min(min_cost, cost)
memo[(current, tuple(unvisited))] = min_cost
return min_cost
N = city_count = int(sys.stdin.readline())
W = travel_costs = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
start_city = 0
initial_unvisited = [i for i in range(1, N)]
memo = {}
result = tsp_memo(W, start_city, initial_unvisited, memo)
print(result)번외
여러분들 그거 아세요?
DP 테이블은 도시가 4개 이하일때는 참조되지 않는답니다.
이게 몬말이냐 하면 4개까지는 디피 테이블이 무용지물이고 도시가 4개일때
if (current, tuple(unvisited)) in memo:
return memo[(current, tuple(unvisited))]이런식으로 디피에 있는 값을 참고하는 부분에 print('아무말')을 찍으면 아무것도 안찍힌다는 뜻이다.
5개부터 찍힌다.
5개는 한 경로만 dp테이블에서 가져와지고,
6개는 두개의 경로가 dp테이블에서 가져와진다.
이거 때문에 모든 경우 다 그려보고 난리쳤는데 결론은 도시가 많아져야 중복되는 경로가 생긴다는 것이다. 5개부터인 이유는 지금 내가 있는 도시, 방문하지 않은 도시를 제외하고 남은 도시들이 2개 이상이어야 경로가 여러가지가 나오기 때문이다.
출발지가 0, 내가 있는 도시가 3, unvisited 가 4일 경우
0 1 2 3 4 랑 0 2 1 3 4
이렇게 두가지가 생기는데
0 1 2 3 4 를 할 때
지금 내가 3에 있고 unvisted가 4인 경우의 dp를 생성해주기 때문에
0 2 1 3 4 를 할 때
내가 3에 있고 unvisted가 4인 경우를 dp테이블에서 가져올 수 있는 것이다.
그것보다 작으면 어짜피 경로가 하나뿐이어서 할 필요가 없다는 뜻!
진짜 별짓 다했다..ㅋ_ㅋ 외판원 순회 푹먹 기록은 여기까지~
언니 멋져요