Wikipedia · einfach zusammengefasst · Stand
Und-Oder-Baum
Ein Und-Oder-Baum ist eine Art Entscheidungsbaum aus der Informatik und dient als Datenstruktur in der Künstlichen Intelligenz, insbesondere beim Minimax …
Inhalt3 Abschnitte
Definition und Einsatz
Ein Und-Oder-Baum ist eine Art Entscheidungsbaum in der Informatik. Er dient als Datenstruktur in der Künstlichen Intelligenz, besonders beim Minimax-Algorithmus und bei der Means-Ends-Analysis. Außerdem wird er häufig für Kontrollstrategien von Problemlöseprogrammen verwendet. Er kann als eine Art parallele Ausführung eines Logikprogrammiersystems betrachtet werden.
Aufbau und Funktionsweise
Ein Und-Oder-Baum besteht aus Und-Knoten und Oder-Knoten, die Entscheidungspunkte darstellen.
• Oder-Knoten entstehen, wenn es mehrere Möglichkeiten gibt, ein Ziel zu erreichen. Es genügt, eine der möglichen Lösungen zu erfüllen.
• Und-Knoten entstehen, wenn ein Hauptziel in mehrere Teilziele zerlegt wird. Alle Teilziele müssen konjunktiv, also gemeinsam, erfüllt sein, damit das Hauptziel erreicht ist. Und-Knoten können durch Constraints ergänzt werden. Diese formalen Bedingungen beschreiben, was gemeinsam erfüllt werden muss.
Hyperkanten
Oder-Kanten können mithilfe von Hyperkanten definiert werden. Eine Hyperkante ist eine Kante in einem Graphen, die einen Knoten gleichzeitig mit mehreren anderen Knoten verbindet. Eine normale Kante verbindet dagegen immer nur zwei Knoten. Um einen Knoten mit drei anderen Knoten zu verbinden, wären daher drei normale Kanten nötig.