Edexcel D2 2006 January — Question 6 13 marks

Exam BoardEdexcel
ModuleD2 (Decision Mathematics 2)
Year2006
SessionJanuary
Marks13
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicTravelling Salesman
TypeIdentify Best Lower Bound
DifficultyModerate -0.5 This is a standard D2 travelling salesman problem requiring routine application of lower bound (vertex deletion + MST) and nearest neighbour algorithms. The techniques are algorithmic and well-practiced, requiring careful arithmetic but no problem-solving insight or novel approaches. Slightly easier than average due to its procedural nature.
Spec7.04a Shortest path: Dijkstra's algorithm7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree
6. The network in the figure above, shows the distances in km , along the roads between eight towns, A, B, C, D, E, F, G and H. Keith has a shop in each town and needs to visit each one. He wishes to travel a minimum distance and his route should start and finish at A . By deleting D, a lower bound for the length of the route was found to be 586 km .
By deleting F, a lower bound for the length of the route was found to be 590 km .
  1. By deleting C, find another lower bound for the length of the route. State which is the best lower bound of the three, giving a reason for your answer.
  2. By inspection complete the table of least distances. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{(8)
    (8)
    (Total 13 marks)} \includegraphics[alt={},max width=\textwidth]{a5d69a77-c196-483c-a550-1a55363555af-3_780_889_1069_1078}
    \end{figure} (4) The table can now be taken to represent a complete network. The nearest neighbour algorithm was used to obtain upper bounds for the length of the route: Starting at D, an upper bound for the length of the route was found to be 838 km .
    Starting at F, an upper bound for the length of the route was found to be 707 km .
  3. Starting at C , use the nearest neighbour algorithm to obtain another upper bound for the length of the route. State which is the best upper bound of the
    ABCDEFGH
    A-848513817314952
    B84-13077126213222136
    C85130-53888392
    D1387753-49190
    E1731268849-100180215
    F21383100-163115
    G14922292180163-97
    H5213619021511597-
    three, giving a reason for your answer.
    (4) (Total 13 marks)
6. The network in the figure above, shows the distances in km , along the roads between eight towns, A, B, C, D, E, F, G and H. Keith has a shop in each town and needs to visit each one. He wishes to travel a minimum distance and his route should start and finish at A .

By deleting D, a lower bound for the length of the route was found to be 586 km .\\
By deleting F, a lower bound for the length of the route was found to be 590 km .
\begin{enumerate}[label=(\alph*)]
\item By deleting C, find another lower bound for the length of the route. State which is the best lower bound of the three, giving a reason for your answer.
\item By inspection complete the table of least distances.

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{(8)\\
(8)\\
(Total 13 marks)}
  \includegraphics[alt={},max width=\textwidth]{a5d69a77-c196-483c-a550-1a55363555af-3_780_889_1069_1078}
\end{center}
\end{figure}

(4)

The table can now be taken to represent a complete network.

The nearest neighbour algorithm was used to obtain upper bounds for the length of the route: Starting at D, an upper bound for the length of the route was found to be 838 km .\\
Starting at F, an upper bound for the length of the route was found to be 707 km .
\item Starting at C , use the nearest neighbour algorithm to obtain another upper bound for the length of the route. State which is the best upper bound of the

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline
 & A & B & C & D & E & F & G & H \\
\hline
A & - & 84 & 85 & 138 & 173 &  & 149 & 52 \\
\hline
B & 84 & - & 130 & 77 & 126 & 213 & 222 & 136 \\
\hline
C & 85 & 130 & - & 53 & 88 & 83 & 92 &  \\
\hline
D & 138 & 77 & 53 & - & 49 &  &  & 190 \\
\hline
E & 173 & 126 & 88 & 49 & - & 100 & 180 & 215 \\
\hline
F &  & 213 & 83 &  & 100 & - & 163 & 115 \\
\hline
G & 149 & 222 & 92 &  & 180 & 163 & - & 97 \\
\hline
H & 52 & 136 &  & 190 & 215 & 115 & 97 & - \\
\hline
\end{tabular}
\end{center}

three, giving a reason for your answer.\\
(4) (Total 13 marks)
\end{enumerate}

\hfill \mbox{\textit{Edexcel D2 2006 Q6 [13]}}
This paper (7 questions)
View full paper
Q1 13 Q2 12 Q3 8 Q4 16 Q5 13 Q6 13 Q7 11