Quiz Space

September 2023 term · AI: Search Methods for Problem Solving · BSCS3003

AI Search Methods Quiz 1: 29 October 2023 (September 2023 term)

The IIT Madras BS AI: Search Methods for Problem Solving (AI Search Methods) Quiz 1 paper sat on 29 Oct 2023, in the September 2023 term: 20 questions for 25 marks in 120 minutes. Every question is below with its answer. Take it as a timed mock test to be marked, or read it through first.

Questions
20
Marks
25
Duration
120 min
MSQ
4
Numerical
3
Written
12
MCQ
1
Take as mock testPractise with answers

Updated

Official paper: IIT M DEGREE AN2 EXAM QPE2 29 Oct 2023 · No negative marking.

Question 1

+2 marksOne or more correct options

STATE SPACE
Recall the rabbits crossing puzzle from the practice assignment. Two groups of rabbits, each group at opposite ends of a path, want to cross the path by making only forward jumps: a rabbit can jump forward to an adjacent empty spot, or jump forward over one rabbit and land in an empty spot.

The start state is (R-LL), where R is a rabbit that wants to go right, and L is a rabbit that wants to go left, and the dash marks the empty spot.
Construct all the states that are reachable from the start state and build a state space graph out of those states, call it Graph-12.
Based on the above data, answer the given subquestions.

Which of the following states are reachable from the start state in exactly 3 moves?

Select all that apply.

  1. A

    (LRL-)

  2. B

    (L-RL)

  3. C

    (RLL-)

  4. D

    (L-LR)

  5. E

    (LL-R)

Show answer

Correct answers

  • A

    (LRL-)

  • B

    (L-RL)

Question 1 on its own page

Question 2

+1 markNumerical answer

STATE SPACE
Recall the rabbits crossing puzzle from the practice assignment. Two groups of rabbits, each group at opposite ends of a path, want to cross the path by making only forward jumps: a rabbit can jump forward to an adjacent empty spot, or jump forward over one rabbit and land in an empty spot.

The start state is (R-LL), where R is a rabbit that wants to go right, and L is a rabbit that wants to go left, and the dash marks the empty spot.
Construct all the states that are reachable from the start state and build a state space graph out of those states, call it Graph-12.
Based on the above data, answer the given subquestions.

From (R-LL), the minimum number of moves needed to reach (LL-R) is __________ .

Show answer

Correct answer: 5

Question 2 on its own page

Question 3

+1 markOne or more correct options

STATE SPACE
Recall the rabbits crossing puzzle from the practice assignment. Two groups of rabbits, each group at opposite ends of a path, want to cross the path by making only forward jumps: a rabbit can jump forward to an adjacent empty spot, or jump forward over one rabbit and land in an empty spot.

The start state is (R-LL), where R is a rabbit that wants to go right, and L is a rabbit that wants to go left, and the dash marks the empty spot.
Construct all the states that are reachable from the start state and build a state space graph out of those states, call it Graph-12.
Based on the above data, answer the given subquestions.

For Graph-12, which of the following algorithms will find the shortest path from (R-LL) to (LL-R)? Assume a suitable MoveGen order for each algorithm.

Select all that apply.

  1. A

    Depth First Search

  2. B

    Breadth First Search

  3. C

    DFID-C (revisits CLOSED nodes)

Show answer

Correct answers

  • A

    Depth First Search

  • B

    Breadth First Search

  • C

    DFID-C (revisits CLOSED nodes)

Question 3 on its own page

Question 4

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. In all the algorithms below, the RemoveSeen procedure will remove nodes from the output of MoveGen if those nodes are present in OPEN/CLOSED lists.
Use Manhattan distance when needed.

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.
Based on the above data, answer the given subquestions.

List the first 4 nodes (including the start node) inspected by Depth First Search. List the nodes in the order they were 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,A,C,I

Question 4 on its own page

Question 5

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. In all the algorithms below, the RemoveSeen procedure will remove nodes from the output of MoveGen if those nodes are present in OPEN/CLOSED lists.
Use Manhattan distance when needed.

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.
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 no path is found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: S,X,Y,G

Show answer

Correct answer: S,A,C,I,G

Question 5 on its own page

Question 6

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. In all the algorithms below, the RemoveSeen procedure will remove nodes from the output of MoveGen if those nodes are present in OPEN/CLOSED lists.
Use Manhattan distance when needed.

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.
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 were 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,A,B,C

Question 6 on its own page

Question 7

+2 marksWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. In all the algorithms below, the RemoveSeen procedure will remove nodes from the output of MoveGen if those nodes are present in OPEN/CLOSED lists.
Use Manhattan distance when needed.

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.
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 no path is found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: S,X,Y,G

Show answer

Correct answer: S,A,D,G

Question 7 on its own page

Question 8

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. In all the algorithms below, the RemoveSeen procedure will remove nodes from the output of MoveGen if those nodes are present in OPEN/CLOSED lists.
Use Manhattan distance when needed.

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.
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 were 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,B,F,E

Question 8 on its own page

Question 9

+2 marksWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. In all the algorithms below, the RemoveSeen procedure will remove nodes from the output of MoveGen if those nodes are present in OPEN/CLOSED lists.
Use Manhattan distance when needed.

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.
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 no path is found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer Format: S,X,Y,G

Show answer

Correct answer: S,B,F,J,G

Question 9 on its own page

Question 10

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. In all the algorithms below, the RemoveSeen procedure will remove nodes from the output of MoveGen if those nodes are present in OPEN/CLOSED lists.
Use Manhattan distance when needed.

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.
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 were 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,B,F,E

Question 10 on its own page

Question 11

+1 markWritten answer

SEARCH
The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by two-way edges.
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. In all the algorithms below, the RemoveSeen procedure will remove nodes from the output of MoveGen if those nodes are present in OPEN/CLOSED lists.
Use Manhattan distance when needed.

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.
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 no path is 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 or more correct options

Genetic Algorithm
A tour of 10 cities is shown below. The edges are bi-directional. Use A,B,C,...,H,I,J as the reference (index) sequence to prepare tour representations.

Based on the above data, answer the given subquestions.

Select all valid path representations of the tour.

Select all that apply.

  1. A

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

  2. B

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

  3. C

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

  4. D

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

Show answer

Correct answers

  • C

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

  • D

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

Question 12 on its own page

Question 13

+1 markOne or more correct options

Genetic Algorithm
A tour of 10 cities is shown below. The edges are bi-directional. Use A,B,C,...,H,I,J as the reference (index) sequence to prepare tour representations.

Based on the above data, answer the given subquestions.

Select all valid adjacency representations of the tour.

Select all that apply.

  1. A

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

  2. B

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

  3. C

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

  4. D

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

Show answer

Correct answers

  • A

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

  • B

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

Question 13 on its own page

Question 14

+2 marksOne correct option

Genetic Algorithm
A tour of 10 cities is shown below. The edges are bi-directional. Use A,B,C,...,H,I,J as the reference (index) sequence to prepare tour representations.

Based on the above data, answer the given subquestions.

Convert the path representation G,E,H,D,J,F,B,I,C,A to ordinal representation.

  1. A

    7,5,6,4,6,4,2,3,2,1

  2. B

    2,8,6,6,4,1,2,3,2,1

  3. C

    2,8,6,6,1,3,2,3,2,1

  4. D

    1,6,6,4,4,4,4,2,1,1

Show answer

Correct answer

  • A

    7,5,6,4,6,4,2,3,2,1

Question 14 on its own page

Question 15

+2 marksWritten answer

Genetic Algorithm
A tour of 10 cities is shown below. The edges are bi-directional. Use A,B,C,...,H,I,J as the reference (index) sequence to prepare tour representations.

Based on the above data, answer the given subquestions.

Two tours in path representation are given below. Generate offspring using Partially Mapped Crossover (PMX), use the locations from 4 to 7 (both inclusive) as the mapping segment. Enter any one of the two child tours in the textbox.

Enter a comma separated list of cities.
DO NOT ENTER SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.

Show answer

Correct answer: G,J,B,H,E,A,D,I,C,F or H,I,G,D,J,F,B,E,A,C

Question 15 on its own page

Question 16

+1 markWritten answer

TSP
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.

ABCDE
A-23211042
B23-863580
C2186-2464
D103524-45
E42806445-
ADACABCDBD
1021232435
AEDECEBEBC
4245648086

Based on the above data, answer the given subquestions.

Use B as the starting city, construct a tour using Nearest Neighbour Heuristic. The tour is __________ . Enter the path representation of the tour, start from B and trace the cities 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: B,X,Y,Z

Show answer

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

Question 16 on its own page

Question 17

+1 markNumerical answer

TSP
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.

ABCDE
A-23211042
B23-863580
C2186-2464
D103524-45
E42806445-
ADACABCDBD
1021232435
AEDECEBEBC
4245648086

Based on the above data, answer the given subquestions.

What is the cost of the tour generated by Nearest Neighbour Heuristic?
Enter a number.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: 17

Show answer

Correct answer: 201

Question 17 on its own page

Question 18

+1 markWritten answer

TSP
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.

ABCDE
A-23211042
B23-863580
C2186-2464
D103524-45
E42806445-
ADACABCDBD
1021232435
AEDECEBEBC
4245648086

Based on the above data, answer the given subquestions.

Construct a tour using Greedy Heuristic. Enter the path representation of the tour starting from city B.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: B,X,Y,Z

Show answer

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

Question 18 on its own page

Question 19

+1 markNumerical answer

TSP
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.

ABCDE
A-23211042
B23-863580
C2186-2464
D103524-45
E42806445-
ADACABCDBD
1021232435
AEDECEBEBC
4245648086

Based on the above data, answer the given subquestions.

What is the cost of the tour generated by Greedy Heuristic?
Enter a number.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: 17

Show answer

Correct answer: 210

Question 19 on its own page

Question 20

+1 markWritten answer

TSP
The distance matrix for 5 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.

ABCDE
A-23211042
B23-863580
C2186-2464
D103524-45
E42806445-
ADACABCDBD
1021232435
AEDECEBEBC
4245648086

Based on the above data, answer the given subquestions.

Construct the savings tour using B as the base city. The savings for including the pairs of cities AC, AD and AE are 88, 48 and 61, respectively. Compute the savings for the remaining three pairs of cities, and use them to simulate the algorithm. Enter the path representation of the tour starting from city B.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: B,X,Y,Z

Show answer

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

Question 20 on its own page