• 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
- 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.