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.