Easy -1.2 This is a straightforward application of standard D1 algorithms (nearest neighbour for upper bound, minimum spanning tree deletion for lower bound) with clearly structured tables. The procedures are mechanical and well-rehearsed, requiring only careful arithmetic and following prescribed steps rather than problem-solving or insight.
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\) )
-
165
185
65
160
Aker Brygge (A)
165
-
155
115
275
National Theatre ( \(N\) )
185
155
-
205
125
Parliament House (P)
65
115
205
-
225
Royal Palace (R)
160
275
125
225
-
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.
Use the nearest neighbour algorithm, starting from the Grand Hotel, to find an upper bound for the walking time for Mark's tour.
By deleting the Grand Hotel, find a lower bound for the walking time for Mark's tour.
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\).
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 }\) )
-
20
17
30
Ibsen (I)
15
-
32
16
Munch (M)
26
18
-
21
Viking ( \(\boldsymbol { V }\) )
19
27
24
-
Find the length of the tour \(G I M V G\).
Find the length of the tour GVMIG.
Find the number of different possible tours for Mark.
Write down the number of different possible tours for Mark if he were to visit \(n\) museums, starting and finishing at the Grand Hotel.
6
\begin{enumerate}[label=(\alph*)]
\item 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.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& Grand Hotel ( $G$ ) & Aker Brygge (A) & National Theatre ( $N$ ) & Parliament House (P) & Royal Palace (R) \\
\hline
Grand Hotel ( $G$ ) & - & 165 & 185 & 65 & 160 \\
\hline
Aker Brygge (A) & 165 & - & 155 & 115 & 275 \\
\hline
National Theatre ( $N$ ) & 185 & 155 & - & 205 & 125 \\
\hline
Parliament House (P) & 65 & 115 & 205 & - & 225 \\
\hline
Royal Palace (R) & 160 & 275 & 125 & 225 & - \\
\hline
\end{tabular}
\end{center}
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.
\begin{enumerate}[label=(\roman*)]
\item Use the nearest neighbour algorithm, starting from the Grand Hotel, to find an upper bound for the walking time for Mark's tour.
\item By deleting the Grand Hotel, find a lower bound for the walking time for Mark's tour.
\item 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$.
\end{enumerate}\item 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.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
\backslashbox{From}{To} & Grand Hotel ( $G$ ) & Ibsen (I) & Munch ( $M$ ) & Viking ( $\boldsymbol { V }$ ) \\
\hline
Grand Hotel ( $\boldsymbol { G }$ ) & - & 20 & 17 & 30 \\
\hline
Ibsen (I) & 15 & - & 32 & 16 \\
\hline
Munch (M) & 26 & 18 & - & 21 \\
\hline
Viking ( $\boldsymbol { V }$ ) & 19 & 27 & 24 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\roman*)]
\item Find the length of the tour $G I M V G$.
\item Find the length of the tour GVMIG.
\item Find the number of different possible tours for Mark.
\item Write down the number of different possible tours for Mark if he were to visit $n$ museums, starting and finishing at the Grand Hotel.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2007 Q6 [14]}}