Question 10
TSP
The distance matrix for 5 cities (A to E) and the sorted edge list is provided below.
For each city the distances to other cities are listed in ascending order.
For example, in row one, the distance from A to B is 30, A to C is 32 and so on.
| A | B:30 | C:32 | D:68 | E:70 |
|---|---|---|---|---|
| B | A:30 | C:36 | E:40 | D:44 |
| C | A:32 | B:36 | D:50 | E:72 |
| D | E:42 | B:44 | C:50 | A:68 |
| E | B:40 | D:42 | A:70 | C:72 |
| AB | AC | BC | BE | DE |
|---|---|---|---|---|
| 30 | 32 | 36 | 40 | 42 |
| BD | CD | AD | AE | CE |
|---|---|---|---|---|
| 44 | 50 | 68 | 70 | 72 |
The search tree traversed by TSP BnB shows four segments.
Identify the four segments xy, uv, rs, pq and then answer the given sub-questions.
Attention: A segment is a two-way edge between two cities. After adding/dropping a permanent segment, infer as many new permanent segments as possible before computing the lower bound.
How many tours are represented in the node rs?
Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 42