Skip over navigation
Cambridge University Faculty of Mathematics NRich logo
menu search
  • Teachers expand_more
    • Early years
    • Primary
    • Secondary
    • Post-16
    • Events
    • Professional development
  • Students expand_more
    • Primary
    • Secondary
    • Post-16
  • Parents expand_more
    • Early Years
    • Primary
    • Secondary
    • Post-16
  • Problem-Solving Schools
  • About NRICH expand_more
    • About us
    • Impact stories
    • Support us
    • Our funders
    • Contact us
  • search

Or search by topic

Number and algebra

  • The Number System and Place Value
  • Calculations and Numerical Methods
  • Fractions, Decimals, Percentages, Ratio and Proportion
  • Properties of Numbers
  • Patterns, Sequences and Structure
  • Algebraic expressions, equations and formulae
  • Coordinates, Functions and Graphs

Geometry and measure

  • Angles, Polygons, and Geometrical Proof
  • 3D Geometry, Shape and Space
  • Measuring and calculating with units
  • Transformations and constructions
  • Pythagoras and Trigonometry
  • Vectors and Matrices

Probability and statistics

  • Handling, Processing and Representing Data
  • Probability

Working mathematically

  • Thinking mathematically
  • Developing positive attitudes
  • Cross-curricular contexts

Advanced mathematics

  • Decision Mathematics and Combinatorics
  • Advanced Probability and Statistics
  • Mechanics
  • Calculus

For younger learners

  • Early Years Foundation Stage

Travelling Salesman

Age 11 to 14
Challenge Level Yellow star
  • Problem
  • Getting Started
  • Student Solutions
  • Teachers' Resources



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 - C - F - E - D - A
A - D - E - F - C - B - A

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
A > B > C > D > H > G > F > E > A
A > B > C > G > F > E > H > D > A
A > B > C > G > E > F > H > D > A
A > B > F > E > H > G > C > D > A
A > B > F > G > C > D > H > E > A
A > B > F > H > D > C > G > E > A
A > B > F > H > E > G > C > D > A
A > B > G > C > D > H > F > E > A
A > D > C > B > F > G > H > E > A
A > D > C > B > F > H > G > E > A
A > D > C > B > G > F > H > E > A
A > D > C > B > G > H > F > E > A
A > D > C > G > B > F > H > E > A
A > D > C > G > E > H > F > B > A
A > D > C > G > H > E > F > B > A
A > D > H > E > F > G > C > B > A
A > D > H > F > B > C > G > E > A
A > D > H > F > E > G > C > B > A
A > D > H > G > C > B > F > E > A
A > E > F > B > C > G > H > D > A
A > E > F > G > H > D > C > B > A
A > E > F > H > D > C > G > B > A
A > E > F > H > G > B > C > D > A
A > E > G > C > B > F > H > D > A
A > E > G > C > D > H > F > B > A
A > E > G > F > H > D > C > B > A
A > E > G > H > F > B > C > D > A
A > E > H > D > C > G > F > B > A
A > E > H > F > B > G > C > D > A
A > E > H > F > G > B > C > D > A
A > E > H > G > F > B > C > D > 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

AB 120
BC 70
CD 110
DA 180
-------------
Total: 480

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.]


You may also like

Only Connect

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?

  • Tech help
  • Accessibility Statement
  • Sign up to our newsletter
  • Twitter X logo

The NRICH Project aims to enrich the mathematical experiences of all learners. To support this aim, members of the NRICH team work in a wide range of capacities, including providing professional development for teachers wishing to embed rich mathematical tasks into everyday classroom practice.

NRICH is part of the family of activities in the Millennium Mathematics Project.

University of Cambridge logo NRICH logo