Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
24 / 24 published solutions
Question 2 MSQ · 0.0 marks
6406536373396.
Printed graph sheets were provided on time.
6406536373397.
Printed graph sheets were provided late.
6406536373398.
Printed graph sheets were not provided.
6406536373399.
I used the graph sheets.
6406536373400.
I did not use graph sheets.
Published solution
**1. Identify the item:** This zero-mark entry reports availability and use of printed graph sheets. It has no independently derivable academic answer; the supplied key selects “provided on time” and “used.”
**Answer: A, D — A and D — supplied administrative responses.**
**Convention note:** These responses are retained as metadata, not asserted as a particular candidate’s personal experience.
A: **Correct:** Selected as the source’s availability response.
B: **Incorrect:** Not the timing response recorded by the source key.
C: **Incorrect:** Contradicts the keyed availability response.
D: **Correct:** Selected as the source’s usage response.
E: **Incorrect:** Contradicts the keyed usage response.
**STATE SPACE SEARCH**
**Background:**
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite
corner of that rectangle and there are eight possible jumps (moves) for a knight.
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
From an allowable position, a knight can jump over obstacles and land on another allowable
position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for
example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the
unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
Compute the MoveGen function and then answer the sub-questions.
The number of unique states in the state space is __________ .
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: 42**
Published solution
**1. Represent the knight by its square:** The ten allowed squares are A,B,C,D,E,F,G,H,I,J. The two grey squares cannot be occupied.
**2. Count distinct states:** One allowed current-square label gives one state, so the state-space size is 10.
**Answer: 10.**
**STATE SPACE SEARCH**
**Background:**
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite
corner of that rectangle and there are eight possible jumps (moves) for a knight.
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
From an allowable position, a knight can jump over obstacles and land on another allowable
position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for
example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the
unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
Compute the MoveGen function and then answer the sub-questions.
MoveGen(C) is __________ .
Enter a comma separated list of positions.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: A,B,C,D**
Published solution
**1. Apply knight displacements:** A legal move has coordinate offset \((\pm1,\pm2)\) or \((\pm2,\pm1)\). Take C=(2,0) in the four-column board.
**2. Keep allowed landing squares:** E=(0,1), H=(1,2) and J=(3,2) are valid landings. The other five potential offsets leave the board or miss an allowed square. Alphabetical order gives E,H,J.
**Answer: E,H,J.**
**STATE SPACE SEARCH**
**Background:**
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite
corner of that rectangle and there are eight possible jumps (moves) for a knight.
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
From an allowable position, a knight can jump over obstacles and land on another allowable
position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for
example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the
unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
Compute the MoveGen function and then answer the sub-questions.
d(G,D) 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 coordinate differences:** G is at (0,2) and D at (3,0), so the horizontal and vertical differences have magnitudes 3 and 2.
**2. Calculate distance:** \(d(G,D)=\sqrt{3^2+2^2}=\sqrt{13}\approx3.605551\), rounding to 3.6.
**Answer: 3.6.**
**STATE SPACE SEARCH**
**Background:**
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite
corner of that rectangle and there are eight possible jumps (moves) for a knight.
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
From an allowable position, a knight can jump over obstacles and land on another allowable
position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for
example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the
unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
Compute the MoveGen function and then answer the sub-questions.
Select the true statement about knight moves in the given state space.
6406536373404.
Some knight-moves are reversible.
6406536373405.
Some knight-moves are not reversible.
6406536373406.
Every knight-move is reversible.
6406536373407.
Every knight-move is not reversible.
Published solution
**1. Reverse a knight displacement:** Negating \((\pm1,\pm2)\) or \((\pm2,\pm1)\) gives another legal knight displacement. Both endpoint squares remain allowed.
**2. Generalize:** Every legal move can therefore be reversed, not merely a special subset of moves.
**Answer: C — Every knight-move is reversible.**
**Convention note:** “Some moves are reversible” is logically true as well if “some” means at least one. C is the strongest complete answer; A is only false if “some” is intended to mean “some but not all.”
A: **Incorrect:** Existentially true, but less complete than the universal statement C intended in this single-choice question.
B: **Incorrect:** There are no one-way knight jumps in this board.
C: **Correct:** Every legal jump has the reverse legal jump.
D: **Incorrect:** This contradicts the symmetry of the displacement rule.
**STATE SPACE SEARCH**
**Background:**
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite
corner of that rectangle and there are eight possible jumps (moves) for a knight.
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
From an allowable position, a knight can jump over obstacles and land on another allowable
position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for
example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the
unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
Compute the MoveGen function and then answer the sub-questions.
Select the true statements about the given state space.
6406536373408.
At least one state has no path from another state.
6406536373409.
Every state has a path to every other state.
6406536373410.
Every state has at most three neighbours.
6406536373411.
Every state has eight neighbours.
Published solution
**1. List degrees from legal moves:** A,D,G,J each have one neighbour; E,F have two; B,C,H,I have three. The adjacency links connect all ten allowed squares into one component.
**2. Translate to statements:** Every state can reach every other state, and no degree exceeds three. Board boundaries and blocked landing squares reduce the theoretical eight jumps.
**Answer: B, C — B and C.**
A: **Incorrect:** The graph has one connected component.
B: **Correct:** All ten allowed positions are mutually reachable.
C: **Correct:** The largest degree is three.
D: **Incorrect:** Several states have just one neighbour, not eight.
**STATE SPACE SEARCH**
**Background:**
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite
corner of that rectangle and there are eight possible jumps (moves) for a knight.
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
From an allowable position, a knight can jump over obstacles and land on another allowable
position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for
example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the
unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
Compute the MoveGen function and then answer the sub-questions.
In the given state space, is it possible for a knight to start from a position and visit the remaining
positions exactly once and return to the starting position to form a knight’s tour?
6406536373412.
Yes
6406536373413.
No
6406536373414.
Cannot be determined
Published solution
**1. Use a necessary Hamiltonian-cycle condition:** In a closed tour visiting every vertex exactly once, each vertex needs two distinct incident tour edges.
**2. Find a counterexample:** A has only neighbour H, and G only neighbour B. A tour cannot enter and leave such a vertex without reusing its only neighbour, so the required knight tour is impossible.
**Answer: B — No.**
A: **Incorrect:** Degree-one vertices prevent a cycle through all positions.
B: **Correct:** At least one degree-one vertex suffices to rule out the closed tour.
C: **Incorrect:** The legal-move graph provides a definitive answer.
**SEARCH**
**Background:**
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite
corner of that rectangle and there are eight possible jumps (moves) for a knight.
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
From an allowable position, a knight can jump over obstacles and land on another allowable
position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for
example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the
unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard.
Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
**Note:** when we say a node (or a position) is inspected/expanded/refined it means: the node (or
position) 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 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 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, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: A,B,C,D**
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 A, new=H and OPEN=H; After H, new=C,F and OPEN=C,F; After C, new=E,J and OPEN=E,J,F.
**3. Read the inspected order:** The first removals from OPEN, including a goal if reached, are A,H,C,E.
**Answer: A,H,C,E.**
**SEARCH**
**Background:**
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite
corner of that rectangle and there are eight possible jumps (moves) for a knight.
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
From an allowable position, a knight can jump over obstacles and land on another allowable
position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for
example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the
unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard.
Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
**Note:** when we say a node (or a position) is inspected/expanded/refined it means: the node (or
position) 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 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 positions.
Enter NIL if a path to the goal is not found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: A,B,C,D**
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 A → H → C → E → I → B → G.
**3. Reconstruct from parents:** Follow the goal’s first-discovery parents backward, then reverse them: A → H → C → E → I → B → G. This parent chain is the returned path; expanded dead ends need not belong to it.
**Answer: A,H,C,E,I,B,G.**
**SEARCH**
**Background:**
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite
corner of that rectangle and there are eight possible jumps (moves) for a knight.
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
From an allowable position, a knight can jump over obstacles and land on another allowable
position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for
example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the
unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard.
Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
**Note:** when we say a node (or a position) is inspected/expanded/refined it means: the node (or
position) 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 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 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, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: A,B,C,D**
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 A, new=H and OPEN=H; After H, new=C,F and OPEN=C,F; After C, new=E,J and OPEN=F,E,J.
**3. Read the inspected order:** The first removals from OPEN, including a goal if reached, are A,H,C,F.
**Answer: A,H,C,F.**
**SEARCH**
**Background:**
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite
corner of that rectangle and there are eight possible jumps (moves) for a knight.
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
From an allowable position, a knight can jump over obstacles and land on another allowable
position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for
example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the
unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard.
Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
**Note:** when we say a node (or a position) is inspected/expanded/refined it means: the node (or
position) 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 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 positions.
Enter NIL if a path to the goal is not found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: A,B,C,D**
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 A → H → C → F → E → J → B → I → G.
**3. Reconstruct from parents:** Follow the goal’s first-discovery parents backward, then reverse them: A → H → F → B → G. This parent chain is the returned path; expanded dead ends need not belong to it.
**Answer: A,H,F,B,G.**
**SEARCH**
**Background:**
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite
corner of that rectangle and there are eight possible jumps (moves) for a knight.
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
From an allowable position, a knight can jump over obstacles and land on another allowable
position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for
example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the
unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard.
Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
**Note:** when we say a node (or a position) is inspected/expanded/refined it means: the node (or
position) 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 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 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, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: A,B,C,D**
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 A, new=H and OPEN=H; After H, new=C,F and OPEN=C,F; After C, new=E,J and OPEN=F,E,J.
**3. Read the inspected order:** The first removals from OPEN, including a goal if reached, are A,H,C,E.
**Answer: A,H,C,E.**
**SEARCH**
**Background:**
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite
corner of that rectangle and there are eight possible jumps (moves) for a knight.
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
From an allowable position, a knight can jump over obstacles and land on another allowable
position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for
example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the
unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard.
Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
**Note:** when we say a node (or a position) is inspected/expanded/refined it means: the node (or
position) 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 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 positions.
Enter NIL if a path to the goal is not found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: A,B,C,D**
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 A (h=2) → H (h=1) → C (h=2.828) → E (h=1) → I (h=2) → B (h=2.236) → G (h=0).
**3. Reconstruct from parents:** Follow the goal’s first-discovery parents backward, then reverse them: A → H → C → E → I → B → G. This parent chain is the returned path; expanded dead ends need not belong to it.
**Answer: A,H,C,E,I,B,G.**
**SEARCH**
**Background:**
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite
corner of that rectangle and there are eight possible jumps (moves) for a knight.
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
From an allowable position, a knight can jump over obstacles and land on another allowable
position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for
example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the
unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard.
Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
**Note:** when we say a node (or a position) is inspected/expanded/refined it means: the node (or
position) 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 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 positions inspected by Hill Climbing. 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, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: A,B,C,D**
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:** A (h=2) → H (h=1).
**3. Test the stopping point:** At H, neighbours are A (h=2), C (h=2.828), F (h=3.162). No strictly improving move remains, and this state is not the goal G. The algorithm therefore stops without a goal path.
**Answer: A,H.**
**SEARCH**
**Background:**
On a chessboard, a knight can jump from one corner of a 2x3 (or 3x2) rectangle to the opposite
corner of that rectangle and there are eight possible jumps (moves) for a knight.
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
From an allowable position, a knight can jump over obstacles and land on another allowable
position.
MoveGen takes a position as input and returns an alphabetically ordered list of knight-moves, for
example, MoveGen(B) = [F,G,I].
The distance between two positions is equal to the Euclidean Distance between the centers of the
unit squares (positions), for example, d(A,A) = 0, d(A,B) = 1, d(A,H) = sqrt(5) and so on.
There is a knight in position A and no other pieces on the chessboard.
Take A as the start position and G as the goal position.
Use alphabetical order to break ties.
Use the Euclidean Distance as the heuristic function.
**Note:** when we say a node (or a position) is inspected/expanded/refined it means: the node (or
position) 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 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 positions.
Enter NIL if a path to the goal is not found.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: A,B,C,D**
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:** A (h=2) → H (h=1).
**3. Test the stopping point:** At H, neighbours are A (h=2), C (h=2.828), F (h=3.162). No strictly improving move remains, and this state is not the goal G. The algorithm therefore stops without a goal path.
**Answer: NIL.**
**Algorithms**
Based on the topic, answer the given subquestions.
Which of the following algorithms are designed to escape local minima?
6406536373423.
Hill Climbing
6406536373424.
Iterated Hill Climbing
6406536373425.
Nearest Neighbour Heuristic for TSP
6406536373426.
Tabu Search
Published solution
**1. Identify a local trap:** Ordinary hill climbing stops when no improving neighbouring state exists. It does not retain a mechanism for leaving that local optimum.
**2. Compare escape mechanisms:** Iterated hill climbing restarts or perturbs the current solution; tabu search can take non-improving moves while using memory to avoid cycling. Nearest neighbour is a constructive tour heuristic, not an escape method.
**Answer: B, D — B and D.**
A: **Incorrect:** Plain hill climbing can remain stuck at a local optimum.
B: **Correct:** Restarting or perturbing gives repeated opportunities to escape a local basin.
C: **Incorrect:** It constructs a tour rather than escaping a complete solution’s local minimum.
D: **Correct:** Its memory and non-improving moves support exploration beyond local minima.
**Algorithms**
Based on the topic, answer the given subquestions.
Stochastic Hill Climbing decides whether to move from N to a randomly selected neighbour x
based on the probability function P = 1/(1+e^(-deltaE/T)), where T is a non negative temperature
parameter, and deltaE = eval(x) - eval(N) for maximization problems where a positive deltaE
indicates that x is better than N. Select the correct statement(s).
6406536373427.
When T tends to INF, the probability of choosing good moves increases.
6406536373428.
When T tends to INF, the probability of choosing bad moves decreases.
6406536373429.
When T tends to 0, the probability of choosing good moves increases.
6406536373430.
When T tends to 0, the probability of choosing bad moves decreases.
Published solution
**1. Hold the move quality fixed:** \(P=1/(1+e^{-\Delta E/T})\), with ΔE>0 for a good move and ΔE<0 for a bad move.
**2. Take the limits:** As T→∞, both good- and bad-move acceptance probabilities approach 1/2. As T→0+, good-move probability approaches 1 and bad-move probability approaches 0.
**Answer: C, D — C and D.**
**Convention note:** At ΔE=0, acceptance is 1/2 for every positive T. T=0 itself is interpreted through a limit rather than direct division.
A: **Incorrect:** For a fixed good move, increasing T moves its probability down toward 1/2.
B: **Incorrect:** For a fixed bad move, increasing T moves its probability up toward 1/2.
C: **Correct:** Lower T raises the acceptance probability of a good move toward 1.
D: **Correct:** Lower T lowers the acceptance probability of a bad move toward 0.
**Algorithms**
Based on the topic, answer the given subquestions.
What is the total number of tours possible for 4 cities?
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: 17**
Published solution
**1. Remove rotational duplication:** Fix one of the four cities as the start. The remaining cities have \((4-1)!=6\) orders.
**2. Identify reverse directions:** For symmetric TSP, a cycle and its reversal are the same tour. Thus \((4-1)!/2=6/2=3\) distinct undirected tours.
**Answer: 3.**
**Algorithms**
Based on the topic, answer the given subquestions.
Given a 4-city tour as input, how many **unique tours (unique neighbours)** will be generated by a
MoveGen using the 2-city exchange operator?
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer Format: 17**
Published solution
**1. Enumerate the possible undirected cycles:** With A fixed, the three distinct four-city tours can be represented by ABCD, ABDC and ACBD.
**2. Apply city swaps to one cycle:** The four adjacent-position swaps collapse to the two other undirected cycles. Swapping opposite positions produces the original cycle in reverse; those unchanged undirected tours are excluded.
**3. Count unique neighbours:** There are two distinct neighbouring tours, excluding the original.
**Answer: 2.**
**Convention note:** This counts symmetric cycles up to rotation and reversal, not the number of distinct raw permutations or swap operations.
**TSP**
Use the distance matrix (and the sorted edge list) to construct TSP tours.
Based on the above data, answer the given subquestions.
Construct a tour using Greedy Heuristic. Enter the path representation of the 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. Use sorted edges with feasibility checks:** Accept an edge only if no city’s degree exceeds 2 and no cycle forms before all cities can be included.
**2. Process the edge list:** DE (12): accept; CD (18): accept; CE (24): skip, premature cycle; BD (30): skip, degree limit; BC (42): accept; BE (54): skip, premature cycle; AE (66): accept; AC (78): skip, degree limit; AD (84): skip, degree limit; AB (96): accept.
**3. Trace the accepted cycle:** A → B → C → D → E → A. Rotating the starting city or reversing direction represents the same undirected tour.
**Answer: A,B,C,D,E.**
**TSP**
Use the distance matrix (and the sorted edge list) to construct TSP tours.
Based on the above data, answer the given subquestions.
Use city “A” as the fulcrum (base) node and complete the given savings list then construct the
Savings tour. Enter the path representation of the 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=132, BD=150, BE=108, CD=144, CE=120, DE=138.
**2. Merge by descending savings:** BD (150): merge; CD (144): merge; DE (138): skip, interior endpoint; BC (132): skip, premature cycle; CE (120): 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 → C → E → A. The path representation omits the final repeated base.
**Answer: A,B,D,C,E.**
**TSP**
Use the distance matrix (and the sorted edge list) to construct TSP tours.
Based on the above data, answer the given subquestions.
What is the cost of the tour generated by Savings Heuristic?
Enter an integer.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer format: 17**
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=132, BD=150, BE=108, CD=144, CE=120, DE=138.
**2. Merge by descending savings:** BD (150): merge; CD (144): merge; DE (138): skip, interior endpoint; BC (132): skip, premature cycle; CE (120): 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 → C → E → A. The path representation omits the final repeated base.
**4. Add its edges:** 96+30+18+24+66=234.
**Answer: 234.**
**TSP**
Use the distance matrix (and the sorted edge list) to construct TSP tours.
Based on the above data, answer the given subquestions.
Consider N cities on the Euclidean plane, how many merge operations will be performed while
constructing the Savings tour?
Enter an expression in the textbox.
**Answer format: 2x^2 - 3x + 1**
Published solution
**1. Count the initial subtours:** With one base city, each of the other N−1 cities initially forms its own base–city–base route.
**2. Reduce to one tour:** Each accepted merge combines two routes and reduces their count by one. Going from N−1 routes to one therefore takes \((N-1)-1=N-2\) merge operations.
**Answer: N-2.**
**TSP**
Use the distance matrix (and the sorted edge list) to construct TSP tours.
Based on the above data, answer the given subquestions.
Consider N cities on the Euclidean plane, for each city, begin at that city and compute a tour using
Nearest Neighbour Heuristic. From the resulting N tours, select the cheapest tour. What can you
conclude about the procedure?
6406536373437.
This procedure will always return the optimal TSP tour.
6406536373438.
This procedure will not always return the optimal TSP tour.
6406536373439.
This procedure may not always terminate.
6406536373440.
This procedure will always terminate.
Published solution
**1. Check termination:** On a finite complete N-city instance, each nearest-neighbour run adds one previously unvisited city until all are included. Running it from every start is still finite, with a direct implementation costing \(O(N^3)\).
**2. Check optimality:** Trying every starting city improves the candidate set, but each run still commits to greedy local choices. Selecting the cheapest of these N tours does not exhaust all tours or guarantee the optimum.
**Answer: B, D — B and D.**
A: **Incorrect:** Different starting cities do not remove the greedy heuristic’s lack of an optimality guarantee.
B: **Correct:** The best of the N greedy tours can still be suboptimal.
C: **Incorrect:** Finite runs over a finite complete distance matrix terminate.
D: **Correct:** Each run visits at most N cities, and only N runs are made.
