AQA D1 2014 June — Question 6 4 marks

Exam BoardAQA
ModuleD1 (Decision Mathematics 1)
Year2014
SessionJune
Marks4
TopicTravelling Salesman
6
  1. Sarah is solving a travelling-salesman problem.
    1. She finds the following upper bounds: \(32,33,32,32,30,32,32\). Write down the best upper bound.
    2. She finds the following lower bounds: 17, 18, 17, 20, 18, 17, 20. Write down the best lower bound.
  2. Rob is travelling by train to a number of cities. He is to start at \(M\) and visit each other city at least once before returning to \(M\). The diagram shows the travelling times, in minutes, between cities. Where no time is shown, there is no direct journey available.
    \includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-16_959_1122_1059_443} The table below shows the minimum travelling times between all pairs of cities.
    \cline { 2 - 6 } \multicolumn{1}{c|}{}\(\boldsymbol { B }\)\(\boldsymbol { E }\)\(\boldsymbol { L }\)\(\boldsymbol { M }\)\(\boldsymbol { N }\)
    \(\boldsymbol { B }\)-23082102192
    \(\boldsymbol { E }\)230-148244258
    \(\boldsymbol { L }\)82148-126110
    \(\boldsymbol { M }\)102244126-236
    \(\boldsymbol { N }\)192258110236-
    1. Explain why the minimum travelling time from \(M\) to \(N\) is not 283 .
    2. Find an upper bound for the minimum travelling time by using the tour \(M N B E L M\).
    3. Write down the actual route corresponding to the tour \(M N B E L M\).
    4. Use the nearest-neighbour algorithm, starting from \(M\), to find another upper bound for the minimum travelling time of Rob's tour.
      [0pt] [4 marks] QUESTION
    1. The best upper bound is \(\_\_\_\_\)
    2. The best lower bound is \(\_\_\_\_\)
This paper (8 questions)
View full paper
Q1 Q2 Q3 2 Q4 3 Q5 6 Q6 4 Q7 Q8