Question 9
The distance matrix for 5 cities are provided below.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | - | 80 | 78 | 68 | 50 |
| B | 80 | - | 152 | 78 | 38 |
| C | 78 | 152 | - | 98 | 114 |
| D | 68 | 78 | 98 | - | 44 |
| E | 50 | 38 | 114 | 44 | - |
Solve the sub-questions using the TSP Branch-and-Bound algorithm.
Attention: Infer as much as possible (and as early as possible) about the permanent segments in the partial solutions. A segment is a two-way edge between two cities.
What is the lower bound on the cost of the tours (S0) as per the TSP BnB algorithm discussed in class?
Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 17