Decision 1 Unit 6

Question 1

What is the Travelling Salesperson used for?

Answer 1

When all nodes need to be visited once and start/finish at the same node.

Question 2

What is the Nearest Neighbour algorithm?

Answer 2

Choose a starting node and choose the least weight arc to the next unused node. Carry on until all nodes have been used then go straight to the end node.

Question 3

How to find the upper bound?

Answer 3

Use the Nearest Neighbour algorithm. The lower the upper bound the better.

Question 4

How to find the lower bound?

Answer 4

Choose a special node and remove it.
Make a minimum spanning tree using Primm’s or Kruskal’s from the remaining arcs.
Then add the special node back in by finding the two lowest weights and add them in.

Question 5

What is the tour and improvement algorithm?

Answer 5

If the 1st and 3rd nodes, and 2nd and 4th nodes connect with a lower weight than 1st and 2nd, and 3rd and 4th then swap them round.