We illustrate how the search progresses in figure 1. To do this, we need the idea of developing a tree of states. Each node in the tree represents a state. The root of the tree, the root node, is the initial state. The arcs of the tree indicate the application of one of the ten operators. The states for which no operators apply are called leaf nodes. They have no arcs leading from them.
Note that we may occasionally omit the direction of the operator as any operator can only be applied to the side with the boat.
We assume that the tree of states is developed by trying to apply operators in a standard order (ignoring direction): 0m1c, 1m0c, 1m1c, 0m2c and 2m0c.
Now for the whole search space -shown in figure 2: this time the order of operator application is 1m0c, 2m0c, 1m1c, 0m1c and 0m2c. Note that depth first search does not require a uniform order of operator application. Note also that the solution paths are indicated by solid lines. Note also that an l indicates a previously visited state (i.e. looping), and an e indicates a missionary eaten!
The search process traverses the search space by going down before going left-to-right. For example, the path indicated by the application of [2m0c, 1m0c] is examined before [1m1c, 1m0c]. The possibility 2m0c is exhaustively explored before the option 1m1c is explored. To do this, the depth-first search strategy requires the search to backtrack.
