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)!이다.

3 TSP – 무작정 vs. DP n = 20일 때, n = 40이라면? DP 또한 6년 이상 걸린다.
무작정 알고리즘: 각 일주여행경로의 길이를 계산하는데 걸리는 시간은 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 방법 또한 실용적인 해결책인 아니다.

4 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

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

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

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

8 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)이라는 말을 사용한다.

9 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

10 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

11 TSP – BnB-Best First Search 개요 (5/6)
노드 [1, 2, 3]를 선택한 경우의 하한 구하기 근거: 이미 v2와 v3를 선택하였음을 의미하므로, v1  v2  v3의 비용은 21(=14+7)이 된다. 나머지는 앞서와 동일한 방법으로 구한다. v1  v2 = 14a v2  v3 = 7a 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

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

13 TSP – BFS 기반 상태공간트리 구축 (1/5)
루트노드 구성 (bound = 21, minLen = ) 노드 [1, 2] (LB = 31) 노드 [1, 3] (LB = 22) 노드 [1, 4] (LB = 30) 노드 [1, 5] (LB = 42) BFS에 따라 한계 값이 가장 작은 [1, 3]을 방문한다.

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

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

16 TSP – BFS 기반 상태공간트리 구축 (4/5)
노드 [1, 3, 2, 5] 방문 결과 minLen = 31이 된다. [1, 2]를 가지치기 할 수 있다. 다음으로, [1, 3, 4]를 선택한다. 상기 과정을 계속 반복하면, 왼편 그림의 Length = 30을 최소 길이로 구할 수 있다.

17 TSP – BFS 기반 상태공간트리 구축 (1/5)

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

19 TSP – BFS 기반 알고리즘 자세한 알고리즘은 생략 (교재 p. 247 참조)
아직도 알고리즘의 시간복잡도는 지수적 시간에 거의 가깝다! 증명 생략 다시 말해서 n = 40이 되면 문제를 풀 수 없는 것과 다름없다고 할 수 있다. 다른 방법이 있을까? 근사(approximation) 알고리즘: 최적의 해답을 준다는 보장은 없지만, 무리 없이 최적에 가까운 해답을 주는 알고리즘이다 (수업 범위 외)