Travelling Salesman
Problem
A Hamiltonian circuit (named after the Irish mathematician Sir
William Rowan Hamilton) is a continuous path in a graph that
passes
through each of the vertices exactly once and returns to
its
starting point.
How many Hamiltonian circuits can you find in these graphs?
Here is another classic problem. A salesman lives in
city A and he
has to visit the cities B, C and D. The distances
between the
cities are: AB = 120, AC=140, AD=180, BC=70, BD=100,
CD=110. Find
the shortest round trip from A through the other
three cities.
Getting Started
Draw diagrams and work systematically.
Student Solutions
Andrei from Tudor Vianu National College in Bucharest sent in a comprehensive solution:
First I observed that, for Hamiltonian circuits, the starting point does not matter and any point could be considered as the starting point.
For the first circuit, I considered A as the starting point.
I found the following 6 Hamiltonian circuits (3 loops which can be travelled in two directions each):
A - B - D - E - F - C - A
A - C - F - E - D - B - A
A -
C - B - D - E - F - A
A - F - E - D - B - C - A
If the starting point and the direction matter, then there are 3 x 2 x 6 = 36 circuits
(x 2 because there are 2 directions on each path,
and x 6because
there are 6 possible starting points).
For the second circuit, I found the following Hamiltonian circuits starting at A:
A > B > C > D > H > F > G > E > A
(16 distinct loops which can be travelled in two directions each).
If the direction and starting point are considered, then there are 16 x 2 x 8 = 256 Hamiltonian circuits.
Now, for the salesman's problem, he must return home. This is a classical problem, known under the name TSP (Travelling Salesperson Problem).
Because usually there are a lot of cities to be visited, and consequently a lot of routes (if n is the number of cities, than there are (n-1)!/2 routes, as explained at the end of the solution), it is impossible to investigate all closed paths, where the starting and finishing points are the same, to count distances and to choose.
There are some algorithms for this type of problem that can help. I'll apply the Nearest Neighbour Algorithm, and compare the result with the counted distances.
Nearest Neighbour Algorithm
The Nearest Neighbour Algorithm works as follows:
1. Choose any city as a starting point. Call this city 'a'.
2. Visit the nearest city to city 'a', which we shall call city 'b'. City 'b' becomes the 'current city'.
3. Visit the nearest city to city 'b' which has not yet been visited - city 'c'. City 'c' is now the 'current city'.
4. As per point 3, repeatedly visit the nearest unvisited city to the current city until all cities have been visited once.
5. Once all cities have been visited once, return from the last city to have been visited to the starting city - city 'a'.
Starting Point: A
Using the Nearest Neighbour Algorithm I have found a minimum distance of 480 units.
For this problem, there are 3! = 6 possible Hamilton circuits that start at A, and it is not so difficult to count them all:
ABCDA = ADCBA 480
ABDCA = ACDBA 470
ACBDA = ADBCA 490
The shortest trip is ABDCA or ACDBA, i.e. 470 units, an improvement on the result arrived at using the Nearest Neighbour Algorithm.
[The number of distinct routes for n cities is (n-1)!/2. This is so because for the first stage of the journey the salesman has (n-1) possible routes. For the next there are (n-2) and so on. This gives a total of (n-1)!. But, half the routes will be the reverse of the others, so we must divide by 2. For 4 cities this means 3!/2 = 3 paths, as above.]
Teachers' Resources
Mathematicians have found no general criterion to test
whether a
graph contains a Hamiltonian circuit or not. This is
unfortunate
because there are many important questions in graph
theory which
depend on the existence or non-existence of
Hamiltonian circuits.