Travelling Salesman Problem


The traveling salesman problem (TSP) is a popular mathematics problem that asks for the most efficient trajectory possible given a set of points and distances that must all be visited.

In computer science, the problem can be applied to the most efficient route for data to travel between various nodes. 

In terms of input, the problem takes a list of physical locations or system nodes, along with distance information. Algorithms and equations work on the process of identifying the most efficient paths possible between the locations. Computer programs can do this through the process of elimination or through a process called heuristics that provides probability outcomes for this type of equation.

In the early days of computers, the traveling salesman problem was one example of the many tasks that computers could do more efficiently than humans. A simple computer program written in almost any programming language can provide excellent and actual results for solving the traveling salesman problem with any reasonable amount of complexity.

In modern IT, the equation itself has applications in identifying network or hardware optimization methods. For example, in the vastly complex global Internet, the traveling salesman problem can be used to work out the most efficient trajectories for data packets being routed anywhere in the system. The same holds true for private networks.

Travelling Salesman Problem (TSP): Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.

Note the difference between Hamiltonian Cycle and TSP. The Hamiltoninan cycle problem is to find if there exist a tour that visits every city exactly once. Here we know that Hamiltonian Tour exists (because the graph is complete) and in fact many such tours exist, the problem is to find a minimum weight Hamiltonian Cycle.


For example, consider the above graph. A TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80.

The problem is a famous NP hard problem. There is no polynomial time know solution for this problem.

Following are different solutions for the traveling salesman problem.


Naive Solution:
1) Consider city 1 as the starting and ending point.
2) Generate all (n-1)! Permutations of cities.
3) Calculate cost of every permutation and keep track of minimum cost permutation.
4) Return the permutation with minimum cost.

Time Complexity: ?(n!)

0 comments:

Post a Comment