Double traversal (both sides of street)

Find optimal route where each edge must be traversed exactly twice (e.g., for inspecting both sides of a street), differing from standard route inspection.

2 questions · Moderate -0.8

7.04c Travelling salesman upper bound: nearest neighbour method
Sort by: Default | Easiest first | Hardest first
Edexcel D1 2008 January Q3
9 marks Moderate -0.8
3. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{7396d930-0143-4876-b019-a4d73e09b172-4_755_1132_239_468} \captionsetup{labelformat=empty} \caption{Figure 4}
\end{figure} Figure 4 models a network of roads in a housing estate. The number on each arc represents the length, in km , of the road. The total weight of the network is 11 km .
A council worker needs to travel along each road once to inspect the road surface. He will start and finish at A and wishes to minimise the length of his route.
  1. Use an appropriate algorithm to find a route for the council worker. You should make your method and working clear. State your route and its length.
    (6) A postal worker needs to walk along each road twice, once on each side of the road. She must start and finish at A . The length of her route is to be minimised. You should ignore the width of the road.
    1. Explain how this differs from the standard route inspection problem.
      (1)
    2. Find the length of the shortest route for the postal worker.
      (2)
Edexcel D1 2003 November Q1
4 marks Moderate -0.8
1. \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-02_992_1292_477_342}
\end{figure} A local council is responsible for maintaining pavements in a district. The roads for which it is responsible are represented by arcs in Fig. 1.The junctions are labelled \(A , B , C , \ldots , G\). The number on each arc represents the length of that road in km. The council has received a number of complaints about the condition of the pavements. In order to inspect the pavements, a council employee needs to walk along each road twice (once on each side of the road) starting and ending at the council offices at \(C\). The length of the route is to be minimal. Ignore the widths of the roads.
  1. Explain how this situation differs from the standard Route Inspection problem.
  2. Find a route of minimum length and state its length.