Question 1  What is the Travelling Salesman problem. 
Question 2  What is the relation between TSP and the "P = NP problem" 
14  . .   . .   . .   . .  2 3 Maze 
1  2  3  4  1 (34) 1  2  4  3  1 (39) 1  3  2  4  1 (41) 1  3  4  2  1 (39) 1  4  2  3  1 (41) 1  4  3  2  1 (34) solutions 
Once you have an algorithm the second chalenge is to write a program to test different examples.
In the above algorithm the most important part is to discover all the routes wich connect each town once. The result of this exercise is what you call a decision tree which links all the towns in all combinations.
The following table shows a result.
/ 4 5 1 3  5 4 1 / / / 3  4  1 2  5  4  3  err2 / / / 2  3 4 1 / / / / / 4  1  err1 1  5  3  2  1  err1 \ \ 4 3 2 1 \ \ / 2  5  1 \ 3  5  2  1 \ / \ / / 2  3  err2 4  5  3  2  1 
The case on the left shows the decision tree in order to calculate all the possible routes in case there are 5 towns.
14  . .   . .   .5.   . .  2 3 MazeWhat the decision tree shows that:

The next challenge in the "Travelling Salesman problem" is to try different algorithms and to uncover which one is fastest.
The advantage when you have one algorithm you can use that one to test if algorithm 2 or 3 is correct. When the results are not correct you know somewhere you have a problem.
Back to my home page Contents of This Document