Travel Salesman Problem Algorithm

Travel Salesman Problem:

It is a classical problem in graph theory. It has no closed, analytic and algorithmic solution. This problem is soluble for smaller number(n) of cities but it breaks down as the number of cities grows.

If there are n-cities, the number of different paths among them is (n-1)! The time to examine a single path is proportional to n. So, the total time to search is n!. If n is large then the time taken is also large. This phenomenon is known as combinatorial explosion.

Travel Salesman Problem Algorithm

Problem Formulation: “It involves n-cities with paths connecting the cities. A tour is any path which begins with some starting city, visits each of the other cities exactly once and returns to the starting city”.

Objectives of Travel Salesman Problem:

The Objectives of TSP is to find a minimal distance tour. To explore all such tours requires an exponential amount of time. As long as n is small, this approach works but it breaks down quickly as a number of cities grow. If there are N-cities then the number of different path among them is 1,2, …, (N-1) or (N-1)!

The time to examine a single path is proportional to N. So, the total time required to perform this search is proportional to N!, it requires O(N!) transverse through the graph, an exponential number.