[알고리즘 - 이론] The Traveling Salesperson Problem : TSP (외판원 문제)

---

앞의 글을 읽으시면 이해에 도움이 됩니다.

 

2022.04.13 - [Computer Science/알고리즘] - [알고리즘] 동적 계획법 (Dynamic Programming)

[알고리즘] 동적 계획법 (Dynamic Programming)

2022.05.27 - [Computer Science/알고리즘] - [알고리즘 - 이론] Branch-and-Bound Strategy (분기한정법)

[알고리즘 - 이론] Branch-and-Bound Strategy (분기한정법)

---

1. Traveling Salesperson Problem : TSP란?

특정 도시를 출발하여 다른 도시들을 한 번씩만 들린 후, 다시 출발한 곳으로 돌아오는 경로를 찾는 문제
예를 들어 대구에서 출발하여 [부산, 포항, 대전, 서울]을 모두 들리고 다시 대구로 돌아오는 경로를 찾는 문제가 되겠습니다.
어디를 먼저 방문하는지는 상관없지만, 아무튼 경로의 합이 최소가 되어야 합니다.

일상 속에서 생각보다 자주 쓰이고 있고, 특히 택배 기사님들의 경로를 생각하면 쉽게 이해할 수 있습니다.

이를 Algorithm으로 풀어낸다면,
TSP의 목표는 방향이 있는 그래프에서
주어진 정점에서 출발하여, 그래프에 있는 각 정점을 정확하게 한 번만 방문하고, 출발한 정점으로 돌아오는 최단경로를 찾는 것이 목표입니다.

결국 순환을 하므로 출발 정점이 어디인지는 상관이 없습니다. 따라서 출발 정점은 단순히 첫째 정점이 될 수 있습니다.

 

따라서 해밀턴 회로를 이용해서 풀 수 있습니다.

이때 TSP를 푸는 알고리즘은 두 가지가 있습니다.

• Branch and Bound
  • https://hi-guten-tag.tistory.com/140
• DP
  • https://hi-guten-tag.tistory.com/141

분기 한정법으로 먼저 TSP를 풀어보겠습니다.

---

2. Branch and Bound (분기 한정법)

모든 정점을 상태 공간 트리에 표현하면 됩니다.
level 1에 출발 정점을 놓고, level 2에 그다음 갈 정점을 넣으면 됩니다.
자세한 정의는 아래에 적겠습니다.

정의 1) 정점이 n개라면 level n-1 까지만 가면 된다.

예를 들어 정점이 1, 2, 3, 4가 있다고 가정했을 때, level 3까지 갔을 때, 어떤 마디까지의 경로는 [1, 2, 4]가 될 겁니다.
따라서 다음에 들어가야 할 정점은 필연적으로 3이 되어야 하고, 3에서 다시 출발 정점까지 돌아올 수 있는지만 체크하면 됩니다.

정의 2) Bound(한계값)를 결정하는 법

best-first search를 사용하기 위해서 각 마디의 한계 값을 구할 수 있어야 합니다.
0-1 KnapSack에서는 W를 넘지 않는 무게에서 이익을 최대로 하는 것이 목표기 때문에, 마디에서 뻗어나가서 얻을 수 있는 이익의 상한을 계산하였습니다.

하지만 TSP에서는 최소 경로를 찾아야 하므로, 마디에서 뻗어나가서 얻을 수 있는 경로의 하한을 구해야 합니다.
만약 그 당시에 최소 경로 길이보다 경로의 하한이 작다면 해당 마디는 유망하다고 판단합니다.

그러면 한계값은 어떻게 얻을 수 있을까요?

남은 모든 마디의 모든 edge 중에 가장 길이가 짧은 edge의 가중치들의 합이 lower bound가 됩니다.
예시를 들겠습니다.

W	1	2	3	4	5
1	0	14	4	10	20
2	14	0	7	8	7
3	4	5	0	7	16
4	11	7	9	0	2
5	18	7	17	4	0

1에서 출발한다고 가정했을 때의 여행 경로의 하한을 구하면,
v1 = 4, v2 = 7, v3 = 4, v4 = 2, v5 = 4이므로, 1에서 출발했을 때 길이의 하한은 4 + 7 + 4 + 2 + 4 = 21이 됩니다.

그렇다고 이 길이의 여행 경로가 있다는 말은 아닙니다. 이보다 더 짧은 여행 경로가 있을 수 없다는 말입니다.

이제 v1에서 v2를 선택하여, 경로 [1, 2]를 포함한 마디를 방문한다고 가정합시다.
이때 여행 경로의 하한을 구하면 v1 -> v2 : 14이므로, 이 마디 이후에 확장하여 구한 여행 경로의 하한을 더하면 됩니다.
v2는 v1에서 나왔으므로 다시 v1으로 갈 수 없고,
다른 정점들에 대한 최솟값을 구할 때는 v2로 가는 경로는 포함하지 않습니다.
왜냐하면 v2는 이미 들렸기 때문입니다.

v3 = 7, v3 = 4, v4 = 2, v5 = 4가 되므로, 14 + 7 + 4 + 2 + 4 = 31이 됩니다.

근데 이미 들린 정점에 대한 경로는 포함하지 않는다면서 v3 -> v1은 왜 포함한 거죠?
라는 의문이 들 수 있겠으나, 다시 출발 정점으로 돌아가는 경로는 있어야 하기에 v3 -> v1도 괜찮습니다.
만약 v4 -> v1의 가중치가 정점 v4에서 나오는 간선들 중 가장 작은 값이었다면, v4 -> v1이 선택되었을 것입니다.

v3 -> v1으로 가는 것이 결코 v1 -> v2 -> v3 -> v1의 경로를 뜻하는 것이 아니고, 단순히 하한선을 구하기 위해 선택한 것이라는 것을 명심해야 합니다.

이제 마지막으로 경로 [1, 2, 3]을 포함하고 있는 마디를 방문한다고 가정합시다.
v1 -> v2 = 14, v2 -> v3 = 7입니다.
v3가 선택할 때, v1을 선택하면 안 됩니다.
v4, v5가 선택할 때는 당연히 v2, v3는 포함하면 안 됩니다.
따라서 v3 = 7, v4 = 2, v5 = 4가 되므로, 경로 [1, 2, 3]을 포함하는 마디의 하한선은 14 + 7 + 7 + 2 + 4 = 23가 됩니다.

 

따라서 경로가 완벽하지 않다는 가정하에 총 세 가지 경우로 나눌 수 있습니다.

• 경로의 마지막 노드를 제외한 나머지 노드들
  • 나머지 노드들은 이미 경로(도착지)가 정해져 있기 때문에 도착지를 찾으면 안 된다.
• 경로의 마지막 노드
  • 마지막 노드는 도착지를 찾아야 한다. 이때 이미 경로에 포함된 노드를 도착지로 삼으면 안 된다.
• 경로에 포함되지 않은 노드
  • 출발지(경로의 첫 번째 노드)를 제외하고는 도착지로 삼으면 안 된다.

이러한 방식으로 Bound를 찾으면 됩니다.

 

같은 방법으로 이 마디 이후의 마디를 선택함으로써 여행경로 길이의 하한을 구할 수 있고, 이 하한을 최고 우선 검색에 사용할 수 있습니다.

 

정의 3) 이제 경로를 찾아야 한다.

 

당연한 말이지만 bound를 기준으로 Priority Queue에 넣어야 한다.

이후 제일 유망한 마디를 순서대로 뽑는다.

 

이제 새로운 노드를 생성하고, 기존의 경로를 그대로 복사한다.

반복문을 이용하여 기존의 경로에 노드를 하나씩 추가하면서 최소 길이를 찾는다.

 

이때 새로운 노드의 레벨이 n - 2라면 경로에 마지막 남은 노드와 처음 출발한 노드를 추가하고 경로의 길이를 구한다.

경로의 길이가 지금까지 찾은 최소 길이보다 작으면 이것이 최적 경로!

 

만약 레벨이 n - 2보다 작다면 해당 마디의 bound를 찾은 후에 지금까지 찾은 최소 길이보다 작으면 PQ에 넣는다.

 

이 반복은 PQ가 모두 비어질 때까지 반복한다.

 

끝!

 

---

3. Dynamic Programming (동적 계획법)

 

 

분기 한정법과 비교해서 뭐가 더 어려운지는 잘 모르겠네요..

개인적으로 DP가 더 어려운 것 같습니다...

아무튼 DP를 이용해서 문제를 풀기 위해서는 이 문제가 최적의 원칙이 성립하는지를 알아야 합니다.

 

만약 vk가 최적 경로 상에서 v1 다음에 오는 도시라면, vk에서 v1로 가는 경로 또한 최단 경로여야 합니다.

그래야만 v1 -> vk + vk -> v1 또한 최적이 되기 때문입니다.

 

따라서 최적 원칙이 성립한다는 것을 알 수 있습니다.

 

이제 본격적으로 DP를 이용해서 풀 때 필요한 몇몇 정의를 하도록 하겠습니다.

 

정의 1) V와 A의 관계 및 다른 변수들

 

V는 모든 도시의 집합이고, A는 V의 부분집합입니다.

 

이때 인접 행렬 W가 있어야 합니다.

또한 D[vi][A]는 vi에서 A에 속한 노드만을 이용해 출발 도시(v1)으로 돌아가는 최단 경로의 길이를 뜻합니다.

 

만약에 A = {v3}인데, v3 -> v1으로 가는 경로가 없다고 가정하면,

D[v2][A] = length[v2, v3, v1]이 되는데, v3 -> v1 경로가 없으므로 길이는 무한대가 됩니다.

 

만약 A = {v3, v3}이고, v4 -> v1의 길이가 있다고 가정한다면,

D[v2][A] = minimum(length[v2, v3, v4, v1], length[v2, v4, v3, v1])이 되므로 앞의 path [v2, v3, v4, v1]이 최적의 경로가 됩니다.

 

따라서 최적의 길이는 minimum(W[1][j] + D[vj][A - {v1, vj}])가 됩니다.

(이때 j는 2 이상, n 이하)

(위 식은 v1에서 vj로 가는 길이 + vj에서 v1, vj가 포함되어 있지 않은 정점들을 이용해 v1으로 가는 최적 경로가 된다.)

 

정의 2) 일반화 된 식 (v1, 1이 출발 정점이라고 가정)

 

그러므로 vi가 A에 속하지 않는다고 가정할 때,

D[vi][A] = minimum(W[i][j] + D[vj][A - {vj}])가 됩니다.

풀어서 설명하자면, vi에서 vj로 가는 길이 W[i][j]와

vj에서 v1로 가는 최적 경로(D[vj][A - {vj}])을 더하면

vi에서 v1로 가는 최적의 경로가 나옵니다.

또한 D[vi][{공집합}] = W[i][1]이 됩니다.

 

위의 식 두 개만 이용하면, 손쉽게 DP를 이용하여 TSP 문제를 풀 수 있습니다.

 

추가) A는 어떻게 구할까

 

어차피 순회 문제이기도 하고, 편의를 위해서 출발 정점을 1로 뒀었습니다.

이때 V의 개수가 5개라면, A에는 최대 4개의 정점이 들어가게 됩니다. (A는 V에서 출발 정점을 제외한 집합의 부분 집합)

만약 A를 리스트로 둔다면 그것도 큰 상관은 없지만, 제일 편한 방법은 아마도 비트로 생각하는 것이 좋을 겁니다.

 

4개의 정점이 모두 들어갔다면, A의 비트는 [1, 1, 1, 1]이므로 15가 됩니다.

정점이 2, 4번 정점만 들어갔다면, A의 비트는 [0, 1, 0, 1]이므로 5가 됩니다.

이처럼 비트를 이용해서 특정 정점이 A에 속하는지, 혹은 A에서 특정 정점을 빼는 것도 수월하게 진행할 수 있습니다.

 

비트 연산자를 이용하면 A에 몇 개의 정점이 속하는지도 알 수 있습니다.

 

하지만 이 방법의 단점은 출발 정점이 바뀌면, 비트 연산자를 모조리 갈아엎어야 하고,

출발 정점이 수시로 바뀐다고 가정한다면 오히려 리스트가 더 좋은 방법이 될 수 있습니다.

 

추가) 방금 리스트로 구현하려고 했는데, 모든 A에 대해 반복문을 돌리는 과정이 너무 복잡하네요..

그냥 편하게 출발 정점 1로 두고, 비트 연산자 씁시다 ㅋㅋ;

 

근데 순회 문제니까 출발 정점이 바뀌어도 딱히 상관은 없을 것 같네요

 

 

이상입니다.

끝!

 

 

 

지적 환영합니다.