Nearest Neighbour & Deleted Vertex Algorithms (DP IB Applications & Interpretation (AI)): Revision Note

Table of least distances

What is the practical travelling salesman problem?

• The practical travelling salesman problem deals with graphs which might not satisfy either condition of the classical problem

  • The graph might not be complete

  • The direct route between any pair of vertices might not be the shortest route

• Here are some real-life examples

  • Each train station in a rail network is not connected directly to every other station

  • It might be cheaper to translate a book from Mandarin to English and then to French than translating directing from Mandarin to French

• You can convert a practical travelling salesman problem into a classical travelling salesman problem using a table of least distances

  • The table of least distances shows the shortest distance between any two vertices in a graph

• The practical travelling salesman problem might not have a route that visits each vertex exactly once

  • Instead you need to find a minimum route that visits each vertex at least once

How can I find the table of least distances?

• STEP 1
  Fill in the information for vertices that are adjacent in the graph

  • Check if the direct route is the shortest route

    • If it is not, then find the length of the short route between them

• STEP 2
  Find the shortest route that can be travelled between each pair of vertices that are not adjacent

  • This completes the table

Nearest neighbour algorithm

What is the nearest neighbour algorithm?

• The nearest neighbour algorithm can be used to find an upper bound for the minimum weight Hamiltonian cycle

  • This gives an upper bound to the travelling salesman problem

• The nearest neighbour algorithm can only be used on a graph that is complete and satisfies the triangle inequality

  • The table of least distances must be found first if needed

How can I use the nearest neighbour algorithm to find an upper bound?

• STEP 1
  Choose a starting vertex

  • The upper bound depends on the starting vertex

  • Different vertices lead to different upper bounds

  • The best upper bound is the lowest

• 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 then pick any

  • You can circle the least value

• STEP 3
  Repeat step 2 until all vertices have been visited

  • There should be exactly one circled value in each row and each column

• STEP 4
  Add the final edge to return to the starting vertex

Deleted vertex algorithm

What is the deleted vertex algorithm?

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

  • This gives a lower bound to the travelling salesman problem

• The deleted vertex algorithm can only be used on a graph that is complete and satisfies the triangle inequality

  • The table of least distances must be found first if needed

• Any Hamiltonian cycle whose length is equal to the lower bound solves the travelling salesman problem

How can I use the deleted vertex algorithm to find a lower bound?

• STEP 1
  Choose a vertex and delete it along with all edges that are directly connected to it

  • The lower bound depends on the deleted vertex

  • Deleting different vertices leads to different upper bounds

  • The best lower bound is the highest

• STEP 2
  Find a minimum spanning tree for the remaining graph

  • You can use Kruskal's algorithm or Prim's algorithm

• STEP 3
  Add the lengths of the two shortest edges that were deleted from the original graph to the weight of the minimum spanning tree