This is one of the most well known difficult problems of time. A salesperson must visit n cities, passing through each city only once, beginning from one of the city that is considered as a base or starting city and returns to it. The cost of the transportation among the cities is given. The problem is to find the order of minimum cost route that is, the order of visiting the cities in such a way that the cost is the minimum.
 

Let's number the cities from 1 to n and city 1 be the start-city of the salesperson. Also let's assume that c(i, j) is the visiting cost from any city i to any other city j.  Here is the systematic way of solving this problem:

Algorithm TSP

1. First, find out all (n -1)! Possible solutions, where n is the number of cities.
2. Next, determine the minimum cost by finding out the cost of everyone of these (n -1)! Solutions.
3. Finally, keep the one with the minimum cost.

Clearly, this requires at least (n-1)! Steps.

If we try to determine the solution of this problem systematically, we would ended up with (n - 1)! possible solutions. For example if there were 21 cities the steps required are (n - 1)! = (21 - 1)! = 20! steps. If each step required a 1msec we would need about 770 centuries to calculate the minimum cost route. (My life is too short for this crap.) Clearly we cannot examine all possible solutions for minimum cost.

Outline of TSP Heuristic

Whenever the salesman is in town i he chooses as his next city i.e., the city j for which the c(i, j) cost, is the minimum among all c(i, k) costs, where k are the pointers of the city the salesman has not visited yet. In case more than one cities give the minimum cost, the city with the smaller k will be chosen. This greedy algorithm selects the cheapest visit in every step and does not care whether this will lead to a wrong result or not.

Heuristic

Input

• Number of cities n
• Cost of traveling between the cities.
• c (i, j)   i, j = 1, . . , n.
• Start with city 1

Output

• Vector of cities and total cost.

 

Main Steps

1. Initialization
• c← 0
• Cost ← 0
• visits ←  0
• e = 1     /* pointer of the visited city */
   
2. For 1 ≤ r ≤  n
Do {
Choose pointer j with
• minimum = c (e, j) = min{c (e, k); visits (k) = 0 and 1 ≤  k  ≤  n }
• cost ← cost + minimum - cost
• e = j
3. C(r) ← j
• C(n) = 1
• cost = cost + c (e, 1)