 |
 |
 |
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