Question 7
TSP Branch-and-Bound
The TSP Branch-and-Bound algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The Branch-and-Bound search tree at the time when the algorithm has discovered the optimal tour is shown below.
Each node in the search tree displays an edge (either XY or ~XY), a cost value, and a unique reference number (a1, b1, b2, c1, c2, d1, d2, e1, e2, e3, e4). Use the reference numbers to break ties. When required, enter the reference numbers in short answers.
What information can you glean from the search tree? Answer the sub-questions based on the information gleaned from the search tree.
Based on the above data, answer the given subquestions.
Let S0 (ref. no. a1) be the first node to be refined, identify the next 4 nodes (2nd to 5th node) that are refined by the TSP Branch-and-Bound algorithm. Enter the nodes (node reference numbers) in the order they are refined.
Enter a comma separated list of node reference numbers.
NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Answer format: a9,b9,c9,d9