DP IB Maths: AI HL

Revision Notes

3.10.6 Bounds for Travelling Salesman Problem

Test Yourself

This revision note discusses more complex situations for the travelling salesman problem and you may wish to refer to the revision note 3.10.5 Travelling Salesman Problem.

Table of Least Distances

In some real-life contexts a graph may not be complete nor satisfy the triangle inequality, for example, when looking at a rail network, not every stop will be connected to every other stop and it may be quicker to travel from stop A to stop B via stop C rather than to travel from A to B directly. Thus, the problem is considered to be a practical travelling salesman problem.

Finding the table of least distances (or weights) can convert a practical travelling salesman problem into a classical travelling salesman problem that can then be analysed.

What is a table of least distances?

  • A table of least distances shows the shortest distance between any two vertices in a graph
    • In some cases, the direct route between two vertices may not be the shortest
  • By finding the table of least distances, a graph can be converted into a complete graph that satisfies the triangle inequality
  • STEP 1
    Fill in the information for vertices that are adjacent in the graph (at this stage check if the direct connections are actually the shortest route)
  • STEP 2
    Complete the rest of the table by finding the shortest route that can be travelled between each pair of vertices that are not adjacent

Exam Tip

  • Remember that the table of least values has a line of symmetry along the leading diagonal for an undirected graph, so complete one half carefully first, then map over to the second half

Worked example

The graph G below contains six vertices representing villages and the roads that connect them. The weighting of the edges represents the time, in minutes, that it takes to walk along a particular road between two villages.

3-10-6-ib-ai-hl-bounds-for-travelling-salesman-problem-we-1

a)
Explain why G is not complete graph.

3-10-6-ib-ai-hl-bounds-for-travelling-salesman-problem-we-1a-solution

b)
Complete the table of least weights below.

  A B C D E F
A            
B            
C            
D            
E            
F            

3-10-6-ib-ai-hl-bounds-for-travelling-salesman-problem-we-1bi-solution

3-10-6-ib-ai-hl-bounds-for-travelling-salesman-problem-we-1bii-solution

Nearest Neighbour Algorithm

As the number of vertices in a graph increases, so does the number of possible Hamiltonian cycles and it can become impractical to solve. The nearest neighbour algorithm can be used to find the upper bound for the minimum weight Hamiltonian cycle.

What is the nearest neighbour algorithm?

  • For a complete graph with at least 3 vertices, performing the nearest neighbour algorithm will generate a low (but not necessarily least) weight Hamiltonian cycle
  • This low weight cycle can be considered the upper bound
  • The best upper bound is the upper bound with the smallest value
  • The nearest neighbour algorithm can only be used on a graph that is complete and satisfies the triangle inequality so the table of least distances should be found first

What are the steps of the nearest neighbour algorithm?

  • STEP 1
    Choose a starting vertex
  • STEP 2
    Follow the edge of least weight from the current vertex to an adjacent unvisited vertex (if there is more than one edge of least weight pick one at random)
  • STEP 3
    Repeat STEP 2 until all vertices have been visited
  • STEP 4
    Add the final edge to return to the starting vertex

Exam Tip

  • If asked to write down the route for the lower bound, don’t forget that some of the entries in the table of lowest distances may not be direct routes between vertices!

Worked example

The table below contains six vertices representing villages and the roads that connect them. The weighting of the edges represents the time in minutes that it takes to walk along a particular road between two villages.

  A B C D E F
A - 14 7 11 13 21
B 14 - 13 18 13 9
C 7 13 - 5 6 14
D 11 18 5 - 10 18
E 13 13 6 10 - 8
F 21 9 14 18 8 -

Starting at village A, use the nearest neighbour algorithm to find the upper bound of the time it would take to visit each village and return to village A.

yTG4~P0v_3-10-6-ib-ai-hl-bounds-for-travelling-salesman-problem-we-2i-solution

3-10-6-ib-ai-hl-bounds-for-travelling-salesman-problem-we-2ii-solution

Deleted Vertex Algorithm

The deleted vertex algorithm can be used to find the lower bound for the minimum weight Hamiltonian cycle.

What is the deleted vertex algorithm?

  • The deleted vertex algorithm can only be used on a graph that is complete and satisfies the triangle inequality so the table of least distances should be found first
  • Deleting different vertices may give different results, the best lower bound is the lower bound with the highest value
  • If you have found a cycle the same length as the lower bound then you have found the shortest route for the travelling salesman problem
  • If the lower bound and the upper bound are the same weight then you have found the shortest route for the travelling salesman problem

What are the steps of the deleted vertex algorithm?

  • STEP 1
    Choose a vertex and delete it along with all edges that are connected to it
  • STEP 2
    Find the minimum spanning tree for the remaining graph (see revision note 3.10.3 Minimum Spanning Trees)
  • STEP 3
    Add the two shortest edges that were deleted from the original graph to the weight of the minimum spanning tree

Exam Tip

  • Be careful when using a weighted adjacency table not to get confused between using Prim’s algorithm and the nearest neighbour algorithm.
    • Remember that Prim’s is used to find a minimum spanning tree, so vertices can be connected to several other vertices and hence can have more than one value in a column circled
    • When using the table for the nearest neighbour algorithm, vertices cannot be revisited so only one value will be circled in each column

Worked example

The table below contains six vertices representing villages and the roads that connect them. The weighting of the edges represents the time in minutes that it takes to walk along a particular road between two villages.

  A B C D E F
A - 14 7 11 13 21
B 14 - 13 18 13 9
C 7 13 - 5 6 14
D 11 18 5 - 10 8
E 13 13 6 10 - 8
F 21 9 14 18 8 -

a)
By deleting vertex A and using Prim’s algorithm, find a lower bound for the time taken to start at village A, visit each of the other villages and return to village A

3-10-6-ib-ai-hl-bounds-for-travelling-salesman-problem-we-3a-solution

b)
Show that by deleting vertex B instead, a higher lower bound can be found.

3-10-6-ib-ai-hl-bounds-for-travelling-salesman-problem-we-3b-solution

 

You've read 0 of your 0 free revision notes

Get unlimited access

to absolutely everything:

  • Downloadable PDFs
  • Unlimited Revision Notes
  • Topic Questions
  • Past Papers
  • Model Answers
  • Videos (Maths and Science)

Join the 80,663 Students that ❤️ Save My Exams

the (exam) results speak for themselves:

Did this page help you?

Naomi C

Author: Naomi C

Naomi graduated from Durham University in 2007 with a Masters degree in Civil Engineering. She has taught Mathematics in the UK, Malaysia and Switzerland covering GCSE, IGCSE, A-Level and IB. She particularly enjoys applying Mathematics to real life and endeavours to bring creativity to the content she creates.