Step5: Travelling Salesman Problem

***What is Travelling Salesman Problem?

      Given a set of cities and the distance between each possible pair, the Travelling Salesman Problem is to find the best possible way of ‘visiting all the cities exactly once and returning to the starting point.

 

        The idea of the traveling salesman problem (TSP) is to find a tour of a given number 

of cities, visiting each city exactly once and returning to the starting city where the 

length of this tour is minimized. 

*If there is no condition to return to the beginning.  It can still be regarded as a TSP. 

*A route returning to the beginning is known as a Hamiltonian Circuit

*A route not returning to the beginning is known as a Hamiltonian Path

***History of TSP:

                                                 First defined in the 1800s by the Irish mathematician W.R. Hamilton and the British mathematician Thomas Kirkman.

     First mathematical formulation in 1930 by Karl Menger.

     The name Travelling Salesman Problem introduced by an American Hassler Whiteney.

     The origin of TSP lies with Hamilton's Icosian Game, a recreational puzzle based on finding a Hamiltonian cycle.

     Richard M. Karp showed the NP-Completeness of the problem in 1972

***Applications of TSP:

   •Even in its purest form the TSP, has several applications such as planning, logistics, and the manufacture of microchips.

   •Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing.

   •The concept city represents, for example, customers, soldering points, or DNA fragments

   •The concept distance represents travelling times or cost, or a similarity measure between DNA fragments.

   •Often used as a benchmark for optimization techniques.

***Different Forms of the Problem:

        There are many different variations of the traveling salesman problem.

#Reference: