Imagine you are standing at Victoria Station and you need to go to Marble Arch. You are looking at a map like figure 4.1. You would probably decide to go north 2 stops on the Victoria line to Oxford Circus, then west 2 stops on the Central line. You perhaps feel it is obvious that that is the best route, but if the route were more complex and there were many lines going in roughly the right direction, you might be less sure.
[IMAGE ]
Figure 4.1: The London Underground map.
To program a computer to carry out such a search we need to provide it with both a representation of the problem (in terms of how the stations are connected) and a method of carrying out the search. In creating the representation we can ignore many aspects of the geography and topology of London. For instance, we do not need to know what the area around a station looks like, or its exact map reference. The information we need concerns legal routes between stations, and perhaps the time taken to travel from one station to another and to change lines. (The London Underground map serves just this purpose, and at the time it was first designed, in the 1920s, it was a great innovation.) If we were interested merely in finding any route between two stations, then we could program the computer with a fairly simple algorithm. In English it is this:
For an example we shall use the simplified map in figure 4.2. Let us say that we want to get to Baker Street. From Victoria we could choose the Victoria line northwards. We follow it station by station: Victoria, Green Park, Oxford Circus, Warren Street. We get to the end of the line at Warren Street without passing our goal, Baker Street. Now we retrace the route back to Oxford Circus and try another line, say the Central line westwards. This reaches a dead end, at Lancaster Gate, so we retrace the route to the last junction, Bond Street, and try a new route, say the Jubilee line southwards. We follow this till we reach a station that has already been visited (Green Park) and then retrace our steps back to Bond Street. We then try the Jubilee line northwards from Bond Street, and reach our goal, Baker Street. The route is then Victoria, Green Park, Oxford Circus, Bond Street, Baker Street.
[IMAGE ]
Figure 4.2: A small section of the Underground map.
This type of search algorithm is known as depth first search, because it searches right down to the end of a path, before trying an alternative. It is guaranteed to find a path to the goal, if one exists, but the path is not likely to be the best one (a better route to Baker Street is to change at Green Park and take the Jubilee line). Another, related, type of search is breadth first search, which follows each path from the current node to the next decision point. It is useful when we want to find a solution with the minimum number of steps from the starting point; an example might occur in programming a robot to perform an action in the smallest possible number of separate movements. For example, from Victoria we investigate the lines to the Embankment, Green Park, South Kensington, and Vauxhall. Since the goal station is not on any of these, we choose one junction, say the Embankment, and investigate all the unexplored lines leading from there (there is only one, to Charing Cross). Since it is not successful we choose the earliest unexplored junction, Green Park. That leads to Bond Street, Oxford Circus, Piccadilly Circus, Charing Cross, and South Kensington. Embankment, Green Park, and South Kensington have now all been explored, and Vauxhall is not a junction. So we look at lines from the earliest unexplored junction, Bond Street. One of these lines leads to Baker Street, and we have found the goal.
But for it to be any use to a tourist, our program for the Tourist Guide should not just find any route to a given station, but the best route (though it is allowed to make some assumptions about how fast the trains go and how long it takes to change lines). The method we shall describe is an adaptation of breadth first search that takes account of the time taken to reach each station. The name, branch and bound, comes from the fact that at each step we put a bound or limit on which branches are searched: i.e., we only consider the ones with the shortest times.
In the appendix to this chapter we outline a computer program to perform branch and bound search, but here is an informal description. Let us assume this time that we want to find the best route to Marble Arch. Imagine we could gather together a large number of volunteers (say 200) and assemble them all at Victoria. They then all set off at the same time, a quarter in each direction, to Pimlico, Green Park, Sloane Square, and St James's Park. At each station with a choice of route the party of volunteers splits, some going one way, others another. Thus at Green Park, some stay on the train to Oxford Circus and some change, splitting up and heading for Hyde Park Corner, Bond Street, Picadilly Circus, and Charing Cross. Naturally the parties get smaller, but provided the original group was large enough, there are enough of them to split up at every junction until the search is over. All we need to do is wait at Marble Arch and ask the first volunteers who arrive what stations they have passed through. These volunteers must have taken the fastest route; if a faster one existed then another party would have found it, and would have arrived sooner.
You may feel that this process is unnecessarily extravagant even with simulated volunteers: why explore south from Victoria when it is obvious that this will not produce a useful route? Unfortunately it is not obvious to our computer program. A fact like this is only obvious to us because our visual system manages, without our having to give conscious thought, to do a lot of the information processing that we need laboriously to program into the computer. Until the search is complete, the program cannnot be sure that there is no remarkable shortcut from somewhere south of Pimlico up to Marble Arch.
Let us now turn to the mechanics of the computer program, which we can do best by simulating our wave of volunteers using pencil and paper. We will make the following assumptions (in practice much more detailed knowledge of likely times could be deployed):
We write on a map of the Underground the times it takes the first of our volunteers to arrive at each station. It will be clearest if we split stations on several lines into pieces, one on each line, as in figure 4.2. We begin by writing 0 by Victoria, then 2 by Sloane Square, St James's Park, Pimlico, and Green Park (Victoria line), since each of these can be reached in 2 minutes from Victoria. Continuing in strict temporal sequence, the next arrivals will be after 4 minutes at Oxford Circus, South Kensington, Vauxhall, and Westminster. At 5 minutes some groups have changed stations to other lines at Green Park, so each of these can be labelled 5. In figure 4.2, the time labels have been completed up to 5 minutes. If you continue this process in strict temporal order, adding all the 6 minute labels before you add the 7 minute ones, you should end up labelling Marble Arch with 11 minutes, for the group that changed at Oxford Circus. That then gives the solution. In the process many other stations will have been labelled.
Note how important it is to do things in chronological order: if we worked outwards from Green Park and forgot what was happening at Oxford Circus, then we could end up erroneously labelling Bond Street (Central line) with 10 and hence Marble Arch with 12.
We now have an informal but quite precise specification of an algorithm, and it remains to convert it into POP-11 to make it usable. In the meantime we shall look at another way of representing the search process, one that has considerable power in helping us to visualize mechanisms such as this.
![[IMAGE ]](img2.gif){kind=link}