And–or tree

An and-or tree is a type of decision tree in computer science and serves as a data structure in Artificial Intelligence, especially in the Minimax algorithm and the Means -Ends Analysis. Generally, he often finds use in control strategies of problem solving programs.

The And - Or tree can be considered as a kind of parallel execution of a logic programming system. It consists of And - nodes and OR- nodes ( decision points). Or - edges can be defined by means of hyperedges. A hyper- edge is an edge in a graph, a node which connects with a plurality of others. Normal edges connect always only two nodes at a time so for connections of a node with three other nodes you need three edges.

Or nodes arise when there are multiple ways to achieve a goal. Here it is enough to meet a number of possible solutions. And nodes are created when a main object can be divided into a plurality of sub-goals. To follow all the subgoals must be satisfied conjunctively to meet the main goal. And nodes are sometimes added constraints to formally describe the conditions that must be satisfied conjunctively.