외판원 순회(TSP: Traveling Salesperson Problem)

외판원 순회(TSP: Traveling Salesperson Problem)란 도시들이 있고 특정 도시에서 도시로 이동할 때 드는 비용이 주어졌을 때 불특정한 도시에서 출발해서 모든 도시를 돌고 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제입니다.

외판원 순회는 NP문제로 이번에 소개할 알고리즘은 N이 16개 이하일 때 DP와 비트마스크를 이용하여 구하는 방법입니다.

---

DP는 특정 도시들을 방문한 상태일 때 최소 비용을 저장해 놓고 이를 사용합니다.
비트마스크는 특정 도시를 방문한 상태를 저장할 때 사용합니다.

예를 들어서 1~3번 도시가 있다고 했을 때, 110(2)는 2,3번 도시를 방문한 상태입니다. 110(2)를 십진수로 바꿔보면 6(1x22 + 1x21 + 0x20)이 됩니다.
즉, 이진수로 봤을 때 오른쪽에서 부터 i번째 수가 1이면 i번 도시가 방문, 0이면 i번 도시가 미방문인 상태를 뜻합니다.

도시가 3개 일 때, 방문한 도시 상태의 경우의 수는 23(8)이고 이를 정리해보면 다음 표와 같습니다. 

	이진수	십진수	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

이제 본격적으로 TSP에 대해 알아보겠습니다.

 

---

TSP는 위에서 언급했다시피 불특정한 도시에서 출발해서 모든 도시를 돌고 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제입니다.
여기서 하나 생각해볼게 출발도시를 어디로 하느냐 입니다.
출발도시를 정해주지 않는데 사실 어떠한 도시를 출발도시로 하던지 모든 도시를 돌아서 다시 출발도시로 돌아오는데 드는 최소 비용은 같습니다. 다시 출발 도시로 돌아오기 때문에 사이클이 발생하기 때문입니다.

예를 들어보겠습니다.
도시가 3개 일 때,
1 -> 2 -> 3
2 -> 3-> 1
3 -> 1 -> 2
이 3가지 경우는 모두 같습니다.

따라서 출발 도시를 어디로 해야할지는 고려할 필요 없이 임의의 도시로 정해두면 됩니다.
저는 1번도시를 출발도시로 보겠습니다.

---

위 그림과 같이 1~5번 도시들과 이동 가능한 경로가 있다고 합시다.
비용까지 적으면 그림이 복잡해져서 일단 생략했습니다.

최소 비용을 구하기 위해서는 깊이 우선 탐색으로 1번 도시부터 방문하지 않은 모든 도시들을 방문하고 출발 도시까지 도달 했을 때 드는 비용들을 구한 뒤 그 비용들 중 최소값을 구하면 됩니다.

 

1번 도시에서 출발해봅시다.

[그림 1]

1번에서는 2,3,4,5 번 도시를 갈 수 있는데 먼저 1번 도시에서 2번 도시로 갔을 때 모든 도시를 돌고 출발도시까지 돌아오는 최소 비용의 경로가 [그림 1]의 왼쪽과 같다고 하고, 1번 도시에서 3번 도시로 갔을 때의 최소 비용이 드는 경로가 오른쪽과 같다고 합니다.

이 때, 그림을 보면 5->4->1 의 경로의 최소 비용을 중복해서 구합니다.
이미 방문한 도시들과 현재 위치한 도시가 같은 경우에는 최소 비용이 일정하므로, 4,5번 도시를 방문하지 않고 5번 도시에서의 최소 비용은 같습니다. 따라서 이를 두 번 구하는 것은 효율적이지 않습니다.
도시가 적은 경우는 괜찮지만 도시가 증가함에 따라 이미 구한 최소 비용을 다시 구하는 시간낭비는 기하급수적으로 증가합니다. 이를 방지하기 위해 사용하는 것이 memoization입니다. (대표적으로 피보나치 수열을 Top-Down 방식으로 구할 때 사용하는 것이죠.)

최소 비용을 저장하기 위해 2차원 배열을 사용합니다. 행과 열은 최소 비용이 같을 조건 즉, 이미 방문한 도시들의 집합과 현재 있는 도시 번호입니다.
d[i][j] = 이미 방문한 도시들의 집합이 i이고 현재 있는 도시가 j일때, 방문하지 않은 나머지 도시들을 모두 방문한 뒤 출발 도시로 돌아올 때 드는 최소 비용.
여기서 i, j의 범위는 도시가 5개 이기 때문에 0<= i < 25(32), 0<= j <5 입니다.

그래서 1->2번 도시를 지났을 때 d[11111][4]와 d[10111][5]를 갱신해주고 (그림에 표시는 안했지만 d[00111][3], d[00011][2]도 갱신 됩니다.) 1->3번 도시를 지날 때는 1->3->2->5의 경로를 지나 5번 도시에 도착했을 때 d[10111][5]에 값이 있으므로 더 이상 구할 필요 없이 해당 배열에 있는 값 3을 사용하면 됩니다.(memoization)

이렇게 1번 도시에서 2,3,4,5 번 도시로 이동했을 때 각 도시에서 남은 도시들을 지나 다시 출발 도시로 돌아오는 최소 비용들 중 최소인 값이 우리가 구하고자 하는 값이 됩니다. 

이를 재귀함수로 구현하면 최소비용을 구할 수 있습니다.
상세한 코드는 아래에 소스코드 링크에서 확인해 주세요.

 

---

외판원 순회를 이용하는 기본적인 문제입니다.
외판원 순회(2098): https://www.acmicpc.net/problem/2098

---

 입출력은 외판원 순회(2098) 문제와 같습니다.
소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/tip/%EC%99%B8%ED%8C%90%EC%9B%90%EC%88%9C%ED%9A%8C.cpp