Travelling Salesman Problem

The Travelling Salesman Problem is the name given to an algorithmic problem which poses the question“Given the names of multiple cities and the distances between these cities, what is the shortest route that passes through all the points, and returns back to the original position?”. Essentially, this is a combinatorial optimization problem (finding an optimal result from a finite list of objects)  and is classified as an NP-Hard problem.

This kind of problem has a wide variety of applications outside route planning. The cities can represent users or soldering points, and distance can be likened to other values such as time and cost. Therefore, this problem is very important to computer scientists due to its appearance in various computational situations.

The travelling salesman problem can be depicted as an undirected weighted graph. The vertices represent cities and the values between indicate distance. TSP is a minimization problem beginning and ending at a certain vertex and only visiting each vertex once.

 

There exists an optimal solution to this problem, identified as the Held-Karp algorithm. However, it is bounded by a time complexity which means it takes an exponential amount of time to obtain the solution. For this very reason, brute force algorithms are also extremely inefficient.

There are many other solutions which exist, however, they compromise precision and accuracy for speed of solution. The most accurate solution which exists to date is the 7/5-approximation ( an improvement to the Christofides 3/2 algorithm).  Looking at the problem from a practical standpoint it is easier to find implementations of the Christofides algorithm, as the 7/5 algorithm is very complex.

This problem is continually investigated, as computer scientists strive to find more and more accurate solutions that do not take exponential time by the use of advanced heuristics and exact algorithms.