Un árbol y-o es una representación gráfica de la reducción de problemas (u metas) a conjunciones y disyunciones de subproblemas (o submetas).
El árbol y-o:
representa el espacio de búsqueda para resolver el problema P, utilizando los métodos de reducción de objetivos:
Dado un problema inicial P 0 y un conjunto de métodos de resolución de problemas de la forma:
el árbol y/o asociado es un conjunto de nodos etiquetados tales que:
Un nodo N, etiquetado por un problema P, es un nodo exitoso si existe un método de la forma P si nada (es decir, P es un "hecho"). El nodo es un nodo fallido si no existe un método para resolver P.
Si todos los hijos de un nodo N, unidos por el mismo arco, son nodos exitosos, entonces el nodo N también es un nodo exitoso. De lo contrario, el nodo es un nodo fallido.
Un árbol y/o especifica sólo el espacio de búsqueda para resolver un problema. Son posibles diferentes estrategias de búsqueda para explorar el espacio. Estos incluyen buscar en el árbol primero en profundidad, primero en amplitud o primero en el mejor uso de alguna medida de conveniencia de las soluciones. La estrategia de búsqueda puede ser secuencial, buscando o generando un nodo a la vez, o paralela, buscando o generando varios nodos en paralelo.
Los métodos utilizados para generar árboles y/o son programas de lógica proposicional (sin variables). En el caso de programas lógicos que contengan variables, las soluciones de subproblemas conjuntos deben ser compatibles. Sujeto a esta complicación, las estrategias de búsqueda secuencial y paralela para árboles y/o proporcionan un modelo computacional para ejecutar programas lógicos.
Los árboles Y–o también se pueden utilizar para representar los espacios de búsqueda para juegos de dos personas. El nodo raíz de dicho árbol representa el problema de que uno de los jugadores gane el juego, comenzando desde el estado inicial del juego. Dado un nodo N, etiquetado por el problema P del jugador que gana el juego desde un estado de juego particular, existe un único conjunto de nodos secundarios conjuntos, correspondientes a todos los movimientos de respuesta de los oponentes. Para cada uno de estos nodos secundarios, existe un conjunto de nodos secundarios no conjuntos, correspondientes a todos los movimientos de defensa del jugador.
Para resolver árboles de juegos con una familia de algoritmos de búsqueda de números de prueba , los árboles de juegos deben asignarse a árboles y/o. Los nodos MAX (es decir, maximizar el movimiento del jugador) se representan como nodos OR, los nodos MIN se asignan a nodos AND. El mapeo es posible cuando la búsqueda se realiza solo con un objetivo binario, que generalmente es "el jugador que se mueve gana el juego".