Chapter 5

Question 1

Define tour

Answer 1

walk visiting every node and returns back to starting node

Question 2

Classical TSM problem

Answer 2

each node visited exactly once before returning to start

Question 3

Practical TSM problem

Answer 3

each node visited at least once before returning to start

Question 4

Outline using MST to find UB

Answer 4

1. Find MST of network and double

Question 5

Outline using RMST to find LB

Answer 5

CLASSICAL ONLY
1. Remove node and attached arcs
2. Find RMST
3. add connecting weight of removed node

Question 6

Outline nearest neighbour algorithm

Answer 6

1. select any node
2. go to nearest node that hasn’t been visited
3. repeat till complete