cs3003_2026T1_Q1_NA.pdf
AI: Search Methods for Problem Solving · Quiz 1 · Jan 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:96bc6948e82e236e_3_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 NAT · 1.0 marks
**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.
[[IMAGE:96bc6948e82e236e_4_3]]
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
[[IMAGE:96bc6948e82e236e_4_4]]
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**
A published solution is not available for this question yet.
Question 4 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:96bc6948e82e236e_4_3]]
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
[[IMAGE:96bc6948e82e236e_4_4]]
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**
A published solution is not available for this question yet.
Question 5 NAT · 1.0 marks
**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.
[[IMAGE:96bc6948e82e236e_4_3]]
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
[[IMAGE:96bc6948e82e236e_4_4]]
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**
A published solution is not available for this question yet.
Question 6 MCQ · 1.0 marks
**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.
[[IMAGE:96bc6948e82e236e_4_3]]
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
[[IMAGE:96bc6948e82e236e_4_4]]
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.
Some knight-moves are reversible.
Some knight-moves are not reversible.
Every knight-move is reversible.
Every knight-move is not reversible.
A published solution is not available for this question yet.
Question 7 MSQ · 1.0 marks
**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.
[[IMAGE:96bc6948e82e236e_4_3]]
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
[[IMAGE:96bc6948e82e236e_4_4]]
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.
At least one state has no path from another state.
Every state has a path to every other state.
Every state has at most three neighbours.
Every state has eight neighbours.
A published solution is not available for this question yet.
Question 8 MCQ · 1.0 marks
**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.
[[IMAGE:96bc6948e82e236e_4_3]]
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
[[IMAGE:96bc6948e82e236e_4_4]]
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?
Yes
No
Cannot be determined
A published solution is not available for this question yet.
Question 9 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:96bc6948e82e236e_7_5]]
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
[[IMAGE:96bc6948e82e236e_7_6]]
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**
A published solution is not available for this question yet.
Question 10 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:96bc6948e82e236e_7_5]]
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
[[IMAGE:96bc6948e82e236e_7_6]]
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**
A published solution is not available for this question yet.
Question 11 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:96bc6948e82e236e_7_5]]
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
[[IMAGE:96bc6948e82e236e_7_6]]
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**
A published solution is not available for this question yet.
Question 12 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:96bc6948e82e236e_7_5]]
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
[[IMAGE:96bc6948e82e236e_7_6]]
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**
A published solution is not available for this question yet.
Question 13 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:96bc6948e82e236e_7_5]]
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
[[IMAGE:96bc6948e82e236e_7_6]]
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**
A published solution is not available for this question yet.
Question 14 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:96bc6948e82e236e_7_5]]
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
[[IMAGE:96bc6948e82e236e_7_6]]
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**
A published solution is not available for this question yet.
Question 15 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:96bc6948e82e236e_7_5]]
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
[[IMAGE:96bc6948e82e236e_7_6]]
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**
A published solution is not available for this question yet.
Question 16 SHORT_TEXT · 1.0 marks
**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.
[[IMAGE:96bc6948e82e236e_7_5]]
**Problem Statement:**
Consider a 4x3 chessboard where the allowable positions are marked by alphabets.
[[IMAGE:96bc6948e82e236e_7_6]]
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**
A published solution is not available for this question yet.
Question 17 MSQ · 1.0 marks
**Algorithms**
Based on the topic, answer the given subquestions.
Which of the following algorithms are designed to escape local minima?
Hill Climbing
Iterated Hill Climbing
Nearest Neighbour Heuristic for TSP
Tabu Search
A published solution is not available for this question yet.
Question 18 MSQ · 1.0 marks
**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).
When T tends to INF, the probability of choosing good moves increases.
When T tends to INF, the probability of choosing bad moves decreases.
When T tends to 0, the probability of choosing good moves increases.
When T tends to 0, the probability of choosing bad moves decreases.
A published solution is not available for this question yet.
Question 19 NAT · 1.0 marks
**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**
A published solution is not available for this question yet.
Question 20 NAT · 1.0 marks
**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**
A published solution is not available for this question yet.
Question 21 SHORT_TEXT · 1.0 marks
**TSP**
Use the distance matrix (and the sorted edge list) to construct TSP tours.
[[IMAGE:96bc6948e82e236e_13_7]]
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**
A published solution is not available for this question yet.
Question 22 SHORT_TEXT · 1.0 marks
**TSP**
Use the distance matrix (and the sorted edge list) to construct TSP tours.
[[IMAGE:96bc6948e82e236e_13_7]]
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”.
[[IMAGE:96bc6948e82e236e_14_8]]
Enter a comma separated list of city names.
NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS.
**Answer format: A,X,Y,Z**
A published solution is not available for this question yet.
Question 23 NAT · 1.0 marks
**TSP**
Use the distance matrix (and the sorted edge list) to construct TSP tours.
[[IMAGE:96bc6948e82e236e_13_7]]
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**
A published solution is not available for this question yet.
Question 24 SHORT_TEXT · 1.0 marks
**TSP**
Use the distance matrix (and the sorted edge list) to construct TSP tours.
[[IMAGE:96bc6948e82e236e_13_7]]
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**
A published solution is not available for this question yet.
Question 25 MSQ · 1.0 marks
**TSP**
Use the distance matrix (and the sorted edge list) to construct TSP tours.
[[IMAGE:96bc6948e82e236e_13_7]]
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?
This procedure will always return the optimal TSP tour.
This procedure will not always return the optimal TSP tour.
This procedure may not always terminate.
This procedure will always terminate.
A published solution is not available for this question yet.