Traveling Salesman Problem(TSP) - 최고 우선 검색 기반 한정 분기(Branch and Bound)

Traveling Salesman Problem(TSP)

최고 우선 검색 기반 한정 분기(Branch and Bound) 

---

서론

Traveling Salesman Problem(TSP) : 외판원이 자신의 집이 위치하고 있는 도시에서 출발하여 다른 도시들을 "각각 한번씩만 방문"하고, "다시 자기 도시로 돌아오는" 가장 짧은 일주여행경로(tour)를 결정하는 문제

 

최고 우선 검색 기반 한정 분기(Branch and Bound) 전략

- 각 노드는 출발노드로부터의 일주여행경로를 나타냄

- 단말노드에 있는 일주여행경로를 모두 검사하여 그 중에서 가장 비용이 낮은 일주여행경로를 찾으면 된다. (무작정 알고리즘: Brute Force 전략)

- 분기한정 가지치기로 최고우선 검색을 사용하기 위해서 각 노드의 한계치(bound)를 구할 수 있어야 한다.

- 이 문제에서는 주어진 노드에서 뻗어 나가서 얻을 수 있는 여행경로 길이의 하한(최소치, lower bound)을 구하여 한계치로 한다.

- 각 노드를 방문할 때 그 노드가 유망 (Promising)할 조건 : 한계치 < (현재까지 알아낸) 최소여행경로 길이

 

최고 우선 검색 기반 한정 분기(Branch and Bound) 순서

1. 최소여행경로(Min Length) 의 초기값은 ∞로 놓는다.

2. 완전한 여행경로를 처음 얻을 때 까지 방문하는 모든 노드는 한계치가 무조건 ∞로 설정된 최소여행경로의 길이 (Min Length=∞) 보다 작으므로 그러한 모든 노드는 유망하다.

3. 완전한 여행경로를 하나라도 얻은 후에는 ∞가 아닌 최소여행경로의 길이(Min Length)를 얻게 되므로, 이후 방문하는 노드의 한계치가 그러한 최소여행경로의 길이(Min Length)보다 크면 Pruning의 효과가 발생한다.

---

본론

아래 주어진 유향 가중치 그래프 및 인접 행렬에서 TSP 문제의 해를 최고 우선 검색을 사용한 한정 분기(Branch and Bound)로 산출할 때 상태 공간 트리, 상태 공간 트리 내 방문한 전체 노드 수, TSP 문제의 최적 해 (즉, 최적 경로) 제시하기

---

1. 루트노드의 한계치(Bound, 하한) 구하기

- v1 -> min(5, 8) = 5

- v2 -> min(4, 4) = 4

- v3 -> min(2, 5) = 2

- v4 -> min(7) = 7

- v5 -> min(1) = 1

- v6 -> min(6, 2) = 2

- v7 -> min(3, 8) = 3

- v8 -> min(5, 4) = 4

 

따라서, 일주여행경로 길이의 하한은 28(= 5 + 4 + 2 + 7 + 1 + 2 + 3 + 4)이 된다.

주의할 점은 “이 길이의 일주여행경로가 있다는 말이 아니라, 이론적으로 이보다 더 짧은 일주여행경로가 있을 수 없다”는 것이다. 그래서 하한(lower bound)이라는 말을 사용한다.

 

2. 레벨 1에 대한 각 노드

 

 

3. Best-First Search(BFS)에 따라 한계 값이 가장 작은 [1, 2]을 우선순위 큐에서 가져온다 (dequeue).

4. 레벨 [1, 2]에 대한 각 노드

 

5. Best-First Search(BFS)에 따라 한계 값이 가장 작은 [1, 2, 3]을 우선순위 큐에서 가져온다 (dequeue).

6. 레벨 [1, 2, 3]에 대한 각 노드

 

7. Best-First Search(BFS)에 따라 한계 값이 가장 작은 [1, 2, 3, 4]을 우선순위 큐에서 가져온다 (dequeue).

8. 레벨 [1, 2, 3, 4]에 대한 각 노드

 

9. Best-First Search(BFS)에 따라 한계 값이 가장 작은 [1, 2, 3, 4, 8]을 우선순위 큐에서 가져온다 (dequeue).

10. 레벨 [1, 2, 3, 4, 8]에 대한 각 노드

 

11. Best-First Search(BFS)에 따라 한계 값이 가장 작은 [1, 2, 3, 4, 8]을 우선순위 큐에서 가져온다 (dequeue).

12. 레벨 [1, 2, 3, 4, 8]에 대한 각 노드

---

상태 공간 트리 내 방문한 전체 노드 수 제시 : 11

TSP 문제의 최적 해 (즉, 최적 경로) 제시 : 1 -> 2-> 3-> 4-> 8 -> 7-> 6-> 5-> 1

 

죄송합니다.. 강의자료만으로 bound 하한 구하는 방법에 대해 이해를 잘 못하겠습니다.