본문 바로가기
  • Home

A Polynomial Time Algorithm of a Traveling Salesman Problem

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2013, 18(12), pp.75-82
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

ABSTRACT

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.

Citation status

* References for papers published after 2022 are currently being built.