8. TSP 문제 비트마스크 + DP로 풀기

TSP 외판원 순회 문제

TSP 외판원 순회 문제는 대표적인 NP문제로, 완전검색으로 풀 수 있다. 이럴 경우 N!의 경우의 수가 발생하는데 N=12이상부터 폭발적으로 증가한다.

그런데 비트마스크와 DP를 활용하면 N=16까지 답을 구할 수 있다. 

---

1. 비트마스크

비트마스크는 특정 도시를 방문했는지 여부를 저장한다.

예를 들어 도시가 3개 라면, 비트마스크가 11-일 때 뒤에서부터 인덱스를 시작하여 2, 3번 도시는 방문, 1번 도시는 미방문 상태가 된다.

	비트마스크	십진수	3번 도시	2번 도시	1번 도시
1	000	0	x	x	x
2	001	1	x	x	o
3	010	2	x	o	x
4	011	3	x	o	o
5	100	4	o	x	x
6	101	5	o	x	o
7	110	6	o	o	x
8	111	7	o	o	o

 

2. DP

DP는 특정 도시들을 방문한 상태에서 최소 비용을 저장해놓고 이것을 사용한다.

들어가기전에 알아야할 것은, TSP문제는 cycle을 형성하는 문제이기 때문에 시작점을 어디로 두어도 똑같은 결과가 나온다.

우리는 1번 도시에서 출발을 해본다.

위 그림에서 두 경로의 cost를 계산할 때 5→4→1로 이동하는 경로에 대해 같은 연산을 중복해서 계산한다.

이것을 방지하기 위해 메모이제이션을 활용할 수 있다.

즉, 이미 구해진 최소비용은 2차원 배열에 저장해두는 것이다.

d[i][j] = 이미 방문한 도시들의 집합이 i이고 현재 있는 도시가 j일때, 방문하지 않은 나머지 도시들을 모두 방문한 뒤 출발 도시로 돌아올 때 드는 최소 비용.

이렇게 출발도시에서 시작하여 모든 도시를 다 돌고 난 후, 최소인 값이 우리가 구하고자 하는 값이다.

* d의 최솟값이 아님!

import sys

def move(now, depth):
    global charge, ans
    if depth == n:
        if path[now][0] > 0:
            ans = min(ans, charge + path[now][0])
        return
    
    visit[now] = 1
    for l in link[now]:
        if not visit[l]:
            charge += path[now][l]
            move(l, depth+1)
            charge -= path[now][l]
    visit[now] = 0

n = int(sys.stdin.readline())
path = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visit = [0] * n
link = {}
charge, ans = 0, 10**7

for i in range(n):
    link[i] = []
    for j in range(n):
        if path[i][j] > 0:
            link[i].append(j)

move(0, 1)

print(ans)
 

출처: https://suri78.tistory.com/152 [공부노트]

 

참고 ㅣ 외판원 순회(TSP: Traveling Salesperson Problem) (tistory.com)