Login or Create an Account to view the mark scheme (answer), comment, and add to a test
The decision version of the travelling salesman problem asks: given a weighted, undirected graph and a source node, does there exist a path starting and finishing at the source node that visits all remaining nodes exactly once and has a total weight of less than X (where X is a given integer)?
(a).
Explain why the decision version of the travelling salesman problem is in NP.
[2](b).
Describe a greedy approach to solving the travelling salesman problem.
[2](c).
An alternative approach to solving the travelling salesman problem is to use a simulated annealing algorithm. The greedy approach described in can be used to generate an initial candidate solution for the simulated annealing algorithm. High-level pseudocode for the simulated annealing algorithm is provided below.
Generate initial candidate solution, S
Repeat until a terminating condition is reached:
Generate a new candidate solution, S_new
Set a temperature, T
If the new candidate solution is accepted:
Set S = S_new
Return S
(i).
Explain how the algorithm would determine whether a new candidate solution is accepted.
[3](ii).
State a terminating condition that could be used for this algorithm.
[2](iii).
Describe one advantage and one limitation of using a simulated annealing algorithm to solve the travelling salesman problem.
[2]
Extended Response11 MarksShared
0 Uses1 View0 Likes