AQA D1 2007 June — Question 6

Exam BoardAQA
ModuleD1 (Decision Mathematics 1)
Year2007
SessionJune
TopicTravelling Salesman
6
  1. Mark is staying at the Grand Hotel ( \(G\) ) in Oslo. He is going to visit four famous places in Oslo: Aker Brygge ( \(A\) ), the National Theatre ( \(N\) ), Parliament House ( \(P\) ) and the Royal Palace ( \(R\) ). The figures in the table represent the walking times, in seconds, between the places.
    Grand Hotel ( \(G\) )Aker Brygge (A)National Theatre ( \(N\) )Parliament House (P)Royal Palace (R)
    Grand Hotel ( \(G\) )-16518565160
    Aker Brygge (A)165-155115275
    National Theatre ( \(N\) )185155-205125
    Parliament House (P)65115205-225
    Royal Palace (R)160275125225-
    Mark is to start his tour from the Grand Hotel, visiting each place once before returning to the Grand Hotel. Mark wishes to keep his walking time to a minimum.
    1. Use the nearest neighbour algorithm, starting from the Grand Hotel, to find an upper bound for the walking time for Mark's tour.
    2. By deleting the Grand Hotel, find a lower bound for the walking time for Mark's tour.
    3. The walking time for an optimal tour is \(T\) seconds. Use your answers to parts (a)(i) and (a)(ii) to write down a conclusion about \(T\).
  2. Mark then intends to start from the Grand Hotel ( \(G\) ), visit three museums, Ibsen ( \(I\) ), Munch ( \(M\) ) and Viking ( \(V\) ), and return to the Grand Hotel. He uses public transport. The table shows the minimum travelling times, in minutes, between the places.
    \backslashbox{From}{To}Grand Hotel ( \(G\) )Ibsen (I)Munch ( \(M\) )Viking ( \(\boldsymbol { V }\) )
    Grand Hotel ( \(\boldsymbol { G }\) )-201730
    Ibsen (I)15-3216
    Munch (M)2618-21
    Viking ( \(\boldsymbol { V }\) )192724-
    1. Find the length of the tour \(G I M V G\).
    2. Find the length of the tour GVMIG.
    3. Find the number of different possible tours for Mark.
    4. Write down the number of different possible tours for Mark if he were to visit \(n\) museums, starting and finishing at the Grand Hotel.
This paper (6 questions)
View full paper
Q1 Q2 Q3 Q4 Q5 Q6