TRAVELLING SALESMAN PROBLEM

INTRODUCTION :-
TSP is one of the most interesting 

problems of Operating System that 

haunts the beginners all the time . 

Reading from the book and 

understanding the TSP will take an 

entire day BUT with this simple post 

you will be able to get a clear picture of 

the problem in just two minutes .
JUST FOCUS FOR TWO MINUTES ....
WHAT IS TSP ?
 follow these steps ;-
     1. Imagine you are a salesman and 

your job is to go through a map 

consisting of 20 locations .
      2. your task is to visit each of these 

locations and to sell .
The KEY  POINT is to have minimize 

travelling time .....
you must be thinking how much time 

will it take .....
If  there are 3 locations  namely A , B , 

C  then following situations will arise 

:-
SITUATION 1 ->  Salesman will go to 

"A"  first , followed by "B "amd finally 

"C".
SITUATION 2 ->  Salesman will go to 

"B"  first , followed by "C "amd finally 

"A".
SITUATION 3 ->  Salesman will go to 

"C"  first , followed by "A "amd finally 

"B"
So ,choices left in the ways=>3*2*1 = 6
That means for 20 locations no. of ways 

 to be assessed are 20!= 

20*19*18.....2*1=2432902008176640000 ;
 which is gigantic and practically 

impossible to solve .
But there is a way to solve such 

problems which is GENETIC 

ALGORITHM that will give us an 

approximate solution but not an exact 

one.
GENETIC ALGORITHM SOLUTION =>
It is based on following two aspects -:
1. All locations to be visited .
2. All locations to be visited exactly 

once.
# G.A. solution comprises of MUTATION 

& CROSSOVER .
# MUTATION particularly SWAPPED 

MUTATION  used . In S.M. two values in 

d given location set are randomly 

chosen & swapped .EX - 
[ 1 2 3 4 5 ] =>[1 2 5 4 3 ]
Here 3, 5 are chosen and swapped 

among the location set.
It satisfies the above two aspects needed 

for valid solution . There will be no 

duplication and no missing of 

locations.
# ORDERED CROSSOVER which has 

the same foundations as S.M. and follow 

same constraints will be used here.See 

the following example -:
Parent gene - [1 2 3 4 5 (6 7 8 )9]
                   [9 8 7 6 5 4 3 2 1]
                     NOW =>
                  [ 9 5 4 3 2 6 7 8 1]
(After crossover).
This process is continued till the 

offspring has no empty values .
 If implemented correctly the end result 

should be a route which contains all of 

the positions it's parents did with no 

positions missing or duplicated.
THIS WAS THE SIMPLE G.A. SOLUTION 

FOR T.S.P .
FOR C-CODE OF THIS PROBLEM CLICK 

ON THE FOLLOWING LINK =>

http://www.theprojectspot.com