This topic was introduced in the section on exhaustive search. Here, we supplement that note by illustrating the order in which a tree is searched using depth-first search.
We assume that we are searching a tree of states. This tree has 31 nodes (equivalent to states here) and each leaf (or terminal node) is at a depth of 3 (counting the root node as being at depth 0). Let us assume that the only winning state is node ee (the winning state is the state that satisfies some criteria for success).
To search for a winning state, we start with the root node (node a). We evaluate the first successor state (node b) -remembering that we still have to examine the trees rooted at nodes c and d. We can represent this information as an ordered set of nodes that await exploration.
Here, representing this information as a Prolog list, we start with [a], we find the next successor states are nodes b, c and d. Let us represent this by replacing node a by nodes b, c and d as the list [b,c,d].
The next node we want to work on is node b -and that is the node at the head of the list. We take the subtree rooted at node b and derive its successor states (sometimes described as expanding the node) -resulting in the replacement of node b by nodes e, f and g. To do this replacement, we remove node b from the list and insert nodes e, f and g -but where?
With depth-first search, we will want to explore node e next. We also want to keep to the regime of always working on the node found at the head of the list. We therefore choose to insert node b's replacements at the head of the list. Our data structure becomes [e,f,g,c,d].
We continue by choosing to derive the successor states for node e. Remember that we we always take the node to be expanded from the front of the list.
The order of search for the winning state
is shown by the numbering of the nodes in figure 3.
