cs3003_2022T3_Q1_AN.pdf cs3003_2022T3_Q1_FN.pdf
AI: Search Methods for Problem Solving · Quiz 1 · Sep 2022
← 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 78 MCQ · 0.0 marks
Note : No Quiz1 for Software Engineering
YES
NO
**AI**
**Section Id :** 64065324004
**Section Number :** 6
**Section type :** Online
**Mandatory or Optional :** Mandatory
**Number of Questions :** 5
**Number of Questions to be attempted :** 5
**Section Marks :** 25
**Display Number Panel :** Yes
**Group All Questions :** No
**Enable Mark as Answered Mark for Review and**
Yes
**Clear Response :**
**Maximum Instruction Time :** 0
A published solution is not available for this question yet.
Question 79 MCQ · 0.0 marks
[[IMAGE:d34f8f920150099b_2_0]]
YES
NO
A published solution is not available for this question yet.
Question 80 MCQ · 1.0 marks
**STATE SPACE**
In the 8-puzzle, use the combination of tile-number (1 to 8) and the direction (Up, Down,Left,
Right) of tile movement to denote a move, for example:
6U — move tile 6 up
2D — move tile 2 down
4L — move tile 4 left
8R — move tile 8 right
Based on the above data, answer the given subquestions.
Starting from board G, the sequence of moves 8D,7R,6U,5U will result in __________ .
[[IMAGE:d34f8f920150099b_3_1]]
Board G
Board A
Board B
Board C
Board D
A published solution is not available for this question yet.
Question 81 SHORT_TEXT · 1.0 marks
**STATE SPACE**
In the 8-puzzle, use the combination of tile-number (1 to 8) and the direction (Up, Down,Left,
Right) of tile movement to denote a move, for example:
6U — move tile 6 up
2D — move tile 2 down
4L — move tile 4 left
8R — move tile 8 right
Based on the above data, answer the given subquestions.
Starting from board S, what is the shortest sequence of moves that will result in board G?
[[IMAGE:d34f8f920150099b_4_2]]
A published solution is not available for this question yet.
Question 82 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 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
[[IMAGE:d34f8f920150099b_5_3]]
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 83 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 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
[[IMAGE:d34f8f920150099b_5_3]]
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,Z,G**
A published solution is not available for this question yet.
Question 84 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 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
[[IMAGE:d34f8f920150099b_5_3]]
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 85 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 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
[[IMAGE:d34f8f920150099b_5_3]]
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,Z,G**
A published solution is not available for this question yet.
Question 86 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 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
[[IMAGE:d34f8f920150099b_5_3]]
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 87 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 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
[[IMAGE:d34f8f920150099b_5_3]]
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,Z,G**
A published solution is not available for this question yet.
Question 88 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 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
[[IMAGE:d34f8f920150099b_5_3]]
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 89 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 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
[[IMAGE:d34f8f920150099b_5_3]]
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,Z,G**
A published solution is not available for this question yet.
Question 90 MSQ · 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 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
[[IMAGE:d34f8f920150099b_5_3]]
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.
[[IMAGE:d34f8f920150099b_11_4]]
State Space 1
State Space 2
State Space 3
State Space 4
A published solution is not available for this question yet.
Question 91 MSQ · 1.0 marks
**GENETIC ALGORITHM**
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.
[[IMAGE:d34f8f920150099b_12_5]]
Based on the above data, answer the given subquestions.
Select the valid path representations of the tour.
I,D,L,E,J,A,C,K,F,B,H,G
A,J,E,L,D,I,G,H,B,F,K,C
A,C,K,L,G,J,F,H,I,D,E,B
A,C,K,H,J,F,G,I,D,L,E,B
A published solution is not available for this question yet.
Question 92 MSQ · 1.0 marks
**GENETIC ALGORITHM**
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.
[[IMAGE:d34f8f920150099b_12_5]]
Based on the above data, answer the given subquestions.
Select the valid adjacency representations of the tour.
C,H,K,L,J,B,I,G,D,A,F,E
J,F,A,I,L,K,H,B,G,E,C,D
I,D,L,E,J,A,C,K,F,B,H,G
A,J,E,L,D,I,G,H,B,F,K,C
A published solution is not available for this question yet.
Question 93 MCQ · 2.0 marks
**GENETIC ALGORITHM**
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.
[[IMAGE:d34f8f920150099b_12_5]]
Based on the above data, answer the given subquestions.
Convert the path representation A,C,K,F,B,H,G,I,D,L,E,J to ordinal representation.
1,2,9,4,1,4,3,3,1,3,1,1
9,4,10,4,2,1,1,5,3,3,1,1
1,2,9,4,1,3,3,4,1,3,1,1
3,10,8,3,2,2,5,1,3,3,2,1
A published solution is not available for this question yet.
Question 94 MSQ · 2.0 marks
**GENETIC ALGORITHM**
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.
[[IMAGE:d34f8f920150099b_12_5]]
Based on the above data, answer the given subquestions.
Path representations of two tours are given below. Generate offspring using Cycle Crossover.
**P1:** I,D,L,E,J,A,C,K,F,B,H,G
**P2:** C,K,I,D,B,E,J,A,H,L,G,F
Select the child tours.
I,K,L,D,J,E,C,A,F,B,H,G
C,D,I,E,B,A,J,K,H,L,G,F
I,D,L,K,B,A,E,H,C,J,F,G
A,L,I,E,J,D,C,K,H,F,G,B
A published solution is not available for this question yet.
Question 95 SHORT_TEXT · 1.0 marks
**TSP**
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided
below. Use this information to construct TSP tours.
[[IMAGE:d34f8f920150099b_15_6]]
Based on the above data, answer the given subquestions.
Use E as the starting city, construct a tour using Nearest Neighbour Heuristic. The tour is __________
. Enter the path representation of the tour, starting from E 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: E,X,Y,Z
A published solution is not available for this question yet.
Question 96 NAT · 1.0 marks
**TSP**
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided
below. Use this information to construct TSP tours.
[[IMAGE:d34f8f920150099b_15_6]]
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 97 SHORT_TEXT · 1.0 marks
**TSP**
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided
below. Use this information to construct TSP tours.
[[IMAGE:d34f8f920150099b_15_6]]
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 A.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: A,X,Y,Z
A published solution is not available for this question yet.
Question 98 NAT · 1.0 marks
**TSP**
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided
below. Use this information to construct TSP tours.
[[IMAGE:d34f8f920150099b_15_6]]
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 99 SHORT_TEXT · 1.0 marks
**TSP**
The distance matrix for 7 cities and the corresponding edge costs (in sorted order) are provided
below. Use this information to construct TSP tours.
[[IMAGE:d34f8f920150099b_15_6]]
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.
[[IMAGE:d34f8f920150099b_18_7]]
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
A published solution is not available for this question yet.
Question 100 MCQ · 0.0 marks
[[IMAGE:d34f8f920150099b_19_8]]
YES
NO
A published solution is not available for this question yet.