Decision Mathematics 2 - The travelling salesman problem

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

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

• 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

• 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