외판원 문제의 다항시간 알고리즘 (A Polynomial Time Algorithm of a Traveling Salesman Problem)

서지정보

· 발행기관 : 한국컴퓨터정보학회
· 수록지 정보 : 한국컴퓨터정보학회논문지 / 18권 / 12호 / 75 ~ 82페이지
· 저자명 : 이상운

초록

본 논문은 NP-완전으로 다항시간 알고리즘이 존재하지 않는 대규모 외판원 문제의 최적 해를 O(n²)의 다항시간으로 구하는 알고리즘을 제안하였다. 대규모 외판원 문제에서 가장 큰 문제는 처리될 데이터가 n ×n으로n 커질수록 기하급수적으로 증가한다. 본 논문에서는 먼저, 데이터의 양을 약 n/2기로 축소시킨다. 다음으로 임의의 정점에서 시작하여 양방향으로 경로를 탐색하는 방법을 적용하였다. 제안된 알고리즘을 26개의 유럽 도시들을방문하는 TSP-1과 46개 미국 도시들을 방문하는 TSP-2에 적용한 결과 모두 최적 해를 O(n²) 수행 복잡도로 빠르게 구하는데 성공하였다. 따라서 제안된 알고리즘은 TSP의 일반화된 알고리즘으로 적용할 수 있을 것이다.

영어초록

This paper proposes a O(n²) polynomial time algorithm to obtain optimal solution for Traveling Salesman problem that is a NP-complete because polynomial time algorithm has been not known yet. The biggest problem in a large-scale Traveling Salesman problem is the fact that the amount of data to be processed is n ×n, and thus as n increases, the data increases by multifold.
Therefore, this paper proposes a methodology by which the data amount is first reduced to approximately n/2. Then, it seeks a bi-directional route at a random point. The proposed algorithm has proved to be successful in obtaining the optimal solutions with O(n²) time complexity when applied to TSP-1 with 26 European cities and TSP-2 with 46 cities of the USA. It could therefore be applied as a generalized algorithm for TSP.

참고자료

· 없음