BTechibtechi.in
Loading Loading
Free IIT Madras BS notes, PYQs and mock tests at btechi.in

AI Search · TSP Branch & Bound

15 questions · 15 marks · 3 papers

Answer key

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

AI: Search Methods for Problem Solving

TSP Branch & Bound

Official Paper

Examination Instructions & Guidelines

Solve on notebook/paper first before checking solutions.
NAT: Numerical response. No negative marking.
Scientific calculator allowed for all calculations.
Official answer key is sealed at the end of this sheet.

End Term · 31 Aug 2025 (FN)End Term

Read the passage below, then answer Q1–Q5
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, ..., d1, ..., e1, e2). 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.
Q1Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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
Your answer:
Q2Short answer1 Mark·Write the answer
Asked 2 times Key ↓
Which node represents the optimal tour? Enter the node reference number in the text box, or enter NIL if it is not possible to determine the optimal tour. Enter a node reference number. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: a9
Your answer:
Q3Short answer1 Mark·Write the answer
Asked 2 times Key ↓
What is the cost of the optimal tour? Enter the cost of the optimal tour in the text box, or enter NIL if it is not possible to determine the optimal tour. Enter an integer. NO SPACES, TABS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: 42
Your answer:
Q4Short answer1 Mark·Write the answer
Asked 2 times Key ↓
Determine the number of cities in the TSP instance. Enter the number of cities in the text box, or enter NIL if it is not possible to determine the number of cities. Enter an integer. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: 42
Your answer:
Q5Short answer1 Mark·Write the answer
Asked 2 times Key ↓
Start from city A, what is the path representation of the optimal tour? Enter the path representation in the text box, or enter NIL if it is not possible to determine the optimal tour. Enter a comma separated list of cities (city labels). NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: A,B,C
Your answer:

End Term · 31 Aug 2025 (AN)End Term

Read the passage below, then answer Q6–Q10
TSP BnB
TSP BnB algorithm is solving a TSP instance where the cities are A, B, C, .... and so on. The BnB search tree (at the point when the algorithm discovers the optimal tour) is provided below. Each node in the search tree displays an edge (either XY or ¬XY), a cost value, and a unique reference number (a1, b1, ..., c1, ..., d1, ..., e1, e2). Use the reference numbers to break ties. When required, use 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.
Q6Short answer1 Mark·Write the answer
Asked 2 times Key ↓
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 BnB 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
Your answer:
Q7Short answer1 Mark·Write the answer
Asked 2 times Key ↓
Which node represents the optimal tour? Enter the node reference number in the text box, or enter NIL if it is not possible to determine the optimal tour. Enter a node reference number. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: a9
Your answer:
Q8Short answer1 Mark·Write the answer
Asked 2 times Key ↓
What is the cost of the optimal tour? Enter the cost of the optimal tour in the text box, or enter NIL if it is not possible to determine the optimal tour. Enter an integer. NO SPACES, TABS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: 42
Your answer:
Q9Short answer1 Mark·Write the answer
Asked 2 times Key ↓
Determine the number of cities in the TSP instance. Enter the number of cities in the text box, or enter NIL if it is not possible to determine the number of cities. Enter an integer. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: 42
Your answer:
Q10Short answer1 Mark·Write the answer
Asked 2 times Key ↓
Start from city A, what is the path representation of the optimal tour? Enter the path representation in the text box, or enter NIL if it is not possible to determine the optimal tour. Enter a comma separated list of cities (city labels). NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: A,B,C
Your answer:

Quiz 2 · 3 Aug 2025 (AN)Quiz 2

Read the passage below, then answer Q11–Q15
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 B is 30, A to C is 32 and so on.
The search tree traversed by TSP BnB shows four segments.
Identify the four segments xy, uv, rs, pq and then answer the given sub-questions.
Attention: A segment is a two-way edge between two cities. After adding/dropping a permanent segment, infer as many new permanent segments as possible before computing the lower bound.
Q11NAT1 Mark·Write the number
Key ↓
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
Your answer:
Q12Short answer1 Mark·Write the answer
Key ↓
What is the first segment (XY) selected for refining S0? Enter edge label XY NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: XY
Your answer:
Q13NAT1 Mark·Write the number
Key ↓
Your answer:
Q14NAT1 Mark·Write the number
Key ↓
How many tours are represented in the node rs? Enter a natural number. NO SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS. Answer format: 42
Your answer:
Q15NAT1 Mark·Write the number
Key ↓
Your answer:

Official Key

Master Answer Key & Explanations

Official answer keys from IIT Madras BS past papers. Click any question to review.

Reveal Key

Q1b1,c2,b2,c3

Q2d3

Q3434

Q45

Q5A,B,D,E,C / A,C,E,D,B

Q6b1,c1,d2,b2

Q7d5

Q8366

Q95

Q10A,B,D,C,E / A,E,C,D,B

Q11182

Q12AB / BA

Q13206

Q140

Q15320

Questions and answer keys are reproduced from the official IIT Madras BS papers. Topics and repeated question types are BTechi’s own grouping. BTechi is not affiliated with IIT Madras.