In this section we shall show how to write a program to find quickest routes on the London Underground, provided we can make simple assumptions about travel times. Here is a call of the main procedure route. Given two stations as input, it returns a list giving the quickest route between them:
route([victoria],[marble arch])=>
** [[[VICTORIA victoria] at 0 mins] [[VICTORIA green park] at 2 mins] [[VICTORIA oxford circus] at 4 mins] [[CENTRAL oxford circus] at 7 mins] [[CENTRAL bond street] at 9 mins] [[CENTRAL marble arch] at 11 mins]]
In each sub-list the first word is the name of the line, followed by the name of the station and the time taken to get to it. The program implements branch and bound search. There are two ways of looking at what it does: one is that it simulates the spread of the volunteer travellers from the start station; the other is that it builds a representation of the search tree. It will be simplest to describe the program in terms of a simulation. We will not set the program out in full, as it would be too long, but we hope that having read this you will understand the way it works well enough to implement a program of your own if you have a suitable system, or to have a clear idea of what is needed if you do not. The program is more complex than those you have met so far, so if at first you cannot understand how it works, then either skip this section or invest some effort in trying to follow the program line by line. The complete search program is incorporated into the example Tourist Guide in appendix B at the end of the book.
To start, we need to be able to represent the Underground map to the program. This is done by a series of add statements storing one entry in the database for each connection between two adjacent stations (you may like to refer back to chapter 3 on the use of the database). Figure 4.2 requires 24 statements to be stored to represent it; here is the part of the program that stores 4 of them:
add([[JUBILEE charing cross] connects [JUBILEE green park]]);
add([[JUBILEE green park] connects [JUBILEE bond street]]);
add([[JUBILEE bond street] connects [JUBILEE baker street]]);
add([[BAKERLOO embankment] connects
[BAKERLOO charing cross]]);
Each entry is a triplet, in the same form as those for the London database of chapter 3. Each of the first and last components gives a line and a station; in the middle is the word `connects', which establishes the relationship between them, and indicates that the stations are next to one another on the line. The line/station combinations are lists, of which the first word is the line name and the rest the station name. We have put the line names in capitals, but that is only for clarity when looking at the program; it does not affect its operation. For convenience, the representation is `redundant': that is, the line name appears twice in each statement when the same information would still be present if it only appeared once.
The remainder of the program can be divided into two main parts:
The volunteers are simulated by recording information about the stations they have reached and are about to reach in the POP-11 database, adding information in chronological sequence. When the destination station is reached the search stops and the second part of the program proceeds to look at the stored information to see the route followed. The bulk of the program is its first part, and we shall now proceed to describe that.