Travelling Salesman Problem.

Answer Question 1 - Travelling Salesman Problem.

The travelling salesman problem starts with four concepts:

1. A map. This can be a country For Example France.
2. Draw on this this map a set of towns: 1)Paris, 2)Lille, 3)Lyon 4)Marseille, etc.
3. Draw routes between those towns. For example a route between 1-2, 1-3, 2-3, 3-4 etc.
4. Calculate the length of each route. This is a number in km.

That are all the tools you need.
The Travelling Sales Man Problem is to find the shortest (closed) route that connect all the towns once.

If for example all the towns are close to the border than this route looks like a circle.

The idea behind the Travelling Sales Man problem is that the Salesman starts in one town, visists all the towns and returns where he starts, following the shortest route.
The Travelling Sales Man problem offers two challenges:

• First to find a methode to calculate this shortest route.
• Secondly to implement this in a program
• Thirdly to find fastest method to calculate this route.

In order to solve a problem you need an algorithm. Such an algorithm calculates in a certain number of steps the solution of the problem.
A simple algorithm is the following:

1. Calculate all possible routes through the maze.
2. Calculate the length of each route.
3. Calculate the route with the shortest length.

   1---------4 | . . | | . . | | . . | | . . | 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

   In the above example there are 6 solutions. A simple investigations learns that 50% is included twice.

   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. 1---------4 | . . | | . . | | .5. | | . . | 2-------- 3 Maze What the decision tree shows that: From town 1 you can go to 3 towns: 1, 5 and 4 In total there are 8 possible routes. In two cases you return back in town 1 but you did not visit all the towns. This is the situation err1. In two cases you have visited all the towns, but you cannot return back in town 1 without visiting at least one town twice. This is the situation err2.

   The next issue is to demonstrate that the program is correct. To do that you have to test the program.
   First you do that with a simple examples for which you know the answer and next you increase the number of towns and routes one by one and you observe if the answer is still correct

   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.

Answer Question 2 - What is the relation between the TSP and the "P = NP problem"

For comments about the "P = NP problem" in Wikipedia read this: "P versus NP problem" in Wikipedia
The "P versus NP problem" has to do with: if it is as easy to solve the problem as to test the answer.
In the case of a "Travelling Salesman Problem" it is in general as easy to solve a specific problem as to test the solution, because you always need a program.

Reflection

For a critical evaluation of the "Traveling Salesman Problem" in Wikipedia read this: "Travelling Salesman Problem" in Wikipedia

Back to my home page Contents of This Document