Traveling Salesman Problem, 외판원 문제. 이번학기에 X줄 타면서 한과제... 대략 3박 4일 걸렸다.. 순수 코딩시간만 해도 머리가 잘 안돌아서 40시간쯤은 했.... 여튼...
위키피디아에서 말하기를..
Q: given a number of cities and the costs of traveling from any city to
any other city, what is the least-cost round-trip route that visits
each city exactly once and then returns to the starting city?
즉, 주어진 도시와 도시들 사이의 거리를 알때, 모든 도시를 한번씩 방문하여 제자리로 돌아 오는 최단 거리의 경로는 어떻게 될까?
두가지 방법으로 문제를 접근해 보았다. 1. Branch and Bound
Branch and Bound
꽤나 간단한 알고리즘 이다. 예를 들어 4개의 도시가 있다고 하고 각각의 거리를 아래의 표와 같이 나타내어보자.
A
B
C
D
A
2
7
9
B
2
5
4
C
7
5
1
D
9
4
1
우선 세도시를 선택한다. A,B,C 라하면. 세도시를 방문하는 법은 한가지 A-B-C 뿐이다. 즉, [A,B] + [B,C] + [C.A] = 2 + 5 + 7 = 14 이다.
여기서 D 도시를 경유하기 위해 최적의 위치를 찾는다. A,B 사이에 A,D,B 를 시도해보고 B,C 사이에 B,D,C 를 시도해보고 C,A 사이에 C,D,A 를 시도한후 거리가 최소가 되는 경우를 선택한다.
즉, B-D-C 에 넣어야 최단 경로가 된다.. 결론적으로 A-B-D-C 의 경로로 여행하게 된다.
이것을 모든 도시를 다 방문 했을때까지 반복 하면 되는것이다.
2. Christofides Algorithm
more..
Definition: (1) A heuristic algorithm to find a near-optimal solution to the traveling salesman problem. Step 1: find a minimum spanning tree T. Step 2: find a perfect matching M among vertices with odd degree. Step 3: combine the edges of M and T to make a multigraph G. Step 4: find an Euler cycle in G by skipping vertices already seen.
저 말대로 실행하면 된다 -_-; 물론... 드럽게 어렵다... (과제시간의 90% 는 이것때문에...)
완성작.
more..
기본적으로 들어 있는 Command 는 Node 와 Node 사이의 distance 를 입력 해놓은 것입니다.
