The IIT Madras BS AI: Search Methods for Problem Solving (AI Search Methods) Quiz 1 paper sat on 26 Feb 2023, in the January 2023 term, set QPE2: 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.
Given a state space with only irreversible actions/moves, __________ .
Depth First Search can find a solution only if the first move chosen is part ofthe final solution
Depth First Search can find a solution even if the first move chosen is not partof the final solution
Breadth First Search can find a solution only if the first move chosen is part ofthe final solution
Breadth First Search can find a solution even if the first move chosen is notpart of the final solution
Correct answers
Depth First Search can find a solution even if the first move chosen is not partof the final solution
Breadth First Search can find a solution even if the first move chosen is notpart of the final solution
In the Simulated Annealing algorithm, __________ .
a population of agents collaborates in a stochastic manner to solve anoptimisation problem
a single agent generates one random neighbour and moves to it only if it isbetter than the current node
a single agent generates one random neighbour and may move to it whetherit is better than the current node or not
a population of agents solves an optimization problem individually beforecombing the best solutions
Correct answer
a single agent generates one random neighbour and may move to it whetherit is better than the current node or not
A boat, man, lion, goat and a basket of cabbage are on the left bank of a river. The boat can carry a man and one other item only (either a lion, goat or cabbage). When the man is not around, the goat will eat the cabbage and the lion will eat the goat.
Model this problem as a state space search problem. A state is represented as LEFT/RIGHT, for example,
1. NONE/BMLGC: nothing on the left bank and all are on the right bank. 2. LC/BMG: lion, cabbage are on the left bank, and a boat, man, goat are on the right bank. 3. G/BML: goat is on the left bank, and a boat, man, lion are on the right bank. 4. L/BM: lion is on the left bank, and a boat and man are on the right bank.
The first two are safe states where nothing gets eaten, the last two are unsafe states where something gets eaten. When LGC is left alone, assume that the goat eats the cabbage, after that the lion eats the goat, so we will have less states to handle.
A move (or action) in this state space stands for one trip across the river, where the man can go alone in the boat or take one item along with him.
Starting from BMLGC/NONE, which of the following states (both safe and unsafe states) are reachable in exactly 3 moves, nothing more, nothing less. Avoid repeating states like a -> b -> a.
C/BMLG
L/BMGC
BMLG/C
BMGC/L
NONE/BML
NONE/BMLC
Correct answers
C/BMLG
L/BMGC
NONE/BML
NONE/BMLC
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already 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
Correct answer: S,A,B,C
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already 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 there is no path. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Correct answer: S,A,B,C,G
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already 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
Correct answer: S,A,E,H
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already 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 there is no path. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Correct answer: S,E,F,G
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already 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
Correct answer: S,E,D,C
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already 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 there is no path. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Correct answer: S,E,D,C,G
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already 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
Correct answer: S,E,D
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
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 either two-way edges (shown as undirected edges) or one-way edges (shown with one arrowhead).
Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already 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 there is no path. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer Format: S,X,Y,G
Correct answer: Nil
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L as the reference (index) sequence to prepare tour representations.
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L as the reference (index) sequence to prepare tour representations.
Based on the above data, answer the given subquestions.
Select the valid path representations of the tour.
L,I,F,E,B,A,C,K,H,D,J,G,L
H,D,J,G,L,I,F,E,B,A,C,K,H
L,I,F,E,B,A,C,K,H,D,J,G
H,D,J,G,L,I,F,E,B,A,C,K
Correct answers
L,I,F,E,B,A,C,K,H,D,J,G
H,D,J,G,L,I,F,E,B,A,C,K
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L as the reference (index) sequence to prepare tour representations.
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L as the reference (index) sequence to prepare tour representations.
Based on the above data, answer the given subquestions.
Select the valid adjacency representations of the tour.
C,A,K,J,B,E,L,D,F,G,H,I
B,E,A,H,F,I,J,K,L,D,C,G
C,A,K,J,H,E,B,D,F,G,L,I
B,G,A,H,F,I,J,E,L,D,C,K
Correct answers
C,A,K,J,B,E,L,D,F,G,H,I
B,E,A,H,F,I,J,K,L,D,C,G
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L as the reference (index) sequence to prepare tour representations.
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L as the reference (index) sequence to prepare tour representations.
Based on the above data, answer the given subquestions.
Convert the path representation I,H,B,L,J,F,D,A,E,G,K,C to ordinal representation.
9,8,2,9,7,5,3,1,2,2,2,1
12,9,6,5,2,1,1,5,3,1,2,1
9,8,2,9,4,5,6,2,4,3,2,1
9,8,2,9,4,5,6,3,1,1,2,1
Correct answer
9,8,2,9,7,5,3,1,2,2,2,1
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L as the reference (index) sequence to prepare tour representations.
A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,C,...,L 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 5 to 8 as the mapping segment. Enter one of the child tours in the textbox.
Two tours in path representation are given below. Generate offspring using Partially Mapped Crossover (PMX), use the locations from 5 to 8 as the mapping segment. Enter one of the child tours in the textbox.
Enter a comma separated list of cities. DO NOT ENTER SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
Correct answer: I,H,J,L,B,A,C,K,E,G,F,D
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
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 __________ . Use alphabetical order to break ties. Enter the path representation of the tour, starting from B and tracing 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
Correct answer: B,F,D,E,A,G,C
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
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
Correct answer: 255
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
Based on the above data, answer the given subquestions.
Construct a tour using Greedy Heuristic, use the sorted edge list for breaking ties, the edges occurring early in the list wins. Enter the path representation of the tour starting from city A.
Enter a comma separated list of city names. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: A,X,Y,Z
Correct answer: A,G,C,B,E,D,F
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
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
Correct answer: 301
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours.
Based on the above data, answer the given subquestions.
Savings heuristic: the initial set of 6 tours with A as the fulcrum node is shown in the figure. Identify the first two edges that will be removed and the first new edge that will be added, and compute the savings. Enter the first edge added and the savings in the text box.
Savings heuristic: the initial set of 6 tours with A as the fulcrum node is shown in the figure. Identify the first two edges that will be removed and the first new edge that will be added, and compute the savings. Enter the first edge added and the savings in the text box.
An edge from X to Y is named as XY. Enter an edge name XY and a number as a comma separated list. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: XY,17
Correct answer: CG,112
