Question 12
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 D is 50, A to E is 76 and so on.
| A | D:50 | E:76 | B:88 | C:92 |
|---|---|---|---|---|
| B | D:40 | C:80 | A:88 | E:140 |
| C | B:80 | A:92 | D:96 | E:100 |
| D | B:40 | A:50 | C:96 | E:120 |
| E | A:76 | C:100 | D:120 | B:140 |
| BD | AD | AE | BC | AB |
|---|---|---|---|---|
| 40 | 50 | 76 | 80 | 88 |
| AC | CD | CE | DE | BE |
|---|---|---|---|---|
| 92 | 96 | 100 | 120 | 140 |
A segment is a two-way edge between two cities. After adding/dropping a permanent segment, infer as many new permanent segments as possible to compute the lower bound.
Run TSP BnB to find the optimal tour.
Determine the first three segments xy, uv and pq processed by TSP BnB.
Based on the above data, answer the given subquestions.
How many tours are represented by the node (S0,xy,uv)?
Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 42