5.1. A general search procedure#
Imagine a visit with a friend to the Staatsgalerie in Stuttgart. It is very crowded in this beautiful art museum, and while admiring the Mondriaan works you lose sight of each other. Having been through situations like this before, you had made the agreement that she would stay where she was, while you would go looking for her. What strategy would you employ?
First of all, to make sure that you don’t miss any room, you have to visit them in some systematic way. You don’t have a global map of the building, so you decide to never leave a room through the door through which you entered. Thinking about it, you recognise that this procedure won’t fully work, because a room might have just one door: the one through which you entered. Assuming that there are still rooms not yet visited, you have to leave such a room through the same door through which you entered, and find a room you’ve visited before, with a door not yet taken. Such a procedure, however, requires that, for each room you visit, you remember the door through which you entered the room (in order to go back to a room you’ve been in before), and the doors you tried already (in order to try a remaining door).
Figure 5.1 Searching for a friend.#
Luckily enough, you carry a piece of paper and a pencil with you, so you can stick little papers saying ‘entrance’ or ‘exit’ on the appropriate doors. However, the amount of paper you have is limited, so a better idea is to mark the doors not yet tried, and to remove the paper when you try a door, so that you can use the paper again. By reusing those pieces of paper that become obsolete, you minimise the amount of paper needed. Similarly, if you return to a room in which there are no remaining doors, you will never return to that room, so you might want to remove the paper saying ‘entrance’ as well. On the other hand, leaving one paper might be a good idea, just in case you return to the room later via a ‘circular’ route; you are then able to see that you already tried all the doors in that room.
So you decide to employ the following procedure:
mark every door in the starting room as ‘exit’;
examine the current room;
if you find your friend, stop;
otherwise, if there are any doors marked ‘exit’ in the room,
choose one of them;
remove the mark ‘exit’;
go through it;
if one of the doors in this room is already marked ‘entrance’, go back to the previous room, and go to step 4;
otherwise, mark the door you just came through as ‘entrance’;
mark all other doors as ‘exit’;
go to step 2;
otherwise, take the door marked ‘entrance’, and go to step 4.
Steps 1–3 are obvious enough. In step 4, you check whether there are any untried doors left; if not, you have to go back to a previously visited room, and do the same there (step 5). This process of reconsidering previous decisions is called backtracking. It is an essential step in any exhaustive search procedure. If there are any alternatives left, you have to check whether you have been there already via some other route (step 4.4). This step is called loop detection, and is only needed for cyclic search spaces. If you omit this step in such cases, you risk walking in circles forever. If you are in a yet unvisited room, you do some bookkeeping and proceed in the same way.
Figure 5.2 You find her by systematically searching the rooms, backtracking when all the rooms reachable from the room you’re in have been visited already (thin lines).#
How does this search procedure work in practice? Suppose you are in the Miró room (Figure 5.1). You decide to try the doors in that room in a clockwise order. You first check the Léger room, then the Kupka room, and finally the Kandinsky room. When you enter the Léger room again from Kandinsky, you realise that you’ve been there before, because there’s a door marked ‘entrance’. So you backtrack to Léger (because there are no alternatives left in Kandinsky and Kupka), and try the next door. This one leads you straight to Kandinsky again, and your little papers remind you that you have been there already. You backtrack again to Léger, and try the Matisse room. From there, Klee is a dead end, so you backtrack and finally find your friend still admiring the Mondriaan paintings! The route you walked is shown in Figure 5.2 (thin lines denote backtracking).
In a computer implementation of such a search procedure, you don’t walk from room to room. Instead of marking nodes and returning to them later, the search program stores a description of those nodes in memory. In the above example, the number of marks needed corresponds to the amount of memory required during search, and just as marks can be used several times, memory space can be reclaimed once all the children of a node have been put on the list. This list of nodes to be tried next is called the agenda; this is an important concept, which can be used to describe any backtracking search procedure. Such a general-purpose agenda-based search algorithm operates as follows (for simplicity, we have omitted loop detection):
take the next node from the agenda;
if it is a goal node, stop;
otherwise,
generate its children;
put them on the agenda;
go to step 1.
This procedure can be almost directly translated into a Prolog program:
% search(Agenda,Goal) <- Goal is a goal node, and a
% descendant of one of the nodes
% on the Agenda
search(Agenda,Goal):-
next(Agenda,Goal,Rest),
goal(Goal).
search(Agenda,Goal):-
next(Agenda,Current,Rest),
children(Current,Children),
add(Children,Rest,NewAgenda),
search(NewAgenda,Goal).
In this program, we have abstracted from the way the agenda is represented. Furthermore, as remarked above, by specifying the order in which nodes are added to and removed from the agenda, we obtain specific search strategies. In the Staatsgalerie example, doors marked most recently are tried first. In other words, the agenda is a last in–first out datastructure, or a stack. In this example, it seems the most reasonable approach, because it minimises the amount of walking needed to backtrack to another room. The result is a depth-first search procedure, moving away as quickly as possible from the initial room, only coming closer again when backtracking.
On the other hand, the shortest path between your initial position and your friend is Miró-Mondriaan, while you finally reach your friend along the path Miró-Léger-Matisse-Mondriaan[1]. You would have found your friend sooner if you would have examined all rooms next to Miró first. But suppose your friend was two rooms away, e.g. in the Matisse room? Well, in that case you would have gone to the rooms next to Miró (Léger and Mondriaan), and then to all rooms next to those (Kupka, Kandinsky and Matisse). That is, doors marked most recently are tried last: a first in–first out strategy, implemented by a datastructure called a queue. Thus you would have found your friend along one of the two shortest paths (Miró-Léger-Matisse). This second method is an example of breadth-first search.
Finally, a third approach called best-first search orders the doors to be tried next according to some criterion called a heuristic. For instance, suppose you saw your friend last in the Mondriaan room. In this case it would be wise to overrule the default clockwise ordering, and to try Mondriaan before Léger. Consequently, you would have found your friend along the path Miró-Mondriaan-Matisse. In the following sections, we will take a closer look at depth-first and breadth-first search. The use of heuristics will be studied in Chapter 6.