Search Tree

Search Tree: Consider the explicit state space graph shown in the figure.
One may list all possible paths, eliminating cycles from the paths, and we would get the complete search tree from a state space graph. Let us examine certain terminology associated with a search tree. A search tree is a data structure containing a root node, from where the search starts. Every node may have 0 or more children. If a node X is a child of node Y, node Y is said to be a parent of node X.

Figure 2: Search tree for the state space graph in Figure 25

Consider the state space given by the graph in Figure 1. Assume that the arcs are bidirectional. Starting the search from state A the search tree obtained is shown in Figure 2. Search Tree – Terminology

• Root Node: The node from which the search starts.
• Leaf Node: A node in the search tree having no children.
• Ancestor/Descendant: X is an ancestor of Y is either X is Y’s parent or X is an ancestor of the parent of Y. If S is an ancestor of Y, Y is said to be a descendant of X.
• Branching factor: the maximum number of children of a non-leaf node in the search tree
• Path: A path in the search tree is a complete path if it begins with the start node and ends with a goal node. Otherwise it is a partial path.

We also need to introduce some data structures that will be used in the search algorithms.

Node data structure A node used in the search algorithm is a data structure which contains the following:
1. A state description
2. A pointer to the parent of the node
3. Depth of the node
4. The operator that generated this node
5. Cost of this path (sum of operator costs) from the start state
The nodes that the algorithm has generated are kept in a data structure called OPEN or fringe. Initially only the start node is in OPEN.

The search starts with the root node. The algorithm picks a node from OPEN for expanding and generates all the children of the node. Expanding a node from OPEN results in a closed node. Some search algorithms keep track of the closed nodes in a data structure called CLOSED.

A solution to the search problem is a sequence of operators that is associated with a path from a start node to a goal node. The cost of a solution is the sum of the arc costs on the solution path. For large state spaces, it is not practical to represent the whole space. State space search makes explicit a sufficient portion of an implicit state space graph to find a goal node. Each node represents a partial solution path from the start node to the given node. In general, from this node there are many possible paths that have this partial path as a prefix.
The search process constructs a search tree, where

• root is the initial state and
• leaf nodes are nodes
• not yet expanded (i.e., in fringe) or
• having no successors (i.e., “dead-ends”)

Search tree may be infinite because of loops even if state space is small
The search problem will return as a solution a path to a goal node. Finding a path is important in problems like path finding, solving 15-puzzle, and such other problems. There are also problems like the N-queens problem for which the path to the solution is not important. For such problems the search problem needs to return the goal state only.