Figure 4.3 shows how we can represent the search in a tree structure. It is the search tree for the route from Victoria to Marble Arch, using the reduced map of figure 4.2, and indicating only the first arrival at any station. Trees in AI grow upside-down, and the time sequence in our diagram goes from the top to the bottom of the page. The starting point, Victoria, is shown as the root of the tree, and the first branches from it go to the first four possible stations. In the tree, stations are known as nodes and each node in our diagram is labelled with a three-letter abbreviation for the station name, followed by a three-letter abreviation in capitals for the line name. As our wave of volunteers spreads out from Victoria and reaches increasing numbers of stations, nodes are added to the tree at increasingly deeper levels. Notice, though, that we still must be careful to work downwards in time sequence, or the end result may go wrong. As soon as Marble Arch is added, we can trace back up the tree, so finding the solution.
[IMAGE ]
Figure 4.3: The search tree for the route from Victoria to Marble Arch.
The task of the program can be seen, then, as building this tree. This is just another way of expressing the description we gave earlier in terms of simulating our volunteers. As we shall see, the tree description is a very general way to describe search procedures.
Breadth first search is just a special case of branch and bound. Suppose in the route finder the time to change lines was equal to the time to travel between stations. Then in figure 4.3, nodes an equal number of steps from the root would lie at the same level in the diagram, and the simulation would consider all of them before going onto lower (i.e., later) nodes. Under these conditions the search becomes breadth first.
![[IMAGE ]](img2.gif){kind=link}