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

AI Search · TSP construction heuristics

5 questions · 5 marks · 1 paper

Answer key

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

AI: Search Methods for Problem Solving

TSP construction heuristics

Official Paper

Examination Instructions & Guidelines

Solve on notebook/paper first before checking solutions.
MSQ: One or more options correct. Select all to score.
NAT: Numerical response. No negative marking.
Scientific calculator allowed for all calculations.
Official answer key is sealed at the end of this sheet.

Read the passage below, then answer Q1–Q5
TSP
Use the distance matrix to construct TSP tours.
Based on the above data, answer the given subquestions.
Q1Short answer1 Mark·Write the answer
Key ↓
Use “A” as the starting city, construct a tour using Nearest Neighbour Heuristic. The tour is __________ . Enter the path representation of the tour, starting from “A” and tracing the cities as selected by the Nearest Neighbour Heuristic. Enter a comma separated list of city names. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: A,X,Y,Z
Your answer:
Q2Short answer1 Mark·Write the answer
Key ↓
Use “A” as the fulcrum (base) node and use Savings Heuristic to construct the TSP tour. Identify the new edge added in the first merge operation. Enter the new edge and its savings. Enter an edge XY and an integer as a comma separated list. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: XY,17
Your answer:
Q3Short answer1 Mark·Write the answer
Key ↓
Use “A” as the fulcrum (base) node and use Savings Heuristic to construct the TSP tour. Enter the path representation of the Savings tour, starting from “A”. Enter a comma separated list of city names. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: A,X,Y,Z
Your answer:
Q4NAT1 Mark·Write the number
Key ↓
What is the cost of the tour generated by Savings Heuristic? Enter an integer. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: 17
Your answer:
Q5MSQ1 Mark·Choose all correct options
Key ↓
Consider N cities in a Euclidean plane and use the Euclidean Distance as the distance measure. For each city, take that city as the fulcrum (base) city and compute its Savings tour. From the resulting N Savings tours, select the cheapest tour. What can you conclude about the above procedure?
1. AThis procedure can be used to compute the optimal TSP tour.
2. BThis procedure is not suitable for computing the optimal TSP tour.
3. CThis procedure may not always terminate.
4. DThis procedure will always terminate.

Official Key

Master Answer Key & Explanations

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

Reveal Key

Q1A,B,E,D,C

Q2DE,120 / ED,120

Q3A,B,E,D,C / A,C,D,E,B

Q4168

Q5B, D

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.