Ein Und-Oder-Baum ist eine Art Entscheidungsbaum aus der Informatik und dient als Datenstruktur in der Künstlichen Intelligenz, insbesondere beim Minimax-Algorithmus und der Means-Ends-Analysis. Generell findet er oft Einsatz bei Kontrollstrategien von Problemlöseprogrammen.
Der Und-Oder-Baum kann als eine Art parallele Ausführung eines Logikprogrammiersystems betrachtet werden. Er besteht aus Und-Knoten und Oder-Knoten (Entscheidungspunkte). Oder-Kanten können mittels Hyperkanten definiert werden. Eine Hyperkante ist eine Kante in einem Graph, die einen Knoten mit mehreren anderen verbindet. Normale Kanten verbinden stets nur zwei Knoten auf einmal, für Verbindungen eines Knotens mit drei anderen Knoten braucht man also insgesamt drei Kanten.
Oder-Knoten entstehen, wenn es mehrere Möglichkeiten gibt, ein Ziel zu erreichen. Hier reicht es, eine von vielen Lösungsmöglichkeiten zu erfüllen. Und-Knoten entstehen, wenn ein Hauptziel in mehrere Teilziele unterteilt werden kann. Somit müssen alle Teilziele konjunktiv erfüllt sein, um das Hauptziel zu erfüllen. Und-Knoten werden manchmal Constraints hinzugefügt, um die Bedingungen, die konjunktiv erfüllt werden müssen, formal zu beschreiben.