5 - Travelling salesman problem

Question 1

What is the difference between the classical and practical travelling salesman problem?

Answer 1

Classical: each vertex is visited exactly once
Practical: each vertex is visited at least once

Question 2

What is the triangle inequality?

Answer 2

longest side of a triangle is less than or equal to the sum of its sides

Question 3

How can a minimum spanning tree be used to find an upper bound for the travelling salesman problem?

Answer 3

1. Find minimum spanning tree using Kruskal’s or Prim’s
2. Double this (complete cycle)
3. Seek shortcuts by intuition

Question 4

How can a minmum spanning tree be used to find a lower bound for the travelling salesman problem?

Answer 4

1. Remove each vertex and its arc
2. Find residual minimum spanning tree and its length
3. Add to RMST the cost of reconnecting the deleted node by two shortest arcs
4. Greatest of these totals is the lower bound
5. Make lower bound as high as possible to narrow inteveral for optimal solution
6. An optimal solution is found if
   * Lower bound contains a Hamiltonian cycle
   * Lower bound = upper bound

Question 5

How can an upper bound to the travelling salesman problem be found using the Nearest neighbour algorithm?

Answer 5

1. Select each vertex in turn as a starting point
2. Go the nearest vertex not yet selected
3. Repeat step 2 until all vertices are visited and then return to the start vertex using the shortest route
4. Once all vertices have been used as starting vertex, select tour with smallest length as upper bound

It’s basically prim’s but you go to the nearest from that vertex not the nearest from any labelled column