Survey of Methods of Solving TSP along with its Implementation using Dynamic Programming Approach

Abstract

The Traveling salesperson problem is one of the problem in mathematics and computer science which haddrown attention as it is easy to understand and difficult to solve. In this paper, we survey the various methods/techniques available to solve traveling salesman problem and analyze it to make critical evaluation of their time complexities. An implementation of the traveling salesman problem using dynamic programming is also presented in this paper which generates optimal answer and tested with 25 cities and it executes in reasonable time.