*The T.S.P. *Example.

**EXAMPLE: **Heuristic algorithm for the *Traveling
Salesman Problem (T.S.P) *.

This is one of the most known problems ,and is often called as
a *difficult *problem.A salesman must visit *n*
cities, passing through each city only once,beginning from one of
them which is considered as his base,and returning to it.The cost
of the transportation among the cities (whichever combination
possible) is given.The program of the journey is requested,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 let
city 1 be the city-base of the salesman.Also let's assume that **c****(i,j)**** **is the visiting cost from **i
**to **j**.There can be **c****(i,j)****<>c****(j,i)****.**Apparently all the possible
solutions are *(n-1)!*.Someone could probably
determine them systematically,find the cost for each and everyone
of these solutions and finally keep the one with the minimum
cost.These requires at least *(n-1)!* steps.

If for example there were 21 cities the steps required are *(n-1)!=(21-1)!=20!
*steps.If every step required a *msec *we
would need about **770 centuries **of
calculations.Apparently,the exhausting examination of all
possible solutions is out of the question.Since we are not aware
of any other quick algorithm that finds a best solution we will
use a heuristic algorithm. According to this algorithm whenever
the salesman is in town *i* he chooses as his next
city,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.There is also a simple rule just in case more
than one cities give the minimum cost,for example in such a case
the city with the smaller *k *will be chosen.This is
a greedy algorithm which selects in every step the cheapest visit
and does not care whether this will lead to a wrong result or
not.

Click to see a** ****PSEUDOCODE**** **for the *T.S.P. *algorithm.

HTML PAGE DIRECTOR :Papaioannou
Panagiotis