cs3003_2026T2_Q1_NA.pdf
AI: Search Methods for Problem Solving · Quiz 1 · May 2026
← Course papers · Start practice / exam
Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
Question 2 MSQ · 0.0 marks
[[IMAGE:840dc7aa919a83cd_2_2]]
Printed graph sheets were provided on time.
Printed graph sheets were provided late.
Printed graph sheets were not provided.
I used the graph sheets.
I did not use graph sheets.
A published solution is not available for this question yet.
Question 3 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:840dc7aa919a83cd_3_3]]
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].
[[IMAGE:840dc7aa919a83cd_3_4]]
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.
A published solution is not available for this question yet.
Question 4 NAT · 1.0 marks
**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.
[[IMAGE:840dc7aa919a83cd_3_3]]
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].
[[IMAGE:840dc7aa919a83cd_3_4]]
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**
A published solution is not available for this question yet.
Question 5 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:840dc7aa919a83cd_3_3]]
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].
[[IMAGE:840dc7aa919a83cd_3_4]]
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**
A published solution is not available for this question yet.
Question 6 NAT · 1.0 marks
**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.
[[IMAGE:840dc7aa919a83cd_3_3]]
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].
[[IMAGE:840dc7aa919a83cd_3_4]]
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**
A published solution is not available for this question yet.
Question 7 MSQ · 1.0 marks
**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.
[[IMAGE:840dc7aa919a83cd_3_3]]
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].
[[IMAGE:840dc7aa919a83cd_3_4]]
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.)
At least one state has no path from another state.
Every state has a path to every other state.
Every state has at most two neighbours.
Every state has at least 12 neighbours.
A published solution is not available for this question yet.
Question 8 MCQ · 1.0 marks
**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.
[[IMAGE:840dc7aa919a83cd_3_3]]
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].
[[IMAGE:840dc7aa919a83cd_3_4]]
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?
Yes
No
Cannot be determined
A published solution is not available for this question yet.
Question 9 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:840dc7aa919a83cd_6_5]]
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**
A published solution is not available for this question yet.
Question 10 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:840dc7aa919a83cd_6_5]]
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**
A published solution is not available for this question yet.
Question 11 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:840dc7aa919a83cd_6_5]]
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**
A published solution is not available for this question yet.
Question 12 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:840dc7aa919a83cd_6_5]]
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**
A published solution is not available for this question yet.
Question 13 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:840dc7aa919a83cd_6_5]]
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**
A published solution is not available for this question yet.
Question 14 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:840dc7aa919a83cd_6_5]]
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**
A published solution is not available for this question yet.
Question 15 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:840dc7aa919a83cd_6_5]]
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**
A published solution is not available for this question yet.
Question 16 MSQ · 1.0 marks
**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.
[[IMAGE:840dc7aa919a83cd_6_5]]
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 __________ .
defines a maximization problem
defines a minimization problem
is monotonic
is non-monotonic
A published solution is not available for this question yet.
Question 17 MSQ · 1.0 marks
**ALGORITHMS**
Answer the given subquestions.
Select the formulas that are in Conjunctive Normal Form.
(A ∧ B) ∨ (¬B ∧ C) ∨ (¬D)
(A
∨ B) ∧ (¬B ∨ C) ∧ (¬D)
A ∧ B ∧ ¬C ∧ D
A ∨ B ∨ ¬C ∨ D
A ∨ (B ∧ (¬C ∨ ¬D))
A published solution is not available for this question yet.
Question 18 MSQ · 1.0 marks
**ALGORITHMS**
Answer the given subquestions.
Perturbation method(s) used for TSP tour creation is/are __________ .
2-city exchange operator
3-edge exchange operator
single-point crossover operator
Nearest Neighbour Heuristic
A published solution is not available for this question yet.
Question 19 MCQ · 1.0 marks
**ALGORITHMS**
Answer the given subquestions.
If a genetic algorithm prematurely converges to a homogeneous suboptimal population, then
which modification will prevent such convergence?
Increasing the selection pressure.
Decreasing the mutation rate.
Increasing the mutation rate.
Truncating low rank parents before crossover.
A published solution is not available for this question yet.
Question 20 MCQ · 1.0 marks
**ALGORITHMS**
Answer the given subquestions.
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 __________ .
drop to O(1)
practically remain the same
significantly decrease
significantly increase
A published solution is not available for this question yet.
Question 21 MCQ · 1.0 marks
**ALGORITHMS**
Answer the given subquestions.
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 __________ .
only if N is better than X
only if X is better than N
unconditionally (resulting in a random walk)
A published solution is not available for this question yet.
Question 22 MCQ · 1.0 marks
**TSP**
Figure shows a distance matrix for 5 cities, use it to construct TSP tours.
[[IMAGE:840dc7aa919a83cd_12_6]]
Based on the above data, answer the given subquestions.
The given TSP is a __________ . (CAUTION: May require bull work.)
Euclidean TSP
non Euclidean TSP
A published solution is not available for this question yet.
Question 23 SHORT_TEXT · 1.0 marks
**TSP**
Figure shows a distance matrix for 5 cities, use it to construct TSP tours.
[[IMAGE:840dc7aa919a83cd_12_6]]
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**
A published solution is not available for this question yet.
Question 24 SHORT_TEXT · 1.0 marks
**TSP**
Figure shows a distance matrix for 5 cities, use it to construct TSP tours.
[[IMAGE:840dc7aa919a83cd_12_6]]
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.
[[IMAGE:840dc7aa919a83cd_13_7]]
Enter a comma separated list of city names.
NO SPACES, TABS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer format: A,X,Y**
A published solution is not available for this question yet.
Question 25 MSQ · 1.0 marks
**TSP ALGORITHMS**
Answer the given subquestions.
A major drawback of Nearest Neighbour Heuristic for TSP is __________ .
it takes exponential computation time
it cannot handle sparse graphs
it often leaves a very long edge for the final return leg
it often returns premature subtours
A published solution is not available for this question yet.
Question 26 MSQ · 1.0 marks
**TSP ALGORITHMS**
Answer the given subquestions.
What is the core principle used in the Savings Heuristic for TSP?
Add the cheapest available edge to the tour.
Maximize the distance saved in merging two subtours.
Minimize the number of cities in each subtour.
Sort the cities by their distance from the base/fulcrum city.
A published solution is not available for this question yet.
Question 27 MCQ · 1.0 marks
**TSP ALGORITHMS**
Answer the given subquestions.
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.
C(a,b) - (C(n,a) + C(n,b))
(C(n,a) + C(n,b)) - 2*C(a,b)
(C(n,a) * C(n,b)) / C(a,b)
(C(n,a) + C(n,b)) - C(a,b)
A published solution is not available for this question yet.