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

AI Search · DFS, BFS, Best First & Hill Climbing

8 questions · 8 marks · 1 paper

Answer key

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

AI: Search Methods for Problem Solving

DFS, BFS, Best First & Hill Climbing

Official Paper

Examination Instructions & Guidelines

Solve on notebook/paper first before checking solutions.
Scientific calculator allowed for all calculations.
Official answer key is sealed at the end of this sheet.

Read the passage below, then answer Q1–Q8
SEARCH
The MoveGen function and the heuristic function for a state space is provided below. Take S as the start node and G as the goal node.
When required use alphabetical order to break ties.
When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and, depending on the algorithm, the neighbours are selectively placed in OPEN.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
Q1Short answer1 Mark·Write the answer
Key ↓
List the first 4 nodes inspected by Depth First Search. List the nodes in the order they are inspected. If the algorithm terminates early then list the nodes inspected up until termination. Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,Z
Your answer:
Q2Short answer1 Mark·Write the answer
Key ↓
What is the path found by Depth First Search? Enter the path as a comma separated list of node labels. Enter NIL if a path to goal is not found. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Your answer:
Q3Short answer1 Mark·Write the answer
Key ↓
List the first 4 nodes inspected by Breadth First Search. List the nodes in the order they are inspected. If the algorithm terminates early then list the nodes inspected up until termination. Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,Z
Your answer:
Q4Short answer1 Mark·Write the answer
Key ↓
What is the path found by Breadth First Search? Enter the path as a comma separated list of node labels. Enter NIL if a path to goal is not found. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Your answer:
Q5Short answer1 Mark·Write the answer
Key ↓
List the first 4 nodes inspected by Best First Search. List the nodes in the order they are inspected. If the algorithm terminates early then list the nodes inspected up until termination. Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,Z
Your answer:
Q6Short answer1 Mark·Write the answer
Asked 3 times Key ↓
What is the path found by Best First Search? Enter the path as a comma separated list of node labels. Enter NIL if a path to goal is not found. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Your answer:
Q7Short answer1 Mark·Write the answer
Key ↓
List the first 4 nodes inspected by Hill Climbing. List the nodes in the order they are inspected. If the algorithm terminates early then list the nodes inspected up until termination. Enter a comma separated list of node labels. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,Z
Your answer:
Q8Short answer1 Mark·Write the answer
Key ↓
What is the path found by Hill Climbing? Enter the path as a comma separated list of node labels. Enter NIL if a path to goal is not found. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Your answer:

Official Key

Master Answer Key & Explanations

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

Reveal Key

Q1S,F,C,A

Q2S,F,C,A,B,G

Q3S,F,H,C

Q4S,H,E,I,G

Q5S,H,E,D

Q6S,H,E,D,B,G

Q7S,H,E,D

Q8Nil

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.