Traveling Salesman Problem – 개요 (1/2)

Presentation on theme: "Traveling Salesman Problem – 개요 (1/2)"— Presentation transcript:

1 Traveling Salesman Problem – 개요 (1/2)
외판원이 자신의 집이 위치하고 있는 도시에서 출발하여 다른 도시들을 “각각 한번씩만 방문”하고, “다시 자기 도시로 돌아오는” 가장 짧은 일주여행경로(tour)를 결정하는 문제이다. 일반적으로, 이 문제는 음이 아닌 가중치가 있는, 방향성 그래프를 대상으로 한다. 여러 개의 일주여행경로 중에서 길이가 최소가 되는 경로가 최적일주여행경로(optimal tour)가 된다.

2 Traveling Salesman Problem – 개요 (2/2)
무작정 알고리즘: 가능한 모든 일주여행경로를 다 고려한 후, 그 중에서 가장 짧은 일주여행경로를 선택한다.  Complete Graph에서 가능한 일주여행경로의 총 개수는 (n – 1)!이다. n = 20일 때, 무작정 알고리즘: 각 일주여행경로의 길이를 계산하는데 걸리는 시간은 1sec이라고 할 때, (20 - 1)! = 19!sec = 3857년이 걸린다. DP 기반 알고리즘 (P.128 참조): 기본동작을 수행하는데 걸리는 시간을 1sec이라고 할 때, T(20) = (20 - 1)(20 - 2)220-3sec = 45초가 걸리고, M(20) = 20  220 = 20,971,520의 배열 슬롯이 필요하다. n = 40이라면? DP 또한 6년 이상 걸린다. Dynamic Programming 방법 또한 실용적인 해결책이 아니다.

3 TSP – BnB 기반 접근법 – Running Example
보기: 다음 인접행렬로 표현된 그래프를 살펴보시오. 완전 연결그래프의 인접행렬 표현 최적 일주여행경로 14 v1 v2 4 8 11 10 7 5 7 7 v4 v3 9 20 18 16 2 7 17 4 v5

4 TSP – BnB 기반 상태공간트리 구축 (1/2)
각 노드는 출발노드로부터의 일주여행경로를 나타냄 루트노드의 여행경로는 [1]이 되고, 루트노드에서 뻗어 나가는 수준 1에 있는 여행경로는 각각 [1,2], [1,3], …, [1,5]가 된다. 노드 [1,2]에서 뻗어 나가는 수준 2에 있는 노드들의 여행경로는 각각 [1,2,3], [1,2,4], [1,2,5]가 된다. 이런 식으로 뻗어 나가서 단말노드에 도달하게 되면 완전한 일주여행경로를 가지게 된다. 최적일주여행경로를 구하는 방법: 단말노드에 있는 일주여행경로를 모두 검사하여 그 중에서 가장 비용이 낮은 일주여행경로를 찾으면 된다.

5 TSP – BnB 기반 상태공간트리 구축 (2/2)
구축된 상태공간 트리의 일부 예 노드의 수 = 5 참고: 각 노드에 저장되어 있는 노드가 4개가 되면 더 이상 뻗어 나갈 필요가 없다. 왜냐하면, 5번째 노드는 더 이상 뻗어 나가지 않고도 알 수 있기 때문이다.

6 TSP – BnB-Best First Search 개요 (1/6)
분기한정 가지치기로 최고우선 검색을 사용하기 위해서 각 노드의 한계치(bound)를 구할 수 있어야 한다. 이 문제에서는 주어진 노드에서 뻗어 나가서 얻을 수 있는 여행경로 길이의 하한(최소치, lower bound)을 구하여 한계치로 한다. 각 노드를 방문할 때 그 노드가 유망 (Promising)할 조건 “한계치” < “최소여행경로의 길이” 반대로, 최소 여행경로의 길이가 한계치보다 큰 경우는 Pruning을 수행하여 검색 공간을 줄인다.

7 TSP – BnB-Best First Search 개요 (2/6)
루트노드의 하한 구하기 전략: 어떤 일주여행경로라도 각 정점을 최소한 한번은 방문 후 떠나야 하므로, 각 정점을 떠나는 이음선 중 최소값의 합이 하한이 된다. v1  min(14, 4, 10, 20) = 4 v2  min(14, 7, 8, 7) = 7 v3  min(4, 5, 7, 16) = 4 v4  min(11, 7, 9, 2) = 2 v5  min(18, 7, 17, 4) = 4 따라서, 일주여행경로 길이의 하한은 21(= )이 된다. 주의할 점은 “이 길이의 일주여행경로가 있다는 말이 아니라, 이보다 더 짧은 일주여행경로가 있을 수 없다”는 것이다. 그래서 하한(lower bound)이라는 말을 사용한다.

8 TSP – BnB-Best First Search 개요 (3/6)
루트노드가 아닌 다른 노드의 한계치 구하기 주어진 총 정점: [v1, …, vk, vk+1, …, vn] [v1, …, vk] 여행경로를 가진 노드의 한계치 (bound) = [v1, …, vk] 경로 상의 총 거리a + vk 에서 V - [v1, …, vk] 에 속한 정점으로 가는 이음선의 길이들 중에서 최소치b vk+1 에서 V - [v2, …, vk, vk+1] 에 속한 정점으로 가는 이음선의 길이들 중에서 최소치c + vk+2 에서 V - [v2, …, vk, vk+2] 에 속한 정점으로 가는 이음선의 길이들 중에서 최소치c + … + vn 에서 V - [v2, …, vk, vn] 에 속한 정점으로 가는 이음선의 길이들 중에서 최소치c

9 TSP – BnB-Best First Search 개요 (4/6)
노드 [1, 2]를 선택한 경우의 하한 구하기 근거: 이미 v2를 선택하였음을 의미하므로, v1  v2의 비용은 이음선의 가중치인 14가 된다. 나머지는 앞서와 동일한 방법으로 구한다. v1  v2 = 14a v2  min(7, 8, 7) = 7b v3  min(4, 7, 16) = 4c v4  min(11, 9, 2) = 2c v5  min(18, 17, 4) = 4c 따라서, [1, 2]를 포함하는 노드에서 확장하여 구한 일주여행경로 길이의 하한은 31(= )가 된다. bound=21 bound=31

10 TSP – BnB-Best First Search 개요 (5/6)
노드 [1, 2, 3]를 선택한 경우의 하한 구하기 근거: 이미 v2와 v3를 선택하였음을 의미하므로, v1  v2  v3의 비용은 21(=14+7)이 된다. 나머지는 앞서와 동일한 방법으로 구한다. v1  v2  v3 = 21a v3  min(7, 16) = 7b v4  min(11, 2) = 2c v5  min(18, 4) = 4c 따라서, [1, 2, 3]을 포함하는 노드에서 확장하여 구한 일주여행경로 길이의 하한은 34(= )이 된다. bound=21 bound=31 bound=34

11 TSP – BnB-Best First Search 개요 (6/6)
한계치(lower bound)와 최소여행경로(Min Length)의 비교 최소여행경로(Min Length) 의 초기값은 로 놓는다. 완전한 여행경로를 처음 얻을 때 까지 방문하는 모든 노드는 한계치가 무조건 의 최소여행경로의 길이 (Min Length= ) 보다 작으므로 그러한 모든 노드는 유망하다. 완전한 여행경로를 얻은 후에는 가 아닌 최소여행경로의 길이(Min Length)를 얻게 되므로, 이후 방문하는 노드의 한계치가 그러한 최소여행경로의 길이(Min Length)보다 크면 Pruning의 효과가 발생한다.

12 BnB – Best FS 기반 상태공간트리 구축 (1/5)
루트노드 방문 (Lower Bound = 21, minLen = ) 기본적으로 너비우선검색 (Breadth-first search) 노드 [1, 2] (LB = 31) 노드 [1, 3] (LB = 22) 노드 [1, 4] (LB = 30) 노드 [1, 5] (LB = 42) Best First Search에 따라 한계 값이 가장 작은 [1, 3]을 방문한다.

13 BnB – Best FS 기반 상태공간트리 구축 (3/5)
노드 [1, 3, 2] (LB = 22) 노드 [1, 3, 4] (LB = 27) 노드 [1, 3, 5] (LB = 39) BFS에 따라 한계 값이 가장 작은 [1, 3, 2]를 방문한다.

14 BnB – Best FS 기반 상태공간트리 구축 (4/5)
노드 [1, 3, 2, 4] 단말노드 이므로 일주여행경로의 길이를 계산한다. 이 길이가 37이고, 37 < 이므로, minLen = 37이 된다. [1, 5]와 [1, 3, 5]는 한계값 (각각 42, 39)이 minLen 보다 크므로 Pruning 할 수 있다.

15 BnB – Best FS 기반 상태공간트리 구축 (4/5)
노드 [1, 3, 2, 5] 방문 결과 minLen = 31이 된다. [1, 2]를 가지치기 할 수 있다. 다음으로, [1, 3, 4]를 선택한다. 상기 과정을 계속 반복하면, minLen = 30을 최소 일주 경로 길이로 구할 수 있다.

16 BnB – Best FS 기반 상태공간트리 구축 (1/5)
최종 결과 트리 (p.244)

17 TSP – BFS 기반 상태공간트리 구축 (5/5)
원래 상태공간 트리의 전체 노드 개수는 41개가 될 수 있다. ( x x 3 x 2 = 41) 반면에, BnB-BFS에서 구성한 상태공간트리를 보면 노드 개수가 17개이다. 결국, 효과적인 Pruning이 이뤄짐을 알 수 있다.

18 TSP의 BnB-BFS 기반 알고리즘 자세한 알고리즘은 생략 (교재 p. 247 참조)
아직도 알고리즘의 시간복잡도는 지수적 시간에 거의 가깝다! 증명 생략 하지만, 대체로 DP 보다 빠른 시간 내에 답을 구할 수 있음 BnB-BFS를 사용해도 여전히 n = 40 정도가 되면 문제를 풀 수 없는 것과 다름없다고 할 수 있다. 다른 방법이 있을까? 근사(approximation) 알고리즘: 최적의 해답을 준다는 보장은 없지만, 무리 없이 최적에 가까운 해답을 주는 알고리즘 (대학원)

19 TSP를 해결하는 여러 근사알고리즘 논문