[알고리즘 정리] - 외판원 순회 문제(Traveling Salesperson Problem, TSP)

 

💡외판원 순회 문제(Traveling Salesman Problem, TSP) 란? 

어떤 도시에서 출발하여 다른 모든 도시들을 돌고
다시 출발했던 도시로 돌아오는데 드는 최소 비용을 찾는 문제

브루트 포스 해결방법 ( 좋은 방법 x) 

외판원 순회 문제를 막연하게 생각해보면, 특정 출발 도시를 가정해놓고 도시를 순회해도 경로의 길이는 다르지 않을 것이다. 출발 도시를  A로 가정해놓고 다른 도시들을 순회하는 방식은 (n-1)! 형식으로 경우의 수를 구할 수 있다. 

하지만 이 경우는 n이 커지면 커질수록 많은 경우의 수를 따져주어야 하기 때문에 효율적인 방법으로 사용되지 않는다. 

 

 

DP 적용 방식 (도시가 16개 이하일 때) / 최적의 접근 방식 

DP 메모제이션 = (n-1)!의 모든 경로를 조사하지 않고 중복된 경로를 제거하는 기법 
비트마스크 = 특정 도시를 방문한 상태를 저장할 때 사용 

 

 

DP 메모제이션 기법은 동일한 하위문제의 반복을 막아줌으로써 더 높은 효율의 연산을 가능하게 해준다. 

(대표적으로는 피보나치 수열을 Top-Down 방식을 구할 때 사용) 

 

비트마스킹은 bit 연산으로 예를 들어 16개의 도시를 표현할 때 위의 방법으로 표현하려면 2^16가지의 경우를 일일이 다 표현해야하는데 비트마스킹으로는 16bit으로 표현할 수 있다. 

예를 들어 16개의 도시들 중 1번, 2번, 6번 도시를 방문 했다고 하면 0000 0000 0010 0011 이런식으로 각 자리에 1로 방문 표시를 해줄 수 있다. 

 

그림과 같이 1번~5번 도시들과 이동 가능한 경로가 있다고 가정해본다. 

출발 경로를 1이라고 지정했을 때 ,

왼쪽 그림은 1-> 2-> 3-> 5-> 4 순으로 순회를 하고 오른쪽그림은 1-> 3-> 2-> 5-> 4 순으로 순회를 한다. 

위 두 방식은 5->4 의 경로가 중복되어 구해진다. 

이미 방문한 도시들과 현재 위치한 도시가 같은 경우에는 최소 비용이 일정하므로 5번 도시에서의 최소비용은 같다. 따라서 중복되는 경우를 두번 구하는건 효율적이지 않다.

이럴 때  DP 메모제이션 기법을 사용하여 최소비용을 저장해두어 중복하여 구하지 않도록 한다. 

 

 

최소비용은 2차원 배열로 표현하는데, 최소비용이 같을 조건 즉 , 행은 이미 방문한 도시들의 집합, 열은 현재 있는 도시번호를 표시한다. 

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

이때 i의 범위는 모든 경우의 수 0<=i<=2^n , j의 범위는 0<=j<=5이다. 

 

왼쪽 그림을 DP 메모제이션 기법을 활용해보면 1->2->3->5->4 순으로 도시를 지날 때, DP[00001][1], DP[00011][2], DP[00111][3] , DP[10111][5] , DP[11111][4] 순으로 갱신된다. 

1->3->2->5->4 순으로 도시를 지날 때는 DP[00001][1], DP[000101][3], DP[00111][2] , DP[10111][5], DP[11111][4] 순으로 갱신되는데, 5번 도착했을 시 [10111][5]에 값(=3)이 이미 있으므로 그 이후를 구할 필요 없이 해당 배열의 값을 사용하면 된다.

 

이렇듯 DP메모제이션 기법과 비트마스킹을 사용하여 최소 비용을 구하는 방법이 외판원 순회 문제에 최적화된 알고리즘 탐색 기법이다. 

 

 

 

 

백준 외판원 순회 문제 풀어보기 : https://www.acmicpc.net/problem/2098

2098번: 외판원 순회