Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
18 / 19 published solutions
Question 119 MSQ · 1.0 marks
**STATE SPACE**
Consider 3-puzzle (a smaller version of 8-puzzle) where a tile (carrying a numeric label) can slide
one position either horizontally or vertically into the **adjacent empty spot,** effectively swapping
the tile and the adjacent empty spot. A tile cannot slide diagonally.
Begin from the start state and build the state space graph by generating valid moves, call it Graph-
1230, use this graph to answer the sub-questions.
6406535137333.
State A
6406535137334.
State B
6406535137335.
State C
6406535137336.
State D
Published solution
**1. Trace the two non-backtracking three-move routes:** Write boards as top-row/bottom-row, using 0 for the blank. From 12/30, one route is \(12/30\to12/03\to02/13\to20/13\), which reaches B. The other is \(12/30\to10/32\to01/32\to31/02\), which reaches C.
**2. Exclude the other options:** A=31/20 and D=23/10 both have the blank at the original bottom-right square. Each move changes the blank’s checkerboard colour, so an odd number of moves cannot return it to that colour.
**Answer: B, C — B and C.**
A: **Incorrect:** Its blank position has the wrong parity for exactly three moves; its shortest distance is four.
B: **Correct:** The displayed route reaches 20/13 in exactly three moves.
C: **Correct:** The displayed route reaches 31/02 in exactly three moves.
D: **Incorrect:** Its blank position has the wrong parity for three moves; its shortest distance is four.
**STATE SPACE**
Consider 3-puzzle (a smaller version of 8-puzzle) where a tile (carrying a numeric label) can slide
one position either horizontally or vertically into the **adjacent empty spot,** effectively swapping
the tile and the adjacent empty spot. A tile cannot slide diagonally.
Begin from the start state and build the state space graph by generating valid moves, call it Graph-
1230, use this graph to answer the sub-questions.
Select the statements that are true about Graph-1230.
6406535137337.
Every move is reversible.
6406535137338.
Every state has a path to every other state.
6406535137339.
Some states have more than two neighbours.
6406535137340.
Every state has exactly two neighbours.
6406535137341.
Every state has exactly one neighbour.
Published solution
**1. Count legal moves at any state:** On a 2×2 board, every blank position is a corner with exactly two orthogonally adjacent tiles, so every state has two distinct neighbours.
**2. Check reversibility and the generated component:** Sliding the same tile back reverses any move. Every vertex of Graph-1230 was generated from the start, and reverse moves return to it; any two vertices are therefore connected through the start.
**Answer: A, B, D — A, B and D.**
A: **Correct:** Swapping a tile with the blank can immediately be undone.
B: **Correct:** All states in the generated component are mutually reachable.
C: **Incorrect:** A corner blank has only two adjacent tiles.
D: **Correct:** Exactly two adjacent tiles give exactly two legal successor states.
E: **Incorrect:** There are always two legal tile moves rather than one.
**STATE SPACE**
Consider 3-puzzle (a smaller version of 8-puzzle) where a tile (carrying a numeric label) can slide
one position either horizontally or vertically into the **adjacent empty spot,** effectively swapping
the tile and the adjacent empty spot. A tile cannot slide diagonally.
Begin from the start state and build the state space graph by generating valid moves, call it Graph-
1230, use this graph to answer the sub-questions.
The number of unique states in Graph-1230 is __________ .
6406535137342.
less than 8
6406535137343.
equal to 8
6406535137344.
more than 8
Published solution
**1. Count reachable boards:** There are 4!=24 arrangements of three labelled tiles and the blank. The sliding-puzzle reachability invariant separates them into two components of twelve states on this 2×2 board.
**2. Check by graph generation:** Repeatedly moving either adjacent tile into the blank produces a cycle containing exactly 12 distinct boards before repetition. Since 12>8, select “more than 8.”
**Answer: C — More than 8 — exactly 12.**
A: **Incorrect:** The reachable component contains 12 boards.
B: **Incorrect:** The reachable component has 12, not 8, boards.
C: **Correct:** Twelve reachable boards exceed eight.
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
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.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
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 are
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**
Published solution
**1. Apply the search rule:** Use a stack with the alphabetically first new successor at the front. RemoveSeen drops successors already in OPEN or CLOSED, so their existing parents are retained.
**2. Track OPEN after expansions:** After S, new=F,H and OPEN=F,H; After F, new=C and OPEN=C,H; After C, new=A and OPEN=A,H.
**3. Read the inspected order:** The first removals from OPEN, including a goal if reached, are S,F,C,A.
**Answer: S,F,C,A.**
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
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.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
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 a path to goal is not found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,G**
Published solution
**1. Apply the search rule:** Use a stack with the alphabetically first new successor at the front. RemoveSeen drops successors already in OPEN or CLOSED, so their existing parents are retained.
**2. Run the frontier to the goal:** The inspected sequence is S → F → C → A → B → G.
**3. Reconstruct from parents:** Follow the goal’s first-discovery parents backward, then reverse them: S → F → C → A → B → G. This parent chain is the returned path; expanded dead ends need not belong to it.
**Answer: S,F,C,A,B,G.**
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
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.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
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 are
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**
Published solution
**1. Apply the search rule:** Use a FIFO queue: append unseen successors in alphabetical order. RemoveSeen preserves the first-discovery parent, so the resulting goal path has the fewest moves.
**2. Track OPEN after expansions:** After S, new=F,H and OPEN=F,H; After F, new=C and OPEN=H,C; After H, new=E and OPEN=C,E.
**3. Read the inspected order:** The first removals from OPEN, including a goal if reached, are S,F,H,C.
**Answer: S,F,H,C.**
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
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.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
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 a path to goal is not found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,G**
Published solution
**1. Apply the search rule:** Use a FIFO queue: append unseen successors in alphabetical order. RemoveSeen preserves the first-discovery parent, so the resulting goal path has the fewest moves.
**2. Run the frontier to the goal:** The inspected sequence is S → F → H → C → E → A → D → I → B → G.
**3. Reconstruct from parents:** Follow the goal’s first-discovery parents backward, then reverse them: S → H → E → I → G. This parent chain is the returned path; expanded dead ends need not belong to it.
**Answer: S,H,E,I,G.**
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
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.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
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 are
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**
Published solution
**1. Apply the search rule:** Choose the smallest h from all of OPEN, breaking equal scores alphabetically. This is greedy best-first search, not a search restricted to the current node’s children.
**2. Track OPEN after expansions:** After S, new=F,H and OPEN=F,H; After H, new=C,E and OPEN=F,C,E; After E, new=A,D,I and OPEN=F,C,A,D,I.
**3. Read the inspected order:** The first removals from OPEN, including a goal if reached, are S,H,E,D.
**Answer: S,H,E,D.**
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
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.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
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 a path to goal is not found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,G**
Published solution
**1. Apply the search rule:** Choose the smallest h from all of OPEN, breaking equal scores alphabetically. This is greedy best-first search, not a search restricted to the current node’s children.
**2. Run the frontier to the goal:** The inspected sequence is S (h=15) → H (h=10) → E (h=6) → D (h=5) → B (h=6) → G (h=0).
**3. Reconstruct from parents:** Follow the goal’s first-discovery parents backward, then reverse them: S → H → E → D → B → G. This parent chain is the returned path; expanded dead ends need not belong to it.
**Answer: S,H,E,D,B,G.**
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
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.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
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 are 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**
Published solution
**1. Apply the search rule:** Choose a strictly lower-h neighbour, breaking ties alphabetically. Hill climbing keeps no alternative frontier for later backtracking.
**2. Follow improving moves:** S (h=15) → H (h=10) → E (h=6) → D (h=5).
**3. Test the stopping point:** At D, neighbours are A (h=13), B (h=6), E (h=6). No strictly improving move remains, and this state is not the goal G. The algorithm therefore stops without a goal path.
**Answer: S,H,E,D.**
**SEARCH**
The MoveGen function and the heuristic function for a state space is provided below. Take S as the
start node and G as the goal node.
When required use alphabetical order to break ties.
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.
Assume that the RemoveSeen procedure will drop the neighbours that are already present in the
OPEN or CLOSED list.
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 a path to goal is not found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: S,X,Y,G**
Published solution
**1. Apply the search rule:** Choose a strictly lower-h neighbour, breaking ties alphabetically. Hill climbing keeps no alternative frontier for later backtracking.
**2. Follow improving moves:** S (h=15) → H (h=10) → E (h=6) → D (h=5).
**3. Test the stopping point:** At D, neighbours are A (h=13), B (h=6), E (h=6). No strictly improving move remains, and this state is not the goal G. The algorithm therefore stops without a goal path.
**Answer: NIL.**
**Genetic Algorithm**
Answer the given subquestions.
Convert the path representation A,C,K,F,B,H,G,I,D,L,E,J to ordinal representation. Use A,B,C,...,L as
the reference (index) sequence.
6406535137353.
1,2,9,4,1,4,3,3,1,3,1,1
6406535137354.
9,4,10,4,2,1,1,5,3,3,1,1
6406535137355.
1,2,9,8,1,3,3,4,1,3,1,1
6406535137356.
3,10,8,3,2,2,5,1,3,3,2,1
Published solution
**1. Use one-based positions in a shrinking reference list:** Find each next city’s current position in A…L, record it, then delete that city.
**2. Perform the successive deletions:** A is 1 in ABCDEFGHIJKL; C is 2 in BCDEFGHIJKL; K is 9 in BDEFGHIJKL; F is 4 in BDEFGHIJL; B is 1 in BDEGHIJL; H is 4 in DEGHIJL; G is 3 in DEGIJL; I is 3 in DEIJL; D is 1 in DEJL; L is 3 in EJL; E is 1 in EJ; J is 1 in J.
**3. Collect the ranks:** 1,2,9,4,1,4,3,3,1,3,1,1.
**Answer: A — 1,2,9,4,1,4,3,3,1,3,1,1.**
A: **Correct:** It records all twelve correct shrinking-list ranks.
B: **Incorrect:** Its first rank 9 selects I rather than the required first city A.
C: **Incorrect:** At the fourth step F has rank 4, not 8.
D: **Incorrect:** Its first rank 3 selects C rather than A.
**Genetic Algorithm**
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.
6406535137357.
I,K,L,D,J,E,C,A,F,B,H,G
6406535137358.
C,D,I,E,B,A,J,K,H,L,G,F
6406535137359.
I,D,L,K,B,A,E,H,C,J,F,G
6406535137360.
A,L,I,E,J,D,C,K,H,F,G,B
Published solution
**1. Identify position cycles:** Following P2 values to their positions in P1 gives cycles of one-based indices (1,7,5,10,3), (2,8,6,4), and (9,11,12). Within each cycle, the two parents contain the same set of cities.
**2. Alternate parent sources:** For child 1, take cycles 1 and 3 from P1 and cycle 2 from P2; for child 2 reverse those choices.
**3. Read the children:** Child 1 is I,K,L,D,J,E,C,A,F,B,H,G. Child 2 is C,D,I,E,B,A,J,K,H,L,G,F. Each contains every city once.
**Answer: A, B — A and B.**
A: **Correct:** This is the child taking cycles 1 and 3 from P1.
B: **Correct:** This is the complementary child.
C: **Incorrect:** It assigns K to position 4, but neither parent has K there, violating cycle crossover’s position inheritance.
D: **Incorrect:** Its first city A comes from neither parent’s first position, violating cycle crossover.
**Genetic Algorithm**
Answer the given subquestions.
Single-point crossover can be used with __________ .
6406535137361.
Adjacency Representation.
6406535137362.
Path Representation
6406535137363.
Ordinal Representation
6406535137364.
All of these
Published solution
**1. Examine the representation constraint:** At ordinal position i, the code is any integer from 1 to n−i+1. Both parents obey the same bound at that position.
**2. Apply single-point crossover:** Copying a prefix from one ordinal parent and a suffix from another preserves each position’s bound. Decoding still removes one distinct city at each step, producing a valid tour.
**Answer: C — Ordinal representation.**
A: **Incorrect:** Crossing successor lists can break the single-cycle requirement or duplicate successors.
B: **Incorrect:** Crossing city permutations directly can duplicate some cities and omit others.
C: **Correct:** Each ordinal position has parent-independent bounds that crossover preserves.
D: **Incorrect:** Only ordinal representation guarantees validity under ordinary single-point crossover.
**Genetic Algorithm**
Answer the given subquestions.
For the case of 3-edge exchange, how many child tours are possible? Enter the number of child
tours in the text box. (Assume that no pair of edges from the selected 3 edges share any city in
common.)
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: 17**
Published solution
**1. Cut three disjoint edges:** The tour breaks into three path segments. Fix one segment’s orientation to remove whole-tour reversal symmetry.
**2. Count reconnections:** The other two segments have 2! orders and 2² orientations, giving 8 undirected reconnection patterns.
**3. Count genuine three-edge exchanges:** Exclude the original tour and the three reconnections equivalent to a two-edge exchange. Thus \(8-1-3=4\) genuine 3-opt children remain.
**Answer: 4.**
**Convention note:** The answer uses the course’s genuine-3-edge convention. If all different reconnections including 2-opt cases are counted, there are seven; including the original gives eight.
**TSP**
Use the distance matrix to construct TSP tours.
Based on the above data, answer the given subquestions.
Use “A” as the starting city, construct a tour using Nearest Neighbour Heuristic. The tour is
__________ . Enter the path representation of the tour, starting from “A” and tracing the cities as
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: A,X,Y,Z
Published solution
**1. Select the closest unvisited city at each step:** A: B=18, C=30, D=90, E=54; choose B; B: C=48, D=84, E=36; choose E; E: C=72, D=24; choose D; D: C=60; choose C.
**2. Close the tour:** Return from C to A at cost 30. The path representation lists each city once; this return is implicit.
**Answer: A,B,E,D,C.**
**TSP**
Use the distance matrix to construct TSP tours.
Based on the above data, answer the given subquestions.
Use “A” as the fulcrum (base) node and use Savings Heuristic to construct the TSP tour. Identify the
new edge added in the first merge operation. Enter the new edge and its savings.
Enter an edge XY and an integer as a comma separated list.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: XY,17
Published solution
**1. Compute all base-A savings:** \(s(i,j)=d(A,i)+d(A,j)-d(i,j)\). The values are BC=0, BD=24, BE=36, CD=60, CE=12 and DE=120.
**2. Take the largest saving:** \(s(D,E)=90+54-24=120\), so the first merge inserts DE. Enter the edge and saving as DE,120.
**Answer: DE,120.**
**TSP**
Use the distance matrix to construct TSP tours.
Based on the above data, answer the given subquestions.
Use “A” as the fulcrum (base) node and use Savings Heuristic to construct the TSP tour. Enter the
path representation of the Savings tour, starting from “A”.
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
Answer format: A,X,Y,Z
Published solution
**1. Calculate savings relative to A:** (s(i,j)=d(A,i)+d(A,j)-d(i,j)). The full list is BC=0, BD=24, BE=36, CD=60, CE=12, DE=120.
**2. Merge by descending savings:** DE (120): merge; CD (60): merge; BE (36): merge. Merge only different chains at their endpoints, preventing premature cycles and degree greater than 2.
**3. Connect the two remaining chain ends to the base:** The tour is A → B → E → D → C → A. The path representation omits the final repeated base.
**Answer: A,B,E,D,C.**
