Question 9
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.
What is the lower bound on the cost of the tour as per the TSP BnB algorithm discussed in class? Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 17