?> Traveling Salesman | Traveling Salesman Problems | Math@TutorCircle.com
Sales Toll Free No: 1-855-666-7446

Traveling Salesman

Top

Traveling Salesman Problems is a method that can be used to find the minimum distance that a traveling salesman has to travel such that he travels all the places at most once. There can be any number of places that we can consider in a traveling salesman problem. The number of paths in this problem is decided on the basis of number of places in consideration, covering all the places. For instance, if the problem has just two places, there can be only one possible path for it. General formula we use to evaluate the total number of paths is given as follows:
(N - 1)! / 2 paths. The Symmetry is maintained in such a way that distance from the source to destination and back from the destination to the source is same.

With increasing value of 'N', the total number of paths in the problem solution Set increases. It is not practically possible for our computer systems to find out all the paths, so it is needed to frame an algorithm that calculates the minimum distance. This value would be much better as compared to nearby values we calculate. Thus we can also say that this method basically involves the optimization of distance to get the most preferable value. Traveling salesman problem is a kind of problem that comes in the category of "NP - complete" problems. It is possible to solve an NP - complete problem by converting the problem into another NP – complete problem. It can also be said as the luck working while finding the solution as you may or may not get the appropriate value i.e. the optimized value in the first go. Traveling salesman problem is important to solve theoretical type of problems for determining the exact and optimized path.

Travelling Salesman Algorithm

Back to Top
Traveling salesman algorithm was introduced in the year 1800. This concept was given by mathematician W.R Hamilton and Thomas Kirkman. Traveling salesman problem algorithm is used to find shortest path. Suppose a salesman lives in a city A and wants to visit city B, C, and D and returns to city A. So task is to find the shortest path between his city A and other cities B , C and D. So it is clear that traveling salesmen problem starts and ends at same Point. Traveling salesmen problem is mainly divided into two parts i.e. symmetric TSP, asymmetric TSP, symmetric TSP. Distance between two cities in forward and reverse direction is same, means distance between A → B and B -> A is same, and in Asymmetric tsp distance between two cites is not equal, means distance between A → B and B → A is not equal.
Let’s take an example of TSP:-



In given diagram there are four cites a, b, c and d, distance between a to b is 10, a to c is 5, a to d is 6, b to d is 9, b to c is 4 and c to d is 8, salesmen starts his journey from city 'a' and then wants to go to city 'b', so there are four possible ways by which he can go, path( 1 ) a->b, path(2) a->c->b , and path(3) a->c->d->b , and path(4) a-> d-> b , but salesman have to choose the shortest path, he calculates the distance between all cities.
Path(1) :- a->b = 10,
Path(2):- a->c->b = 5 + 4 = 9,
Path(3):- a->c->d->b = 5 + 8 + 9 = 22,
Path(4):- a->d->b = 6 + 9 = 15,
We conclude that distance of path (2) is minimum, so salesman will go through this path, this is the concept of TSP. This is all about travelling salesman algorithm.