The Travelling Salesman Problem (Edexcel International AS Maths: Decision 1): Exam Questions

The table above shows the least distances, in metres, between seven classrooms, A, B, C, D, E, F and G. A teacher needs to visit each classroom, starting and finishing at A, and wishes to minimise the total distance travelled.

Show that there are two nearest neighbour routes that start from A. State these routes and their corresponding lengths.

Starting by deleting A, and all of its arcs, find a lower bound for the length of the teacher’s route.

Use your results to write down the smallest interval which you can be confident contains the optimal length of the teacher’s route.

The network in Figure 2 shows the distances, in miles, between ten towns, A, B, C, H, L, M, P, S, W and Y.

Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.

Use Prim’s algorithm on the table, starting at A, to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree.

State the weight of the minimum spanning tree found in (b).

Sharon needs to visit all of the towns, starting and finishing in the same town, and wishes to minimise the total distance she travels.

Use your answer to (c) to calculate an initial upper bound for the length of Sharon’s route.

Use the nearest neighbour algorithm on the table, starting at W, to find an upper bound for the length of Sharon’s route. Write down the route which gives this upper bound.

Using the nearest neighbour algorithm, starting at Y, an upper bound of length 212 miles was found.

State the best upper bound that can be obtained by using this information and your answers from (d) and (e). Give the reason for your answer.

By deleting W and all of its arcs, find a lower bound for the length of Sharon’s route.

Sharon decides to take the route found in (e).

Interpret this route in terms of the actual towns visited.

Figure 5 models a network of roads. The number on each edge gives the length, in km, of the corresponding road. The vertices, A, B, C, D, E, F, G and H, represent eight towns. Bronwen needs to visit each town. She will start and finish at A and wishes to minimise the total distance travelled.

By applying Dijkstra’s algorithm, starting at A, complete the table of least distances.

Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Bronwen’s route. Write down the route that gives this upper bound.

A reduced network is formed by deleting A and all arcs that are directly joined to A.

(i) Use Prim’s algorithm, starting at C, to construct a minimum spanning tree for the reduced network. You must clearly state the order in which you select the arcs of your tree.

(ii) Hence, calculate a lower bound for the length of Bronwen’s route.

Using only the results from (b) and (c), write down the smallest interval that you can be confident contains the length of Bronwen’s optimal route.

The table below represents a complete network that shows the least costs of travelling between eight cities, A, B, C, D, E, F, G and H.

Srinjoy must visit each city at least once. He will start and finish at A and wishes to minimise his total cost.

Use Prim’s algorithm, starting at A, to find a minimum spanning tree for this network. You must list the arcs that form the tree in the order in which you select them.

State the weight of the minimum spanning tree.

Use your answer to (b) to help you calculate an initial upper bound for the total cost of Srinjoy’s route.

Show that there are two nearest neighbour routes that start from A. You must make the routes and their corresponding costs clear.

State the best upper bound that can be obtained by using your answers to (c) and (d).

Starting by deleting A and all of its arcs, find a lower bound for the total cost of Srinjoy’s route. You must make your method and working clear.

Use your results to write down the smallest interval that must contain the optimal cost of Srinjoy’s route.

Figure 3 models a network of roads. The number on each edge gives the length, in km, of the corresponding road. The vertices, A, B, C, D, E, F and G, represent seven towns. Derek needs to visit each town. He will start and finish at A and wishes to minimise the total distance travelled.

By inspection, complete the two copies of the table of least distances.

Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Derek’s route. Write down the route that gives this upper bound.

Interpret the route found in (b) in terms of the towns actually visited.

Starting by deleting A and all of its arcs, find a lower bound for the route length.

Clive needs to travel along the roads to check that they are in good repair. He wishes to minimise the total distance travelled and must start at A and finish at G.

By considering the pairings of all relevant nodes, find the length of Clive’s route. State the edges that need to be traversed twice. You must make your method and working clear.

Explain the difference between the classical and the practical travelling salesperson problems.

The table below shows the distances, in km, between seven museums, A, B, C, D, E, F and G.

Fran must visit each museum. She will start and finish at A and wishes to minimise the total distance travelled.

Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the length of Fran’s route. Make your method clear.

Starting at D, a second upper bound of 203 km was found.

State whether this is a better upper bound than the answer to (b), giving a reason for your answer.

A reduced network is formed by deleting G and all the arcs that are directly joined to G.

(i) Use Prim’s algorithm, starting at A, to construct a minimum spanning tree for the reduced network. You must clearly state the order in which you select the arcs of your tree.

(ii) Hence calculate a lower bound for the length of Fran’s route.

By deleting A, a second lower bound was found to be 188 km.

State whether this is a better lower bound than the answer to (d)(ii), giving a reason for your answer.

Using only the results from (c) and (e), write down the smallest interval that you can be confident contains the length of Fran’s optimal route.

The table below shows the least distances, in km, between six towns, A, B, C, D, E and F.

Mei must visit each town at least once. She will start and finish at A and wishes her route to minimise the total distance she will travel.

Starting with the minimum spanning tree below, use the shortcut method to find an upper bound below 520 km for Mei’s route. You must state the shortcut(s) you use and the length of your upper bound.

Use the nearest neighbour algorithm, starting at A, to find another upper bound for the length of Mei’s route.

Starting by deleting E, and all of its arcs, find a lower bound for the length of Mei’s route. Make your method clear.

The table below shows the distances, in km, between six data collection points, A, B, C, D, E and F.

Ferhana must visit each data collection point. She will start and finish at A and wishes to minimise the total distance she travels.

Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the distance Ferhana must travel. Make your method clear.

Starting by deleting B, and all of its arcs, find a lower bound for the distance Ferhana must travel. Make your calculation clear.

The table above shows the least distances, in km, between six cities, A, B, C, D, E and F. Mohsen needs to visit each city, starting and finishing at A, and wishes to minimise the total distance he will travel.

Starting at A, use the nearest neighbour algorithm to obtain an upper bound for the length of Mohsen’s route. You must state your route and its length.

Starting by deleting A and all of its arcs, find a lower bound for the length of Mohsen’s route.

Use your answers from (a) and (b) to write down the smallest interval that you can be confident contains the optimal length of the route.