4 Jeremy is planning a long weekend break during which he wants to photograph as many different churches as he can. He will start from his home, \(J\), on Friday morning and return to his home on Monday evening. Table 1, below, summarises the routes he can take each day and the number of churches that he will pass on each route. You may assume that the 28 churches in the table are all different.
\begin{table}[h]
| Day | From | To | | Number of churches |
| Friday | J | Kayton | \(K\) | 4 |
| J | Little Elling | \(L\) | 5 |
| Saturday | K | Moreton Emcombe | M | 2 |
| K | Nether Ensleigh | \(N\) | 0 |
| L | Nether Ensleigh | \(N\) | 0 |
| L | Peacombe | \(P\) | 4 |
| Sunday | M | River Ardan | \(R\) | 0 |
| N | River Ardan | \(R\) | 4 |
| P | Seabury | \(S\) | 3 |
| \(P\) | Teebury | \(T\) | 2 |
| Monday | \(R\) | Jeremy's home | \(J\) | 4 |
| S | Jeremy's home | \(J\) | 0 |
| \(T\) | Jeremy's home | \(J\) | 0 |
\captionsetup{labelformat=empty}
\caption{Table 1}
\end{table}
- Represent the information in the table as a directed network in which the vertices represent the places. You may code the place names using the letters, as above.
Jeremy wants to use dynamic programming to find the route on which he will pass the greatest number of churches. The (stage; state) variables will represent the places where he stays overnight. \(J\) will have (stage; state) variable ( \(0 ; 0\) ) at the start of the journey and ( \(4 ; 0\) ) at the end. Table 2 shows the (stage; state) variables for all the other places.
\begin{table}[h]
| Place | \(K\) | \(L\) | \(M\) | \(N\) | \(P\) | \(R\) | \(S\) | \(T\) |
| Stage variable | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 |
| State variable | 0 | 1 | 0 | 1 | 2 | 0 | 1 | 2 |
\captionsetup{labelformat=empty}
\caption{Table 2}
- Set up a dynamic programming tabulation, working backwards from Monday to Friday, to find the route that Jeremy should take to pass the greatest number of churches. Write down Jeremy's route. You may code the place names using the letters, as above. Write down the number of churches that he will be able to photograph on this route.