Traveling  Salesman  Problem

Traveling salesman problem (TSP) 또는 traveling salesperson problem 은 이산 (discrete) 또는 조합최적화 (Combinatorial Optimization)) 에 속하는 문제이다. 이 문제는 풀기가 어려운 계산복잡도이론 (Computational Complexity Theory) 의 문제부류 중에서 전형적인 예로 사용된다. 많은 수의 도시가 있고, 한 도시에서 다른 도시로의 여행 경비를 알고있을때, 각 도시를 한번만 방문하고 출발한 도시로 되돌아 오는데 가장 비용이 적게드는 여행경로는 무엇인가?

그래프이론 (Graph Theory) 에서의 동등한 형식은 : 완전 가중치 그래프 (complete weighted graph : 도시들을 나타내는 vertices, 도로를 나타내는 edges, 여행경비나 도로의 거리를 나타내는 weights) 가 주어졌을때, 가장 적은 weight 를 가지는 해밀턴의 사이클 (Hamiltonian Cycle) 을 찾는것이다. ...... (Wikipedia : Traveling salesman problem)

잘 알려져 있는 세일즈맨의 여행 문제를 한 번 살펴보기로 하자. 우리의 세일즈맨 윌리 로먼 (Willy Loman) 은 판매망과 여행 예산, 그리고 비행기 요금의 팜플렛을 가지고 있다. 그는 보스턴에서 출발해 그의 예산의 한도 내에서 그림 1 에 나와 있는 9 군데의 도시를 두루 여행한 뒤 다시 보스턴으로 돌아가야 한다. 그가 당신에게 어떤 경로를 택해야 할 지 알아내 달라고 요구한다. 그에게 주어진 예산이 많다면 당신이 해야 할 일은 어렵지 않을 것이다. 하지만 허용된 예산이 적을 경우, 아주 힘들여 작업을 해야만 할 것이다. 예산의 한도를 넘기지 않는 것조차 불가능할 수도 있다. 둘 중 어떤 상황이든, 당신은 그 도시들에 대해 가능한 모든 순서를 고려해야 할 것이다. 이처럼 몇 안 되는 도시들을 고려하는 데에만도 실상 가능한 경로의 수는 대략 10 만 가지에 달한다! (9! = 362880)

순서의 가짓수는 계승 (! 기호로 표현되는) 으로 알려져 있다. 계승 (factorial) 은 빠르게 아주 큰 수에 이른다. 4 의 계승, 즉 4! = 4 × 3 × 2 × 1 = 24 이며, 5! = 5 × 4! 즉 5 × 24 = 120 이 되고, 6! = 720 이 되는 식으로 계속 이어진다. 물론, 컴퓨터는 많은 가능성을 다루는 데 훌륭한 능력을 발휘하지만, 급격히 증가하는 가능성의 수가 모든 계산 자원의 용량을 압도한다. Stephen Cook 은 이러한 점을 지적한다. ...... (Dennis Shasha 1995)

Travelling salesman problem (TSP) 은 제한된 수의 도시들 간의 여행을 하는데, 모든 도시를 방문하면서 가장 여행 비용이 싸게 들도록하고 출발지점으로 되돌아 오는 문제이다. (도시 X 에서 Y 까지의 여행 경비는 Y 에서 X 까지 여행경비와 같다는 의미에서 여행 비용은 대칭적이다. 모든 도시를 방문하는 길은 방문하는 도시의 순서로 표시한다). finite complete graph 의 가장자리 (edge) 에 정수의 가중치를 두어 각각의 비용을 표시한다. 목적은 최소의 전체 가중치 (minimum total weight) 를 가지는 hamiltonian cycle (모든 vertices를 통과 하는 cycle) 을 찾는 것이다. 그 cycle 은 여행경로로 보통 표시된다.

TSP와 관련된 수학문제는 아일랜드의 수학자 William Rowan Hamilton 와 영국 수학자 Thomas Penyngton Kirkman 에 의해 1800년대에 다루어졌다. 그들의 업적에 대해서는 Graph Theory 1736-1936 에 나와있다. .... TSP의 일반적 형태에 대한 연구는 Karl Menger 에 의해 1930년대에 처음 연구되기 시작했다. 그 문제는 나중에 프린스턴에서  Hassler Whitney 와 Merrill Flood 에 의해 더욱 발전되었다. 그들의 TSP의 연구의 진척에 관해서는 ``On the history of combinatorial optimization (till 1960)'' 에서 자세히 다루고 있다. .............. (TSP 의 해결 : 프린스턴 대학)

term :

순회판매원 문제 (Traveling Salesman Problem)    비결정 완전 (NP-complete)   조합최적화 (Combinatorial Optimization)   계산복잡도이론 (Computational Complexity Theory)   그래프이론 (Graph Theory)    해밀턴의 사이클 (Hamiltonian Cycle)   최단경로 찾기 문제 (Shortest Path Finding Problem)   Stephen Cook

site :

TSP 의 해결 : 프린스턴 대학

       역사,  milestone(해결 방법의 역사),  관련 도서 목록, 미국의 13,509 개의 도시 연결 TSP 예, .......

AI Topics : Traveling Salesperson and NP-complete Problems

Travelling Salesman Problem : Kohonen 의 신경망 이론을 이용한 java applet 구현

TSP using Genetic Algorithm  : LaLena

TSP java applet : Tufts 대학

TSP 해결을 위한 알고리즘 : CMU

TSPBIB Home Page : TSP 와 관련문제에 대해 인터넷에서 이용할 수 있는 paper, source code, technical report 등등의 리스트

paper :

스티븐 쿡과 레오니드 레빈 : Dennis Shasha

해밀턴 사이클과 판매원 방문 문제 (Hamiltonian Cycles and the Travelling Salesperson Problem)   최단경로 알고리즘 (Shortest-Path Algorithm) : Richard Johnsonbaugh

강화학습 기법을 이용한 TSP 의 해법 (A learning based algorithm for Traveling Salesman Problem) : 임준묵, 강진규, 길본일수, 임재국, 대한산업공학회, 2002