cs3003_2025T1_Q1_NA.pdf
AI: Search Methods for Problem Solving · Quiz 1 · Jan 2025
← Course papers · Start practice / exam
This page contains the reliably extracted subset, not the complete original paper.
Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
Question 38 MSQ · 0.0 marks
[[IMAGE:023d51d028e29330_2_0]]
Printed graph sheets were provided on time.
Printed graph sheets were provided late.
Printed graph sheets were not provided.
I used the graph sheets.
I did not use graph sheets.
A published solution is not available for this question yet.
Question 39 MSQ · 1.0 marks
**STATE SPACE**
Select the algorithms that find the shortest path (measured in number of hops).
Breadth-First Search
Best-First Search
Depth-First Search
DFID-N (opens only new nodes)
DFID-C (reopens closed nodes)
Hill Climbing
A published solution is not available for this question yet.
Question 40 MCQ · 2.0 marks
**STATE SPACE**
[[IMAGE:023d51d028e29330_3_1]]
[[IMAGE:023d51d028e29330_3_2]]
[[IMAGE:023d51d028e29330_3_3]]
[[IMAGE:023d51d028e29330_3_4]]
[[IMAGE:023d51d028e29330_3_5]]
A published solution is not available for this question yet.
Question 41 MSQ · 1.0 marks
**STATE SPACE**
[[IMAGE:023d51d028e29330_3_6]]
Every move is reversible.
There is at least one move that is not reversible.
There is a path from every state to every other state.
Every state has two neighbours.
A published solution is not available for this question yet.
Question 42 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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:023d51d028e29330_4_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.
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 43 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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:023d51d028e29330_4_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.
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 44 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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:023d51d028e29330_4_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.
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 45 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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:023d51d028e29330_4_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.
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 46 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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:023d51d028e29330_4_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.
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 47 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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:023d51d028e29330_4_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.
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 48 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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:023d51d028e29330_4_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.
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 49 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.
The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists.
Use Manhattan distance when needed.
[[IMAGE:023d51d028e29330_4_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.
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 50 MSQ · 1.0 marks
**Genetic Algorithm**
A tour of 10 cities is shown below. The edges are bi-directional. Use **D, E, F,..., M** as the reference
(index) sequence to prepare tour representations.
[[IMAGE:023d51d028e29330_8_8]]
Based on the above data, answer the given subquestions.
Select the valid path representations of the tour.
J, G, F, I, L, M, E, D, H, K
J, G, F, I, L, M, E, D, H, K, J
M, E, D, H, K, J, G, F, I, L
M, E, D, H, K, J, G, F, I, L, M
A published solution is not available for this question yet.
Question 51 MSQ · 1.0 marks
**Genetic Algorithm**
A tour of 10 cities is shown below. The edges are bi-directional. Use **D, E, F,..., M** as the reference
(index) sequence to prepare tour representations.
[[IMAGE:023d51d028e29330_8_8]]
Based on the above data, answer the given subquestions.
Select the valid adjacency representations of the tour.
F, D, I, M, K, L, G, J, H, E
H, D, I, F, K, L, G, J, M, E
E, M, D, J, L, F, K, H, I, G
E, M, G, J, D, F, K, H, I, L
A published solution is not available for this question yet.
Question 52 MCQ · 2.0 marks
**Genetic Algorithm**
A tour of 10 cities is shown below. The edges are bi-directional. Use **D, E, F,..., M** as the reference
(index) sequence to prepare tour representations.
[[IMAGE:023d51d028e29330_8_8]]
Based on the above data, answer the given subquestions.
Convert the path representation **I, L, G, D, F, H, J, E, K, M** to ordinal representation.
7, 4, 3, 4, 5, 5, 2, 1, 1, 1
6, 8, 4, 1, 2, 2, 2, 1, 1, 1
6, 4, 8, 2, 1, 5, 2, 1, 1, 1
7, 3, 6, 4, 2, 3, 3, 3, 2, 1
A published solution is not available for this question yet.
Question 53 SHORT_TEXT · 2.0 marks
**Genetic Algorithm**
A tour of 10 cities is shown below. The edges are bi-directional. Use **D, E, F,..., M** as the reference
(index) sequence to prepare tour representations.
[[IMAGE:023d51d028e29330_8_8]]
Based on the above data, answer the given subquestions.
Two tours in path representation are given below. Generate offspring using Cycle Crossover.
Enter one of the child tours in the textbox.
[[IMAGE:023d51d028e29330_9_9]]
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 54 SHORT_TEXT · 1.0 marks
**TSP**
The distance matrix for 5 cities and corresponding edge costs (in ascending order) is provided
below. Use this information to construct TSP tours.
[[IMAGE:023d51d028e29330_10_10]]
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 55 NAT · 1.0 marks
**TSP**
The distance matrix for 5 cities and corresponding edge costs (in ascending order) is provided
below. Use this information to construct TSP tours.
[[IMAGE:023d51d028e29330_10_10]]
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 56 SHORT_TEXT · 1.0 marks
**TSP**
The distance matrix for 5 cities and corresponding edge costs (in ascending order) is provided
below. Use this information to construct TSP tours.
[[IMAGE:023d51d028e29330_10_10]]
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 57 NAT · 1.0 marks
**TSP**
The distance matrix for 5 cities and corresponding edge costs (in ascending order) is provided
below. Use this information to construct TSP tours.
[[IMAGE:023d51d028e29330_10_10]]
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 58 SHORT_TEXT · 1.0 marks
**TSP**
The distance matrix for 5 cities and corresponding edge costs (in ascending order) is provided
below. Use this information to construct TSP tours.
[[IMAGE:023d51d028e29330_10_10]]
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:023d51d028e29330_12_11]]
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.