The graph represents a salesman’s area of activity with the
shops that the salesman must visit each day. What route around the
shops has the minimum total distance?
Andrei from Tudor Vianu National College in Bucharest sent in a
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 - AA - C - F - E - D - B - AA -
C - B - D - E - F - AA - 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:
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
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
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
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