In the last chapter we looked at the notion of search spaces. Search spaces, as shown in Figure 2.2, are trees corresponding to the different traversals possible in the state space or the solution space. In this chapter we begin by constructing the machinery, viz. algorithms, for navigating this space. We begin our study with the corresponding tiny state space shown in Figure 3.1.

The tiny search problem has seven nodes, including the start node S, the goal node G, and five other nodes named A, B, C, D, and E. Without any loss of generality, let us assume that the nodes are states in a state space. The algorithms apply to the solution space as well. The left side of the figure describes the MoveGen function with the notation Node → (list of neighbours). On the right side is the corresponding graph which, remember, is implicit and not given upfront. The algorithm itself works with the MoveGen function and also the GoalTest function. The latter, for this example, simply knows that state G is the goal node. For configuration problems like the N-queens, it will need to inspect the node given as the argument.

The search space that an algorithm explores is implicit. It is generated on the fly by the MoveGen function, as described in Algorithm 2.1. The candidates generated are added to what is traditionally called OPEN, from where they are picked one by one for inspection. In this chapter we represent OPEN as a list data structure.