cs3003_2024T2_Q1_NA.pdf
AI: Search Methods for Problem Solving · Quiz 1 · May 2024
← 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 19 MSQ · 5.0 marks
[[IMAGE:279c850c4dac8101_1_0]]
[1, 2, 4, 6]
[1, 2, 4, 5, 6]
[1, 3, 6, 1, 2, 4, 6]
[1, 3, 6, 1, 2, 4, 5]
**AI**
**Section Id :** 64065359425
**Section Number :** 2
**Section type :** Online
**Mandatory or Optional :** Mandatory
**Number of Questions :** 8
**Number of Questions to be attempted :** 8
**Section Marks :** 25
**Display Number Panel :** Yes
**Section Negative Marks :** 0
**Group All Questions :** No
**Enable Mark as Answered Mark for Review and**
No
**Clear Response :**
**Section Maximum Duration :** 0
**Section Minimum Duration :** 0
**Section Time In :** Minutes
**Maximum Instruction Time :** 0
A published solution is not available for this question yet.
Question 21 MCQ · 0.0 marks
[[IMAGE:279c850c4dac8101_2_1]]
Printed graph sheets were provided to me.
Printed graph sheets were not provided to me.
I did not use graph sheets.
A published solution is not available for this question yet.
Question 22 MCQ · 1.0 marks
Which of the following is/are guaranteed in any state space?
Each move is reversible.
Each state is reachable from every other state.
The goal state is reachable from the start state.
None of these.
A published solution is not available for this question yet.
Question 23 MSQ · 2.0 marks
Consider the 3-2-1 Water Jug puzzle with three jugs A, B and C of capacities 3L, 2L and 1L,
respectively.
A state is uniquely represented by the amount of water present in the three jugs, for example, the
tuple (3,0,0) describes the state where jug A contains 3L of water and jugs B and C are empty.
Two basic (atomic) moves are allowed: (1.) pick up a jug and fill up (top up) another jug, and (2.)
pick up a jug and empty it into another jug, without spilling any water in the process.
Start from (3,0,0) and construct the state space graph of this puzzle.
Which of the following states occur in the state space graph?
[[IMAGE:279c850c4dac8101_3_2]]
[[IMAGE:279c850c4dac8101_3_3]]
[[IMAGE:279c850c4dac8101_3_4]]
[[IMAGE:279c850c4dac8101_3_5]]
A published solution is not available for this question yet.
Question 24 MSQ · 1.0 marks
Which of the following is true about the 3-2-1 Water Jug state space?
Every move is reversible.
Every state is reachable from every other state.
From (3,0,0) there is a path to (1,1,1).
A published solution is not available for this question yet.
Question 25 SHORT_TEXT · 1.0 marks
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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:279c850c4dac8101_4_6]]
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 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 26 SHORT_TEXT · 1.0 marks
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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:279c850c4dac8101_4_6]]
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**
A published solution is not available for this question yet.
Question 27 SHORT_TEXT · 1.0 marks
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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:279c850c4dac8101_4_6]]
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 28 SHORT_TEXT · 2.0 marks
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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:279c850c4dac8101_4_6]]
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**
A published solution is not available for this question yet.
Question 29 SHORT_TEXT · 1.0 marks
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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:279c850c4dac8101_4_6]]
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 30 SHORT_TEXT · 2.0 marks
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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:279c850c4dac8101_4_6]]
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**
A published solution is not available for this question yet.
Question 31 SHORT_TEXT · 1.0 marks
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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:279c850c4dac8101_4_6]]
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 32 SHORT_TEXT · 1.0 marks
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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:279c850c4dac8101_4_6]]
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**
A published solution is not available for this question yet.
Question 33 MSQ · 1.0 marks
A tour of 12 cities is shown below. The edges are bi-directional. Use K,L,M,...,V as the reference
(index) sequence to prepare tour representations.
[[IMAGE:279c850c4dac8101_8_7]]
Based on the above data, answer the given subquestions.
Select the valid path representations of the tour.
M,U,S,K,O,V,R,T,P,L,N,Q
K,S,U,M,Q,N,L,P,T,R,V,O
M,U,S,K,O,V,R,T,P,L,N,Q,M
K,S,U,M,Q,N,L,P,T,R,V,O,K
A published solution is not available for this question yet.
Question 34 MSQ · 1.0 marks
A tour of 12 cities is shown below. The edges are bi-directional. Use K,L,M,...,V as the reference
(index) sequence to prepare tour representations.
[[IMAGE:279c850c4dac8101_8_7]]
Based on the above data, answer the given subquestions.
Select the valid adjacency representations of the tour.
O,N,U,Q,V,L,M,T,K,P,S,R
S,P,Q,L,K,T,N,V,U,R,M,O
P,N,U,Q,V,L,O,T,K,M,S,R
S,P,T,L,Q,K,N,V,U,R,M,O
A published solution is not available for this question yet.
Question 35 MCQ · 2.0 marks
A tour of 12 cities is shown below. The edges are bi-directional. Use K,L,M,...,V as the reference
(index) sequence to prepare tour representations.
[[IMAGE:279c850c4dac8101_8_7]]
Based on the above data, answer the given subquestions.
Convert the path representation O,T,M,L,U,P,K,N,R,V,S,Q to ordinal representation.
[[IMAGE:279c850c4dac8101_9_8]]
[[IMAGE:279c850c4dac8101_9_9]]
[[IMAGE:279c850c4dac8101_9_10]]
[[IMAGE:279c850c4dac8101_9_11]]
A published solution is not available for this question yet.
Question 36 SHORT_TEXT · 2.0 marks
A tour of 12 cities is shown below. The edges are bi-directional. Use K,L,M,...,V as the reference
(index) sequence to prepare tour representations.
[[IMAGE:279c850c4dac8101_8_7]]
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.
[[IMAGE:279c850c4dac8101_9_12]]
Enter a comma separated list of cities.
DO NOT ENTER SPACES, TABS, DOTS, BRACKETS OR EXTRANEOUS CHARACTERS.
A published solution is not available for this question yet.
Question 37 SHORT_TEXT · 1.0 marks
[[IMAGE:279c850c4dac8101_10_13]]
Based on the above data, answer the given subquestions.
Start from city C and construct a tour using Nearest Neighbour Heuristic. Enter the path
representation of the tour starting from city C. Use the same order in which cities were added to
the tour.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: C,X,Y,Z
A published solution is not available for this question yet.
Question 38 NAT · 1.0 marks
[[IMAGE:279c850c4dac8101_10_13]]
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 39 SHORT_TEXT · 1.0 marks
[[IMAGE:279c850c4dac8101_10_13]]
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 C.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: C,X,Y,Z
A published solution is not available for this question yet.
Question 40 NAT · 1.0 marks
[[IMAGE:279c850c4dac8101_10_13]]
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 41 SHORT_TEXT · 1.0 marks
[[IMAGE:279c850c4dac8101_10_13]]
Based on the above data, answer the given subquestions.
Take C as the fulcrum node and compute the **two** missing values in the savings list (full list) given
below. Construct the savings tour. Enter the path representation of the tour starting from city C.
[[IMAGE:279c850c4dac8101_12_14]]
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: C,X,Y,Z
A published solution is not available for this question yet.