SKEDSOFT

TRAVELING-SALESMAN PROBLEM: The traveling-salesman problem, stated as follows :
‘‘A salesman is required to visit a number of cities during a trip. Given the distances between the cities, in what order should he travel so as to visit every city precisely once and return home, with the minimum mileage traveled ?’’Representing the cities by vertices and the roads between them by edges. We get a graph. In this graph, with every edge ei there is associated a real number (the distance in miles, say), w(ei). Such a graph is called a weighted graph ; w(ei) being the weight of edge ei. (i.e., A traveling salesman wants to visit each of n cities exactly once and return to his starting point) if each of the cities has a road to very other city, we have a complete weighted grap.

For example, suppose that the salesman wants to visit five cities, namely, A, B, C, D and E (see Figure). In which order should he visit these cities to travel the minimum total distance ? To solve this problem we can assume the salesman starts in A (since this must be part of the circuit) and examine all possible ways for him to visit the other four cities and then return to A (starting elsewhere will produce the same circuits). There are a total of 24 such circuits, but since we travel the same distance when we travel a circuit in reverse order, we need only consider 12 different circuits to find the minimum total distance he must travel. We list these 12 different circuits and the total distance traveled for each circuit. As can be seen from the list, the minimum total distance of 458 miles is traveled using the circuit A – B – E – D – C – A (or its reverse).

The graph showing the distance between five cities (A, B, C, D, E)
The traveling salesman problem asks for the circuit of minimum total weight in a weighted, complete, undirected graph that visits each vertex exactly once and returns to its starting point. This is equivalent to asking for a Hamilton circuit with minimum total weight in the complete graph, since each vertex is visited exactly once in the circuit.
The most straight forward way to solve an instance of the traveling salesman problem is to examine all possible Hamilton circuits and select one of minimum total length. How many circuits do we have to examine to solve the problem if there are n vertices in the graph ? Once a starting point is chosen, there are (n – 1) ! different Hamilton circuits to examine, since there are n – 1 choices for the second vertex, n – 2 choices for the third vertex, and so on. Since a Hamilton circuit can be traveled in reverse order, we need only examine circuits to find our answer.

Note that grows extremely rapidly. Trying to solve a traveling salesman problem in this way when there are only a few dozen vertices is impractical. For example, with 25 vertices, a total of 24!/2 (approximately 3.1 × 1023) different Hamilton circuits would have to be considered. If it took just one nanosecond (10^{– 9} second) to examine each Hamilton circuit, a total of approximately ten million year would be required to find a minimum-length Hamilton circuit in this graph by exhaustive search techniques.