직장인의 개발 일기

오늘 설명할 알고리즘은 외판원 순회 알고리즘(Traveling Salesperson Problem, TSP)입니다. 조합 최적화 문제로 전산학에서 연구된 가장 유명한 문제 중 하나입니다. 이 문제의 요구사항은 간단합니다. 각 도시들을 한 번씩 방문하고, 여행을 시작한 도시로 다시 돌아오는 최단 경로를 구하는 것입니다.

외판원 순회 문제의 경우 도시(N)의 개수가 10개 이하일 때와 16개 이하일 때 2가지로 나눠서 생각할 수 있습니다.

[ 동작 원리 ]

먼저 N이 10개 이하일 때는 완전 탐색을 통하여 구할 수 있습니다. 10개의 도시를 모두 한 번씩 방문하고 시작했던 도시로 돌아오는 방법은 모두 10! = 3628800이므로 충분히 완전 탐색을 통하여 구할 수 있습니다.

여기서 가장 중요한 포인트는 시작점이 어디여도 상관이 없다는 것입니다.

예를 들어

1→2→3→4→5→1,

2→3→4→5→1→2,

3→4→5→1→2→3,

…

위의 모든 경로가 이동거리가 같은 것을 볼 수 있습니다. 하지만 위의 방법은 겹치는 경로가 많이 발생하고 이를 줄일 수 있다면 더 많은 도시를 경유할 수 있을 것입니다. 따라서 N의 개수를 16개까지 더 늘려보겠습니다.

N이 16개 이하일 때는 dp을 통하여 구할 수 있습니다. dp [ 현재 도시 ][ 방문한 도시 ] = 남은 도시들을 방문할 수 있는 최단 경로입니다. 현재 도시에서 나머지 도시들을 방문할 때 최단 경로를 저장함으로써 중복되는 계산과정을 줄일 수 있습니다.

그리고 이때 방문한 도시는 비트 마스킹을 통해서 구현합니다. 위의 그래프처럼 5개의 도시가 있다고 생각하면 모두 방문했을 때 비트는 11111일 것입니다. 만약 1번 도시를 제외하고 모든 도시를 방문했다면 11110이 됩니다.

이를 점화식으로 표현하면 dp [ 현재 도시 ][ 방문한 도시 ] = min( dp [ 현재 도시 ][ 방문한 도시 ], 현재노드에서 i번 도시까지 거리 + dp[ i ][ 방문한 도시 ] )가 됩니다.

이를 통해 다음 문제를 풀 수 있습니다.

https://rudalsd.tistory.com/37