Decision Mathematics 2 - The travelling salesman problem

Cards about the travelling salesman

HideShow resource information

Key Words

Classical - each vertex is visited only once

Practical - each vertex is visited at least once

Walk - finite sequence of edges where the end of one edge is the start of the next

Tour - A walk that visits every vertex & returns to its starting vertex

1 of 4

Finding an upper bound

Minimum spanning tree

  • You can find one of these using either Prim's or Kruskal's algorithm
  • When you have found the MST, double the value that you get (this is effectively going up then down every edge)
  • This can become an improved upper bound by finding a shortcut

Nearest Neighbour

  • Choose a starting vertex
  • Move to the nearest unvisited vertex
  • Repeat step 2 until all vertices have been visited
  • Return to the start vertex
2 of 4

Finding a lower bound

  • Choose a vertex and delete it and all of its connected edges
  • Find a minimum spanning tree for the rest of the network
  • Add the vertex back on to the minimum spanning tree by adding the two shorted arcs from the deleted vertex to the weight of the minimum spanning tree
3 of 4

Nearest Neighbour Algorithm

  • Choose a starting vertex
  • Move from your present position to the nearest unvisited vertex
  • Repeat step 2 until every vertex has been visited
  • Return to start vertex in the quickest way possible from your current position
4 of 4


Charlotte Wilding

Great! :)

Similar Further Maths resources:

See all Further Maths resources »See all resources »