외판원 순회 (TSP) 알고리즘 개념

외판원 순회 문제 (Traveling Salesman Problem)는 조합 최적화 문제의 일종이다.

 

브루트 포스로 해결

한가지 정말정말 무식한 방법이 있긴 하다. n개의 점들을 도는 순서를 순열을 통해 구해놓고, 그 경로를 따라 가면서 거리를 구하는 것이다. 하지만 알다시피, n개 점들의 순열의 경우의 수는 n!개이다... n이 20만 되어도 2,432,902,008,176,640,000가지, 한국말로 '243경' 개의 경우의 수를 따져 주어야 한다.

동적 계획법으로 해결

1~n번 도시가 있고, 이 중 몇 개의 도시를 거친 후에 지금 판매원이 i번 도시에 있다.
그럼, 이 중에서 거쳐오지 않았던 도시들 중에서 다음 도시를 정해야 한다.

우리는 다음 도시로 이동했다고 '가정' 하는 방식을 사용할 것이다.

좀 더 이해하기 쉽게 n 개수를 줄여서, 5개 도시를 돌아야 하고, 이 중 1, 2번 도시를 돌았다고 하자. 3, 4, 5번 도시가 남았다. 이 때 우리는 3가지 경우의 수를 생각할 수 있다.

• 3번 도시를 방문 + 나머지 4, 5번 도시를 최적으로 해결
• 4번 도시를 방문 + 나머지 3, 5번 도시를 최적으로 해결
• 5번 도시를 방문 + 나머지 3, 4번 도시를 최적으로 해결

이 중에서 최솟값이 우리가 찾는 그 도시가 된다. 현재 상태에서 남은 점들을 최적 경로로 돌았을 때의 총 거리 이다. 즉 나머지 3, 4, 5번 도시를 최적으로 해결 하는 방법이다. 

구현

2차원 리스트 dp를, dp[i][visited]을 정의하자.

우리는 인덱스로 접근하기 쉽게 하기 위해서 두 번째 visited 인자로 숫자를 사용할 것이고, 각각의 비트를 각각의 도시에 매핑해서 0과 1로 방문 여부를 표시할 것이다.

즉, 5개의 도시 중 visit 이 00110 이라면 2, 3번 도시를 방문한 것이고

00001 이라면 1번 도시만 방문한 것이고
11111 이라면 모두 방문한 것이다.

그러면 00000부터 11111 (2^n-1) 까지, 총 2^n칸이 필요할 것이고 이것이 각각 현재 위치 i마다 다 필요하므로 dp 리스트는 n by n^2의 크기가 될 것이다.

그리고 앞서 언급했던 다음 도시로 이동했다고 '가정' 하는 것은 해당 도시 번호만큼 비트 시프트를 한 값을 | (or) 연산 해서 1로 만들어주는 것으로써 가능하다.

 

이제 점화식을 세워 보면

dp[i][visited] = min(dp[i][visited], dp[j][visited | (1 << j) + graph[i][j])

시간 복잡도

TSP(visited, currentVertex) =
if(visited == U) then dist(currentVertex, 0)
else then min(TSP(visited∪{k}, k) + dist(currentVertex, k),k ∈ U-visited)

visited의 경우의 수는 2^n, 현재 위치한 currentVertex가 n개가 있으므로, 부분 문제는 n*2^n개이다. 그리고 각각의 부분 문제 안에서 n만에 풀기 때문에 전체 시간 복잡도는 O(n^2*2^n)이다.

 

 

출처