Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
25 / 26 published solutions
Question 2 MSQ · 0.0 marks
6406537043204.
Printed graph sheets were provided on time.
6406537043205.
Printed graph sheets were provided late.
6406537043206.
Printed graph sheets were not provided.
6406537043207.
I used the graph sheets.
6406537043208.
I did not use graph sheets.
Published solution
**1. Interpret this administrative entry:** The image asks candidates to request printed graph sheets. The supplied zero-mark key records “provided on time” and “used.” This is an experience-report item rather than a problem with a derivable academic answer.
**Answer: A, D — A and D — supplied administrative responses.**
**Convention note:** These selections preserve the provided key; they do not establish what happened to an individual candidate.
A: **Correct:** This is the availability report selected by the supplied key.
B: **Incorrect:** This is not the timing report selected by the key.
C: **Incorrect:** This contradicts the key’s report that sheets were provided.
D: **Correct:** This is the usage report selected by the supplied key.
E: **Incorrect:** This contradicts the key’s reported usage.
**STATE SPACE SEARCH**
A gameboard is made of hexagonal tiles, allowing 6 directions of movement from each tile:
north, south, north-east, north-west, south-east, and south-west.
A knight can move in two equivalent ways: take **two** steps in a chosen direction, turn 60 degrees
left or right, and take **one** final step; or equivalently take **one** step in a chosen direction, turn 60
degrees left or right, and take **two** final steps.
This rule generates 12 move choices as illustrated below.
A move is valid if its starting and landing tiles exist, even if the intervening tiles are missing.
**Problem Statement:**
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a
list of valid move choices in alphabetical order, e.g., MoveGen(A) = [E,L].
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and
opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of
corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
Based on the above data, answer the given subquestions.
Design a state representation for the gameboard, enter its description in the textbox as succinct
as possible.
Published solution
**1. Identify the changing information:** There is one knight and a fixed board. Its current tile completely determines which moves are possible; previously visited tiles do not constrain a legal move.
**2. Encode a state:** Store one label from A through L as the knight’s current board position. No history or extra piece positions are needed.
**Answer: Board position.**
**STATE SPACE SEARCH**
A gameboard is made of hexagonal tiles, allowing 6 directions of movement from each tile:
north, south, north-east, north-west, south-east, and south-west.
A knight can move in two equivalent ways: take **two** steps in a chosen direction, turn 60 degrees
left or right, and take **one** final step; or equivalently take **one** step in a chosen direction, turn 60
degrees left or right, and take **two** final steps.
This rule generates 12 move choices as illustrated below.
A move is valid if its starting and landing tiles exist, even if the intervening tiles are missing.
**Problem Statement:**
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a
list of valid move choices in alphabetical order, e.g., MoveGen(A) = [E,L].
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and
opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of
corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
Based on the above data, answer the given subquestions.
The number of unique states in the gameboard state space is __________ .
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: 42**
Published solution
**1. Count the possible representations:** The knight can occupy one of twelve labelled tiles A–L, so the full board state space has 12 distinct states.
**2. Separate size from reachability:** Disconnection can limit states reachable from a particular start, but it does not remove tiles from the full board state space.
**Answer: 12.**
**STATE SPACE SEARCH**
A gameboard is made of hexagonal tiles, allowing 6 directions of movement from each tile:
north, south, north-east, north-west, south-east, and south-west.
A knight can move in two equivalent ways: take **two** steps in a chosen direction, turn 60 degrees
left or right, and take **one** final step; or equivalently take **one** step in a chosen direction, turn 60
degrees left or right, and take **two** final steps.
This rule generates 12 move choices as illustrated below.
A move is valid if its starting and landing tiles exist, even if the intervening tiles are missing.
**Problem Statement:**
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a
list of valid move choices in alphabetical order, e.g., MoveGen(A) = [E,L].
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and
opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of
corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
Based on the above data, answer the given subquestions.
MoveGen(G) is __________ .
Enter a comma separated list of positions.
NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: A,B,C,D**
Published solution
**1. Translate the knight rule into displacements:** On the hex-centre lattice, a jump is two adjacent-centre steps in one direction and one in a direction turned 60°. Its length is \(\sqrt{3(4+1+4\cos60^\circ)}=\sqrt{21}\).
**2. Check existing landing tiles:** Relative to G, C has centre displacement \((-4.5,-\sqrt3/2)\) and H has \((-4.5,\sqrt3/2)\), both legal jump orientations. No other existing tile is a landing point. Alphabetical MoveGen(G)=C,H.
**Answer: C,H.**
**STATE SPACE SEARCH**
A gameboard is made of hexagonal tiles, allowing 6 directions of movement from each tile:
north, south, north-east, north-west, south-east, and south-west.
A knight can move in two equivalent ways: take **two** steps in a chosen direction, turn 60 degrees
left or right, and take **one** final step; or equivalently take **one** step in a chosen direction, turn 60
degrees left or right, and take **two** final steps.
This rule generates 12 move choices as illustrated below.
A move is valid if its starting and landing tiles exist, even if the intervening tiles are missing.
**Problem Statement:**
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a
list of valid move choices in alphabetical order, e.g., MoveGen(A) = [E,L].
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and
opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of
corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
Based on the above data, answer the given subquestions.
d(C,G) is __________ .
Enter a decimal number rounded to one decimal place.
NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: 42.1**
Published solution
**1. Read centre offsets:** Taking horizontal units of 1.5 and vertical units of \(\sqrt3/2\), C and G differ by 3 horizontal units and 1 vertical unit, i.e. \(\Delta x=4.5,\Delta y=\sqrt3/2\).
**2. Use Euclidean distance:** \[d(C,G)=\sqrt{4.5^2+(\sqrt3/2)^2}=\sqrt{21}\approx4.582576\to4.6.\]
**Answer: 4.6.**
**STATE SPACE SEARCH**
A gameboard is made of hexagonal tiles, allowing 6 directions of movement from each tile:
north, south, north-east, north-west, south-east, and south-west.
A knight can move in two equivalent ways: take **two** steps in a chosen direction, turn 60 degrees
left or right, and take **one** final step; or equivalently take **one** step in a chosen direction, turn 60
degrees left or right, and take **two** final steps.
This rule generates 12 move choices as illustrated below.
A move is valid if its starting and landing tiles exist, even if the intervening tiles are missing.
**Problem Statement:**
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a
list of valid move choices in alphabetical order, e.g., MoveGen(A) = [E,L].
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and
opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of
corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
Based on the above data, answer the given subquestions.
What is true about the gameboard state space?
(Note: a path is a sequence of one or more moves.)
6406537043213.
At least one state has no path from another state.
6406537043214.
Every state has a path to every other state.
6406537043215.
Every state has at most two neighbours.
6406537043216.
Every state has at least 12 neighbours.
Published solution
**1. Build the legal-move graph:** Ten tiles form the cycle A–E–F–J–K–B–C–G–H–L–A. D and I have no legal neighbours.
**2. Infer connectivity and degrees:** The isolated tiles cannot be reached from the cycle, and every tile has degree either 0 or 2.
**Answer: A, C — A and C.**
A: **Correct:** D and I are isolated, so not all state pairs have paths.
B: **Incorrect:** The two isolated tiles disprove universal reachability.
C: **Correct:** Cycle vertices have two neighbours; isolated vertices have zero.
D: **Incorrect:** Twelve theoretical jump directions do not imply twelve existing landing tiles.
**STATE SPACE SEARCH**
A gameboard is made of hexagonal tiles, allowing 6 directions of movement from each tile:
north, south, north-east, north-west, south-east, and south-west.
A knight can move in two equivalent ways: take **two** steps in a chosen direction, turn 60 degrees
left or right, and take **one** final step; or equivalently take **one** step in a chosen direction, turn 60
degrees left or right, and take **two** final steps.
This rule generates 12 move choices as illustrated below.
A move is valid if its starting and landing tiles exist, even if the intervening tiles are missing.
**Problem Statement:**
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a
list of valid move choices in alphabetical order, e.g., MoveGen(A) = [E,L].
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and
opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of
corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
Based on the above data, answer the given subquestions.
Can a knight complete a TSP tour on the gameboard, visiting all the positions?
6406537043217.
Yes
6406537043218.
No
6406537043219.
Cannot be determined
Published solution
**1. Use the graph structure:** D and I are isolated, while the remaining ten tiles lie in one cycle.
**2. Apply the tour requirement:** A knight tour visiting all twelve positions would have to reach the isolated tiles. No such path or closed tour exists.
**Answer: B — No.**
A: **Incorrect:** There is no move into or out of the isolated positions.
B: **Correct:** Disconnection prevents a tour through all twelve tiles.
C: **Incorrect:** The legal-move graph determines impossibility directly.
**SEARCH**
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a
list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move
choices are as described in the STATE SPACE SEARCH section.
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and
opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of
corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties.
**Note:** When we say a node (a state) is inspected/expanded/refined it means: the node (the state) 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.
**Note:** RemoveSeen procedure will drop neighbours already present in OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
List the first 4 positions inspected by Depth-First Search. List the positions in the order they are
inspected. If the algorithm terminates early then list the positions inspected up until termination.
Enter a comma separated list of positions.
NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: 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 F, new=E,J and OPEN=E,J; After E, new=A and OPEN=A,J; After A, new=L and OPEN=L,J.
**3. Read the inspected order:** The first removals from OPEN, including a goal if reached, are F,E,A,L.
**Answer: F,E,A,L.**
**SEARCH**
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a
list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move
choices are as described in the STATE SPACE SEARCH section.
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and
opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of
corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties.
**Note:** When we say a node (a state) is inspected/expanded/refined it means: the node (the state) 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.
**Note:** RemoveSeen procedure will drop neighbours already present in 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 positions.
Enter NIL if a path to the goal is not found.
NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: 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. Run the frontier to the goal:** The inspected sequence is F → E → A → L → H → G → C.
**3. Reconstruct from parents:** Follow the goal’s first-discovery parents backward, then reverse them: F → E → A → L → H → G → C. This parent chain is the returned path; expanded dead ends need not belong to it.
**Answer: F,E,A,L,H,G,C.**
**SEARCH**
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a
list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move
choices are as described in the STATE SPACE SEARCH section.
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and
opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of
corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties.
**Note:** When we say a node (a state) is inspected/expanded/refined it means: the node (the state) 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.
**Note:** RemoveSeen procedure will drop neighbours already present in OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
List the first 4 positions inspected by Breadth-First Search. List the positions in the order they are
inspected. If the algorithm terminates early then list the positions inspected up until termination.
Enter a comma separated list of positions.
NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: 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 F, new=E,J and OPEN=E,J; After E, new=A and OPEN=J,A; After J, new=K and OPEN=A,K.
**3. Read the inspected order:** The first removals from OPEN, including a goal if reached, are F,E,J,A.
**Answer: F,E,J,A.**
**SEARCH**
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a
list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move
choices are as described in the STATE SPACE SEARCH section.
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and
opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of
corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties.
**Note:** When we say a node (a state) is inspected/expanded/refined it means: the node (the state) 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.
**Note:** RemoveSeen procedure will drop neighbours already present in 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 positions.
Enter NIL if a path to the goal is not found.
NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: 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. Run the frontier to the goal:** The inspected sequence is F → E → J → A → K → L → B → H → C.
**3. Reconstruct from parents:** Follow the goal’s first-discovery parents backward, then reverse them: F → J → K → B → C. This parent chain is the returned path; expanded dead ends need not belong to it.
**Answer: F,J,K,B,C.**
**SEARCH**
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a
list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move
choices are as described in the STATE SPACE SEARCH section.
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and
opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of
corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties.
**Note:** When we say a node (a state) is inspected/expanded/refined it means: the node (the state) 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.
**Note:** RemoveSeen procedure will drop neighbours already present in OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
List the first 4 positions inspected by Best-First Search. List the positions in the order they are
inspected. If the algorithm terminates early then list the positions inspected up until termination.
Enter a comma separated list of positions.
NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: 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 F, new=E,J and OPEN=E,J; After E, new=A and OPEN=J,A; After A, new=L and OPEN=J,L.
**3. Read the inspected order:** The first removals from OPEN, including a goal if reached, are F,E,A,L.
**Answer: F,E,A,L.**
**SEARCH**
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a
list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move
choices are as described in the STATE SPACE SEARCH section.
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and
opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of
corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties.
**Note:** When we say a node (a state) is inspected/expanded/refined it means: the node (the state) 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.
**Note:** RemoveSeen procedure will drop neighbours already present in 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 positions.
Enter NIL if a path to the goal is not found.
NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: 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. Run the frontier to the goal:** The inspected sequence is F (h=1.732) → E (h=6) → A (h=1.732) → L (h=5.196) → H (h=1.732) → G (h=4.583) → C (h=0).
**3. Reconstruct from parents:** Follow the goal’s first-discovery parents backward, then reverse them: F → E → A → L → H → G → C. This parent chain is the returned path; expanded dead ends need not belong to it.
**Answer: F,E,A,L,H,G,C.**
**SEARCH**
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a
list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move
choices are as described in the STATE SPACE SEARCH section.
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and
opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of
corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties.
**Note:** When we say a node (a state) is inspected/expanded/refined it means: the node (the state) 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.
**Note:** RemoveSeen procedure will drop neighbours already present in 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 positions.
Enter NIL if a path to the goal is not found.
NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: 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:** F (h=1.732).
**3. Test the stopping point:** At F, neighbours are E (h=6), J (h=6.245). No strictly improving move remains, and this state is not the goal C. The algorithm therefore stops without a goal path.
**Answer: NIL.**
**SEARCH**
Figure shows a gameboard with 12 positions (tiles A to L). MoveGen takes a position and returns a
list of valid knight move choices in alphabetical order, e.g., MoveGen(A) = [E,L]. Valid knight move
choices are as described in the STATE SPACE SEARCH section.
Each position is a regular hexagon with unit sides, where opposite vertices are 2 units apart and
opposite sides are sqrt(3) units apart.
Take the distance between two positions as the Euclidean Distance between the center points of
corresponding hexagons. For example, d(A,A) = 0, d(A,B) = 3, d(A,F) = sqrt(3).
There is a knight in position F and no other pieces on the board.
Take F as the start position and C as the goal position.
Use the Euclidean Distance as the heuristic function.
Use alphabetical order to break ties.
**Note:** When we say a node (a state) is inspected/expanded/refined it means: the node (the state) 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.
**Note:** RemoveSeen procedure will drop neighbours already present in OPEN or CLOSED list.
Based on the above data, answer the given subquestions.
The heuristic function for the gameboard __________ .
6406537043227.
defines a maximization problem
6406537043228.
defines a minimization problem
6406537043229.
is monotonic
6406537043230.
is non-monotonic
Published solution
**1. Identify the direction of improvement:** h(x)=d(x,C) is a remaining-distance estimate; smaller values are preferred and h(C)=0. Thus it defines a minimization objective.
**2. Check progress along legal edges:** For example, h(F)=√3≈1.732, whereas its neighbours have h(E)=6 and h(J)=√39≈6.245. A route to C therefore need not decrease h at every move.
**3. Check the unit-move consistency interpretation:** Edge G→C has unit move cost, but h(G)=√21>1+h(C). Therefore this unscaled distance is not monotone/consistent when each jump costs one.
**Answer: B, D — B and D.**
**Convention note:** The course uses “non-monotonic” for the non-improving heuristic landscape. If edge cost is physical Euclidean jump length √21 instead of one move, Euclidean distance is consistent by the triangle inequality; those are different cost conventions.
A: **Incorrect:** The goal is approached by reducing, not increasing, distance.
B: **Correct:** Distance to C is minimized at the goal.
C: **Incorrect:** It is not monotonically improving, and it fails consistency for unit-cost jumps.
D: **Correct:** The legal route can require worsening distance values.
Select the formulas that are in Conjunctive Normal Form.
6406537043231.
(A ∧ B) ∨ (¬B ∧ C) ∨ (¬D)
6406537043232.
(A
∨ B) ∧ (¬B ∨ C) ∧ (¬D)
6406537043233.
A ∧ B ∧ ¬C ∧ D
6406537043234.
A ∨ B ∨ ¬C ∨ D
6406537043235.
A ∨ (B ∧ (¬C ∨ ¬D))
Published solution
**1. Apply the syntactic CNF rule:** A conjunctive normal form is an AND of clauses, each clause being an OR of literals. A single literal is a one-literal clause, and a single clause is itself a CNF formula.
**2. Inspect the grouping:** B is an AND of three clauses, C is an AND of unit clauses, and D is one disjunction of literals. A and E have conjunctions nested inside disjunctions and are not written in CNF.
**Answer: B, C, D — B, C and D.**
A: **Incorrect:** Its outer OR combines conjunctions, so this displayed form is not CNF.
B: **Correct:** Each conjunct is a disjunction of literals.
C: **Correct:** Each literal forms a unit clause.
D: **Correct:** One clause is a valid CNF with a single conjunct.
E: **Incorrect:** It nests a conjunction inside an OR and requires distribution to become CNF.
Perturbation method(s) used for TSP tour creation is/are __________ .
6406537043236.
2-city exchange operator
6406537043237.
3-edge exchange operator
6406537043238.
single-point crossover operator
6406537043239.
Nearest Neighbour Heuristic
Published solution
**1. Distinguish perturbation from construction:** A perturbation takes an existing complete tour and changes its order or edges to generate neighbouring tours.
**2. Classify the methods:** Swapping two cities and exchanging three edges modify existing tours. Crossover recombines parents, while nearest neighbour constructs a tour by adding cities.
**Answer: A, B — A and B.**
A: **Correct:** Swapping two tour positions is a local perturbation operator.
B: **Correct:** Removing and reconnecting three tour edges is a local perturbation operator.
C: **Incorrect:** This is a recombination operator rather than the listed tour-neighbourhood perturbation.
D: **Incorrect:** This builds a tour incrementally rather than perturbing an existing one.
If a genetic algorithm prematurely converges to a homogeneous suboptimal population, then
which modification will prevent such convergence?
6406537043240.
Increasing the selection pressure.
6406537043241.
Decreasing the mutation rate.
6406537043242.
Increasing the mutation rate.
6406537043243.
Truncating low rank parents before crossover.
Published solution
**1. Identify premature convergence:** A homogeneous population has lost diversity, allowing a suboptimal region to dominate.
**2. Restore exploration:** A larger mutation rate introduces new alleles or tour variations, helping the search leave that region. Excessively high mutation can also disrupt good solutions, so this is a practical remedy rather than a universal guarantee.
**Answer: C — Increase the mutation rate.**
A: **Incorrect:** Higher selection pressure often accelerates diversity loss.
B: **Incorrect:** Lower mutation reduces the supply of new variations.
C: **Correct:** More mutation can restore diversity and reduce premature convergence.
D: **Incorrect:** Discarding lower-ranked parents can further reduce diversity.
If you initially implement Breadth-First Search using First-In-First-Out Queue and later replace the
queue with Max-Priority Queue based on node depth (larger depth equals higher priority), then
the memory footprint of the queue would __________ .
6406537043244.
drop to O(1)
6406537043245.
practically remain the same
6406537043246.
significantly decrease
6406537043247.
significantly increase
Published solution
**1. Compare expansion priorities:** FIFO BFS keeps a broad frontier across a depth level, using up to \(O(b^d)\) frontier space in a branching tree.
**2. Prioritize larger depth:** Expanding deepest available nodes produces depth-first behavior, retaining mainly the active branch and deferred siblings, typically \(O(bm)\) space to maximum depth m. Frontier memory therefore usually decreases substantially.
**Answer: C — Significantly decrease.**
**Convention note:** This is the usual finite-tree comparison, not a guarantee for every graph or tie rule. If CLOSED is retained, total graph-search memory can still be large even when OPEN shrinks.
A: **Incorrect:** Deferred siblings still require storage, so the bound is not generally O(1).
B: **Incorrect:** Breadth-first and depth-prioritized frontiers can have very different widths.
C: **Correct:** Depth-first ordering typically stores fewer simultaneous frontier nodes.
D: **Incorrect:** Depth prioritization typically reduces rather than expands the frontier.
In the Simulated Annealing schedule, if the temperature parameter T drops to absolute zero very
early in the search process, the algorithm will move from the current node N to a random
neighbour X __________ .
6406537043248.
only if N is better than X
6406537043249.
only if X is better than N
6406537043250.
unconditionally (resulting in a random walk)
Published solution
**1. Take the zero-temperature limit:** For a worse move with energy increase ΔE>0, the annealing acceptance probability \(e^{-\Delta E/T}\) tends to zero as T→0+.
**2. Interpret the resulting search:** Improving moves remain acceptable and uphill escape moves disappear, so the algorithm behaves like a greedy local search.
**Answer: B — Only if X is better than N.**
**Convention note:** Standard Metropolis implementations also accept equal-energy moves. B is the intended choice when equal-valued neighbours are excluded or the course uses strict improvement; literal “only better” omits that neutral-move case.
A: **Incorrect:** Worse neighbours are rejected in the zero-temperature limit.
B: **Correct:** This is the intended strictly-improving zero-temperature rule.
C: **Incorrect:** Unconditional random-walk behavior corresponds to very high temperature, not zero.
**TSP**
Figure shows a distance matrix for 5 cities, use it to construct TSP tours.
Based on the above data, answer the given subquestions.
Construct a tour using Nearest Neighbour Heuristic, start from city A. Enter the path
representation of the tour in the order it is constructed.
Enter a comma separated list of city names.
NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer format: A,X,Y**
Published solution
**1. Select the closest unvisited city at each step:** A: B=50, C=36, D=28, E=30; choose D; D: B=36, C=50, E=22; choose E; E: B=58, C=32; choose C; C: B=82; choose B.
**2. Close the tour:** Return from B to A at cost 50. The path representation lists each city once; this return is implicit.
**Answer: A,D,E,C,B.**
**TSP**
Figure shows a distance matrix for 5 cities, use it to construct TSP tours.
Based on the above data, answer the given subquestions.
Use city A as the base (fulcrum) city to complete the savings list then construct the Savings tour.
Enter the path representation of the tour starting from city A.
Enter a comma separated list of city names.
NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer format: A,X,Y**
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=4, BD=42, BE=22, CD=14, CE=34, DE=36.
**2. Merge by descending savings:** BD (42): merge; DE (36): merge; CE (34): 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 → D → E → C → A. The path representation omits the final repeated base.
**Answer: A,B,D,E,C.**
A major drawback of Nearest Neighbour Heuristic for TSP is __________ .
6406537043255.
it takes exponential computation time
6406537043256.
it cannot handle sparse graphs
6406537043257.
it often leaves a very long edge for the final return leg
6406537043258.
it often returns premature subtours
Published solution
**1. Track the nearest-neighbour limitation:** Every choice considers the cheapest next unvisited city, without accounting for the eventual return to the start.
**2. Identify the major quality issue:** The last city can be far from the start, leaving an expensive final edge. The direct implementation scans at most n candidates on each of n steps, giving \(O(n^2)\), not exponential time.
**Answer: C — C — an expensive final return edge.**
A: **Incorrect:** The simple implementation is quadratic rather than exponential.
B: **Incorrect:** Sparse graphs require care and may cause dead ends, but the intended standard TSP uses a complete distance graph.
C: **Correct:** Local choices can leave a costly closing edge.
D: **Incorrect:** Maintaining an unvisited set prevents a smaller completed cycle before all cities are visited.
What is the core principle used in the Savings Heuristic for TSP?
6406537043259.
Add the cheapest available edge to the tour.
6406537043260.
Maximize the distance saved in merging two subtours.
6406537043261.
Minimize the number of cities in each subtour.
6406537043262.
Sort the cities by their distance from the base/fulcrum city.
Published solution
**1. Compare separate and merged routes:** Separate base-centred routes use connections to the base from both endpoints. Joining endpoints i,j replaces two such connections with one edge i–j.
**2. Choose the best feasible merge:** Rank merges by the distance eliminated, taking the largest saving while preserving a valid tour structure.
**Answer: B — Maximize distance saved when merging subtours.**
A: **Incorrect:** The cheapest direct edge need not yield the largest reduction from base routes.
B: **Correct:** It chooses the feasible merge with the greatest saved distance.
C: **Incorrect:** Its objective is distance saved rather than a minimum city count per route.
D: **Incorrect:** Sorting distances to the base alone ignores intercity connection costs.
The savings S(a,b) for two cities a and b relative to base/fulcrum city n is __________ , where C(x,y) is
the distance between cities x and y.
6406537043263.
C(a,b) - (C(n,a) + C(n,b))
6406537043264.
(C(n,a) + C(n,b)) - 2*C(a,b)
6406537043265.
(C(n,a) * C(n,b)) / C(a,b)
6406537043266.
(C(n,a) + C(n,b)) - C(a,b)
Published solution
**1. Identify removed connections:** A merge replaces edges a–n and n–b, with total cost C(n,a)+C(n,b).
**2. Subtract the new connection:** Adding a–b costs C(a,b), so \[S(a,b)=C(n,a)+C(n,b)-C(a,b).\]
**Answer: D — \(C(n,a)+C(n,b)-C(a,b)\).**
A: **Incorrect:** This is the negative of the saving.
B: **Incorrect:** The new edge is added once, so its cost is subtracted once.
C: **Incorrect:** Savings compare additive route costs, not a ratio of their products.
D: **Correct:** It subtracts the added edge cost from the two removed base-edge costs.
