STATE SPACE\ Consider 3-puzzle (a smaller version of 8-puzzle) where a tile (carrying a numeric label) can slide one position either horizontally or vertically into the adjacent empty spot, effectively swapping the tile and the adjacent empty spot. A tile cannot slide diagonally. Figure from the passage in the original paper Begin from the start state and build the state space graph by generating valid moves, call it Graph- 1230, use this graph to answer the sub-questions. Select the statements that are true about Graph-1230.

(B) Every state has a path to every other state.

(D) Every state has exactly two neighbours.

(C) Some states have more than two neighbours.

(E) Every state has exactly one neighbour.

AI Search Methods Quiz 1 PYQ Sep 2025: 26 Oct 2025 · IITM BS

Question 1

+1 markOne or more correct options

STATE SPACE
Consider 3-puzzle (a smaller version of 8-puzzle) where a tile (carrying a numeric label) can slide one position either horizontally or vertically into the adjacent empty spot, effectively swapping the tile and the adjacent empty spot. A tile cannot slide diagonally.

Begin from the start state and build the state space graph by generating valid moves, call it Graph- 1230, use this graph to answer the sub-questions.

Select all that apply.

A
State A
B
State B
C
State C
D
State D

Show answer

Correct answers

B
State B
C
State C

Question 1 on its own page

Question 2

+1 markOne or more correct options

STATE SPACE
Consider 3-puzzle (a smaller version of 8-puzzle) where a tile (carrying a numeric label) can slide one position either horizontally or vertically into the adjacent empty spot, effectively swapping the tile and the adjacent empty spot. A tile cannot slide diagonally.

Begin from the start state and build the state space graph by generating valid moves, call it Graph- 1230, use this graph to answer the sub-questions.

Select the statements that are true about Graph-1230.

Select all that apply.

A
Every move is reversible.
B
Every state has a path to every other state.
C
Some states have more than two neighbours.
D
Every state has exactly two neighbours.
E
Every state has exactly one neighbour.

Show answer

Correct answers

A
Every move is reversible.
B
Every state has a path to every other state.
D
Every state has exactly two neighbours.

Question 2 on its own page

Question 3

+1 markOne correct option

STATE SPACE
Consider 3-puzzle (a smaller version of 8-puzzle) where a tile (carrying a numeric label) can slide one position either horizontally or vertically into the adjacent empty spot, effectively swapping the tile and the adjacent empty spot. A tile cannot slide diagonally.

Begin from the start state and build the state space graph by generating valid moves, call it Graph- 1230, use this graph to answer the sub-questions.

The number of unique states in Graph-1230 is __________ .

A
less than 8
B
equal to 8
C
more than 8

Show answer

Correct answer

C
more than 8

Question 3 on its own page

Question 4

+1 markWritten answer

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.

x	MoveGen(x)	h(x)
S	F,H	15
A	B,C,D,E	13
B	A,D,G	6
C	A,F,H	15
D	A,B,E	5
E	A,D,H,I	6
F	C,H,S	14
G	B,D,I	0
H	C,E,S	10
I	E,G	7

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.

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

Show answer

Correct answer: S,F,C,A

Question 4 on its own page

Question 5

+1 markWritten answer

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.

x	MoveGen(x)	h(x)
S	F,H	15
A	B,C,D,E	13
B	A,D,G	6
C	A,F,H	15
D	A,B,E	5
E	A,D,H,I	6
F	C,H,S	14
G	B,D,I	0
H	C,E,S	10
I	E,G	7

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.

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

Show answer

Correct answer: S,F,C,A,B,G

Question 5 on its own page

Question 6

+1 markWritten answer

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.

x	MoveGen(x)	h(x)
S	F,H	15
A	B,C,D,E	13
B	A,D,G	6
C	A,F,H	15
D	A,B,E	5
E	A,D,H,I	6
F	C,H,S	14
G	B,D,I	0
H	C,E,S	10
I	E,G	7

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.

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

Show answer

Correct answer: S,F,H,C

Question 6 on its own page

Question 7

+1 markWritten answer

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.

x	MoveGen(x)	h(x)
S	F,H	15
A	B,C,D,E	13
B	A,D,G	6
C	A,F,H	15
D	A,B,E	5
E	A,D,H,I	6
F	C,H,S	14
G	B,D,I	0
H	C,E,S	10
I	E,G	7

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.

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

Show answer

Correct answer: S,H,E,I,G

Question 7 on its own page

Question 8

+1 markWritten answer

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.

x	MoveGen(x)	h(x)
S	F,H	15
A	B,C,D,E	13
B	A,D,G	6
C	A,F,H	15
D	A,B,E	5
E	A,D,H,I	6
F	C,H,S	14
G	B,D,I	0
H	C,E,S	10
I	E,G	7

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.

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

Show answer

Correct answer: S,H,E,D

Question 8 on its own page

Question 9

+1 markWritten answer

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.

x	MoveGen(x)	h(x)
S	F,H	15
A	B,C,D,E	13
B	A,D,G	6
C	A,F,H	15
D	A,B,E	5
E	A,D,H,I	6
F	C,H,S	14
G	B,D,I	0
H	C,E,S	10
I	E,G	7

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.

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

Show answer

Correct answer: S,H,E,D,B,G

Question 9 on its own page

Question 10

+1 markWritten answer

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.

x	MoveGen(x)	h(x)
S	F,H	15
A	B,C,D,E	13
B	A,D,G	6
C	A,F,H	15
D	A,B,E	5
E	A,D,H,I	6
F	C,H,S	14
G	B,D,I	0
H	C,E,S	10
I	E,G	7

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.

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

Show answer

Correct answer: S,H,E,D

Question 10 on its own page

Question 11

+1 markWritten answer

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.

x	MoveGen(x)	h(x)
S	F,H	15
A	B,C,D,E	13
B	A,D,G	6
C	A,F,H	15
D	A,B,E	5
E	A,D,H,I	6
F	C,H,S	14
G	B,D,I	0
H	C,E,S	10
I	E,G	7

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.

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

Show answer

Correct answer: Nil

Question 11 on its own page

Question 12

+1 markOne correct option

Genetic Algorithm
Answer the given subquestions.

Convert the path representation A,C,K,F,B,H,G,I,D,L,E,J to ordinal representation. Use A,B,C,...,L as the reference (index) sequence.

A
1,2,9,4,1,4,3,3,1,3,1,1
B
9,4,10,4,2,1,1,5,3,3,1,1
C
1,2,9,8,1,3,3,4,1,3,1,1
D
3,10,8,3,2,2,5,1,3,3,2,1

Show answer

Correct answer

A
1,2,9,4,1,4,3,3,1,3,1,1

Question 12 on its own page

Question 13

+1 markOne or more correct options

Genetic Algorithm
Answer the given subquestions.

Path representations of two tours are given below. Generate offspring using Cycle Crossover. P1: I,D,L,E,J,A,C,K,F,B,H,G
P2: C,K,I,D,B,E,J,A,H,L,G,F
Select the child tours.

Select all that apply.

A
I,K,L,D,J,E,C,A,F,B,H,G
B
C,D,I,E,B,A,J,K,H,L,G,F
C
I,D,L,K,B,A,E,H,C,J,F,G
D
A,L,I,E,J,D,C,K,H,F,G,B

Show answer

Correct answers

A
I,K,L,D,J,E,C,A,F,B,H,G
B
C,D,I,E,B,A,J,K,H,L,G,F

Question 13 on its own page

Question 14

+1 markOne correct option

Genetic Algorithm
Answer the given subquestions.

Single-point crossover can be used with __________ .

A
Adjacency Representation.
B
Path Representation
C
Ordinal Representation
D
All of these

Show answer

Correct answer

C
Ordinal Representation

Question 14 on its own page

Question 15

+1 markNumerical answer

Genetic Algorithm
Answer the given subquestions.

For the case of 3-edge exchange, how many child tours are possible? Enter the number of child tours in the text box. (Assume that no pair of edges from the selected 3 edges share any city in common.)
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: 17

Show answer

Correct answer: 4

Question 15 on its own page

Question 16

+1 markWritten answer

TSP
Use the distance matrix to construct TSP tours.

	A	B	C	D	E
A	-	18	30	90	54
B	18	-	48	84	36
C	30	48	-	60	72
D	90	84	60	-	24
E	54	36	72	24	-

Based on the above data, answer the given subquestions.

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

Show answer

Correct answer: A,B,E,D,C

Question 16 on its own page

Question 17

+1 markWritten answer

TSP
Use the distance matrix to construct TSP tours.

	A	B	C	D	E
A	-	18	30	90	54
B	18	-	48	84	36
C	30	48	-	60	72
D	90	84	60	-	24
E	54	36	72	24	-

Based on the above data, answer the given subquestions.

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

Show answer

Correct answer: DE,120 or ED,120

Question 17 on its own page

Question 18

+1 markWritten answer

TSP
Use the distance matrix to construct TSP tours.

	A	B	C	D	E
A	-	18	30	90	54
B	18	-	48	84	36
C	30	48	-	60	72
D	90	84	60	-	24
E	54	36	72	24	-

Based on the above data, answer the given subquestions.

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

Show answer

Correct answer: A,B,E,D,C or A,C,D,E,B

Question 18 on its own page

Question 19

+1 markNumerical answer

TSP
Use the distance matrix to construct TSP tours.

	A	B	C	D	E
A	-	18	30	90	54
B	18	-	48	84	36
C	30	48	-	60	72
D	90	84	60	-	24
E	54	36	72	24	-

Based on the above data, answer the given subquestions.

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

Show answer

Correct answer: 168

Question 19 on its own page

Question 20

+1 markOne or more correct options

TSP
Use the distance matrix to construct TSP tours.

	A	B	C	D	E
A	-	18	30	90	54
B	18	-	48	84	36
C	30	48	-	60	72
D	90	84	60	-	24
E	54	36	72	24	-

Based on the above data, answer the given subquestions.

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?

Select all that apply.

A
This procedure can be used to compute the optimal TSP tour.
B
This procedure is not suitable for computing the optimal TSP tour.
C
This procedure may not always terminate.
D
This procedure will always terminate.

Show answer

Correct answers

B
This procedure is not suitable for computing the optimal TSP tour.
D
This procedure will always terminate.

Question 20 on its own page