IB DP Maths: AI HL复习笔记3.10.6 Bounds for Travelling Salesman Problem

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.

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

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

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