Tree , Graph searching for problem solving as state space, Formalizing search in a graph,

•   A tree is graph connected  without any cycles.

•  Trees comes with different types: tournament brackets, family trees, organizational charts and decision trees. In the above figure  there is a path between a to b and b to a this forms  a cycle. Here in tree no such  cycles are formed.

                          

Graph searching for problem solving as state space

•  Graph searching for problem solving as state space  search  is to find a sequence of actions to achieve a goal as searching for paths in a directed graph.

•  To solve the problem ,We define the underlying search space  and then apply a search algorithm.

•  Searching  in  graphs, therefore, provides  an appropriate  abstract model of problem solving , independent of the particular domain.

Formalizing search in a graph

1. To formalize search in a graph, first we need to define a state space. Lets a say the state space is a graph    of vertices and edges  i.e., (V,E)

• V is a set of nodes and

•  E is a set of arcs , directed from a node to another node.

2. Each node  refers to a simple node  data structure that contains a state description  and other information  such as the parent of the node , operator that generated the node from that parent, and other book keeping data.

3. Each arc corresponds to an instance of one of the operators.

4.Whenever we are formalizing search in state space  , we are converting the entire state space into nodes with each operator with some instances that takes me  to next nodes which ends up in a directed graph. This searching in a directed graph for a path from Start to Goal gives the solution.

5. Each arc in a directed graph has a fixed positive cost associated with it corresponding to the cost of the operator.

6. Each node has a set of successor nodes corresponding to all of the legal operators as that can be applied to the source node state.

•   expanding a node means  it is a continuous process of generating  all the successor nodes and add them to their associated arcs.

7.  One or more nodes are designated as the start node later there will be a  goal test predicate that  is applied to a state to determine if its associated node is goal node.

8. A solution is a sequence of operators that is associated with a path in a state space from a start node to goal node.