Traveling Salesman Problem -A traveling salesman starts at city 1, travels to cities 2, . . . , n ?1 in any order that the salesman chooses, and then ends his trip in city n. Let us denote (i, j) to be the distance from city to city j. The goal of the Traveling Salesman Problem is to find the minimum total distance possible for the traveling salesman to travel. There are no restrictions on the possible distances (i, j) between each of the cities other than the requirement that each (i, j) is a positive integer and (i, j) = (j, i) [1,3,4].

We give a simple proof that no deterministic Problem in o(2 n ) time:

For any nonempty subset S {2, . . . , n} and for any city i S, let us define (S, i) to be the length of the shortest path that starts at city 1, visits all cities in the set Salesman Problem is equivalent to the problem of computing ({2, . . . , n}, n). Clearly, ({i}, i) = (1, i) and when This recursive formula cannot be simplified, so the fastest way to compute ({2, . . . , n}, n) is to apply this recursive formula to ({2, . . . , n}, n). Since this subsets S {2, . . . , n} and each i S, we obtain a lower Traveling Salesman Problem.

This lower bound is confirmed by the fact that the fastest known deterministic and exact algorithm which solves the Traveling Salesman Problem was first time of (2 ) [2,4].
		
		
			

Author : 2712 Willow Glen Drive, Baltimore, Maryland 21209.