Question 13
The distance matrix for 6 cities are provided below. For each city the distances to other cities are listed in ascending order. For example, the distance from A to D is 42, and from A to F is 48, and so on.
| A | D:42 | F:48 | E:64 | C:86 | B:96 |
|---|---|---|---|---|---|
| B | C:72 | F:88 | A:96 | D:104 | E:144 |
| C | D:62 | B:72 | A:86 | F:114 | E:150 |
| D | A:42 | C:62 | F:86 | E:100 | B:104 |
| E | F:58 | A:64 | D:100 | B:144 | C:150 |
| F | A:48 | E:58 | D:86 | B:88 | C:114 |
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 cost of the node (S0,AD,~AF,EF,CD,~AE) in the TSP BnB search tree?
Enter a natural number.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: 17.3