And–or tree

An and–or tree is a graphical representation of the reduction of problems (or goals) to conjunctions and disjunctions of subproblems (or subgoals).

Example

The and–or tree:

represents the search space for solving the problem P, using the goal-reduction methods:

P if Q and R

P if S

Q if T

Q if U

Definitions

Given an initial problem P₀ and set of problem solving methods of the form:

P if P₁ and … and P_n

the associated and–or tree is a set of labelled nodes such that:

1. The root of the tree is a node labelled by P₀.
2. For every node N labelled by a problem or sub-problem P and for every method of the form P if P₁ and … and P_n, there exists a set of children nodes N₁, …, N_n of the node N, such that each node N_i is labelled by P_i. The nodes are conjoined by an arc, to distinguish them from children of N that might

…

Source: Wikipedia