cs3003_2023T2_Q1_NA.pdf
AI: Search Methods for Problem Solving · Quiz 1 · May 2023
← Course papers · Start practice / exam
Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
Question 20 MSQ · 2.0 marks
**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.
[[IMAGE:132a8716b0b35e80_3_1]]
The start state is **(RR-L)** , 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-21.
Based on the above data, answer the given subquestions.
Which of the following states are reachable from the start state in exactly 3 moves?
(RL–R)
(–RLR)
(–RRL)
(–LRR)
(L–RR)
A published solution is not available for this question yet.
Question 21 NAT · 1.0 marks
**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.
[[IMAGE:132a8716b0b35e80_3_1]]
The start state is **(RR-L)** , 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-21.
Based on the above data, answer the given subquestions.
From (RR-L) , the minimum number of moves needed to reach (L-RR) is __________
A published solution is not available for this question yet.
Question 22 MSQ · 1.0 marks
**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.
[[IMAGE:132a8716b0b35e80_3_1]]
The start state is **(RR-L)** , 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-21.
Based on the above data, answer the given subquestions.
For Graph-21, when there is a path from some start state to some goal state, __________ .
Depth First Search can find a solution only if the first move chosen is part of
the final solution
Depth First Search can find a solution even if the first move chosen is not part
of the final solution
Breadth First Search can find a solution only if the first move chosen is part of
the final solution
Breadth First Search can find a solution even if the first move chosen is not
part of the final solution
A published solution is not available for this question yet.
Question 23 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:132a8716b0b35e80_6_2]]
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**
A published solution is not available for this question yet.
Question 24 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:132a8716b0b35e80_6_2]]
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**
A published solution is not available for this question yet.
Question 25 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:132a8716b0b35e80_6_2]]
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**
A published solution is not available for this question yet.
Question 26 SHORT_TEXT · 2.0 marks
**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.
[[IMAGE:132a8716b0b35e80_6_2]]
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**
A published solution is not available for this question yet.
Question 27 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:132a8716b0b35e80_6_2]]
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**
A published solution is not available for this question yet.
Question 28 SHORT_TEXT · 2.0 marks
**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.
[[IMAGE:132a8716b0b35e80_6_2]]
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**
A published solution is not available for this question yet.
Question 29 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:132a8716b0b35e80_6_2]]
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**
A published solution is not available for this question yet.
Question 30 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:132a8716b0b35e80_6_2]]
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**
A published solution is not available for this question yet.
Question 31 MSQ · 1.0 marks
**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.
[[IMAGE:132a8716b0b35e80_12_3]]
Based on the above data, answer the given subquestions.
Select all valid path representations of the tour.
B,I,G,C,H,E,F,A,D,J,B
A,F,E,H,C,G,I,B,J,D,A
B,I,G,C,H,E,F,A,D,J
A,F,E,H,C,G,I,B,J,D
A published solution is not available for this question yet.
Question 32 MSQ · 1.0 marks
**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.
[[IMAGE:132a8716b0b35e80_12_3]]
Based on the above data, answer the given subquestions.
Select all valid adjacency representations of the tour.
D,I,H,J,F,A,C,E,G,B
F,J,G,A,H,E,I,C,B,D
D,I,H,J,A,E,C,F,G,B
E,J,G,A,F,H,I,C,B,D
A published solution is not available for this question yet.
Question 33 MCQ · 2.0 marks
**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.
[[IMAGE:132a8716b0b35e80_12_3]]
Based on the above data, answer the given subquestions.
Convert the path representation C,E,F,D,G,A,H,J,B,I to ordinal representation.
3,4,4,3,3,1,2,3,1,1
2,8,6,2,5,3,3,1,1,1
2,8,6,2,5,4,3,1,1,1
9,5,1,5,1,2,3,1,2,1
A published solution is not available for this question yet.
Question 34 SHORT_TEXT · 2.0 marks
**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.
[[IMAGE:132a8716b0b35e80_12_3]]
Based on the above data, answer the given subquestions.
[[IMAGE:132a8716b0b35e80_14_4]]
A published solution is not available for this question yet.
Question 35 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:132a8716b0b35e80_15_5]]
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
A published solution is not available for this question yet.
Question 36 NAT · 1.0 marks
**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.
[[IMAGE:132a8716b0b35e80_15_5]]
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
A published solution is not available for this question yet.
Question 37 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:132a8716b0b35e80_15_5]]
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
A published solution is not available for this question yet.
Question 38 NAT · 1.0 marks
**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.
[[IMAGE:132a8716b0b35e80_15_5]]
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
A published solution is not available for this question yet.
Question 39 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:132a8716b0b35e80_15_5]]
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 CD,
CE and DE are 83, 82 and 90, 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
A published solution is not available for this question yet.