OCR MEI D2 2012 June — Question 3 20 marks

Exam BoardOCR MEI
ModuleD2 (Decision Mathematics 2)
Year2012
SessionJune
Marks20
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicTravelling Salesman
TypeFloyd's Algorithm Application
DifficultyStandard +0.3 This is a structured algorithmic question testing Floyd's algorithm and TSP techniques. Part (i) involves completing standard Floyd's algorithm tables (routine procedure), part (ii) applies the deletion method for lower bounds (standard technique), and parts (iii-v) use nearest neighbour algorithm and interpretation. While multi-part with several marks, each component follows well-defined algorithms with no novel problem-solving required—slightly easier than average due to the procedural nature of Decision Mathematics questions.
Spec7.04a Shortest path: Dijkstra's algorithm7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree7.04e Route inspection: Chinese postman, pairing odd nodes
3 The weights on the network represent distances. \includegraphics[max width=\textwidth, alt={}, center]{eb4e9c34-7d8f-4118-b7ec-edcd9567077f-4_451_544_324_740}
  1. The answer book shows the initial tables and the results of iterations \(1,2,3\) and 5 when Floyd's algorithm is applied to the network.
    (A) Complete the two tables for iteration 4.
    (B) Use the final route table to give the shortest route from vertex \(\mathbf { 3 }\) to vertex \(\mathbf { 5 }\).
    (C) Use the final distance table to produce a complete network with weights representing the shortest distances between vertices.
  2. Using the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson Problem by deleting vertex 5 and its arcs, and by finding the length of a minimum connector for the remainder. (You may find the minimum connector by inspection.)
  3. Use the nearest neighbour algorithm, starting at vertex \(\mathbf { 1 }\), to produce a Hamilton cycle in the complete network. Give the length of your cycle.
  4. Interpret your Hamilton cycle in part (iii) in terms of the original network.
  5. Give a walk of minimum length which traverses every arc on the original network at least once, and which returns to the start. Give the length of your walk.
3 The weights on the network represent distances.\\
\includegraphics[max width=\textwidth, alt={}, center]{eb4e9c34-7d8f-4118-b7ec-edcd9567077f-4_451_544_324_740}
\begin{enumerate}[label=(\roman*)]
\item The answer book shows the initial tables and the results of iterations $1,2,3$ and 5 when Floyd's algorithm is applied to the network.\\
(A) Complete the two tables for iteration 4.\\
(B) Use the final route table to give the shortest route from vertex $\mathbf { 3 }$ to vertex $\mathbf { 5 }$.\\
(C) Use the final distance table to produce a complete network with weights representing the shortest distances between vertices.
\item Using the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson Problem by deleting vertex 5 and its arcs, and by finding the length of a minimum connector for the remainder. (You may find the minimum connector by inspection.)
\item Use the nearest neighbour algorithm, starting at vertex $\mathbf { 1 }$, to produce a Hamilton cycle in the complete network. Give the length of your cycle.
\item Interpret your Hamilton cycle in part (iii) in terms of the original network.
\item Give a walk of minimum length which traverses every arc on the original network at least once, and which returns to the start. Give the length of your walk.
\end{enumerate}

\hfill \mbox{\textit{OCR MEI D2 2012 Q3 [20]}}
This paper (4 questions)
View full paper
Q1 16 Q2 16 Q3 20 Q4 20