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

- First, find out all (
n-1)! Possible solutions, wherenis the number of cities.- Next, determine the minimum cost by finding out the cost of everyone of these (
n-1)! Solutions.- 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.

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.

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

- Initialization

c← 0- Cost ← 0
- visits ← 0
e= 1 /* pointer of the visited city */

- For 1 ≤
r≤nDo {

Choose pointer

jwith

- minimum =
c(e,j) = min{c(e,k); visits (k) = 0 and 1 ≤k≤n}- cost ← cost + minimum - cost
e=jC(r) ← j

C(n) = 1- cost = cost +
c(e, 1)