Travel Salesman Problem Algorithm

Travel Salesman Problem:

It is a classical problem in graph theory. It has no closed, analytic, or algorithmic solution. This problem is soluble for a 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.

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 Objective of TSP is to find a minimal-distance tour. Exploring all such tours requires an exponential amount of time. As long as n is small, this approach works but it breaks down quickly as several cities grow. If there are N-cities then the number of different paths 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.