# 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).

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:

1. mark every door in the starting room as ‘exit’;

2. examine the current room;

3. if you find your friend, stop;

4. otherwise, if there are any doors marked ‘exit’ in the room,

1. choose one of them;

2. remove the mark ‘exit’;

3. go through it;

4. if one of the doors in this room is already marked ‘entrance’, go back to the previous room, and go to step 4;

5. otherwise, mark the door you just came through as ‘entrance’;

6. mark all other doors as ‘exit’;

7. go to step 2;

5. 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.

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):

1. take the next node from the agenda;

2. if it is a goal node, stop;

3. 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),