Travelling salesman algorithms

• • Classic travelling salesman problem: each vertex must be visited exactly once
  • Practical travelling salesman problem: each vertex must be visited at least once
• Using a minimum spanning tree to find the upper bound:

  • find the minimum spanning tree
  • double every edge
  • try and find "shortcuts"
  • list the edges which have been deleted and those which have been added for the "shortcuts"
  • mention the weight of the graph