Reduzierte binäre Entscheidungsdiagramme (ROBDD) sind eine effiziente Datenstruktur für Boolesche Funktionen mehrerer Variablen f(x1,x2,...,xn) . Ich würde gerne eine Intuition für wie effizient sie sind.
Wir wissen zum Beispiel, dass Daten mit niedriger Entropie (einige Symbole häufiger als andere, viele Wiederholungen) sehr gut komprimiert werden können, während völlig zufällige Daten nicht komprimiert werden können.
Gibt es eine analoge Intuition für die Schätzung, wie effizient ROBDDs eine gegebene boolesche Formel darstellen können? Irgendwelche Literatur zu diesem Thema (vorzugsweise online)?
Es gibt einen Artikel im Wikipedia-Artikel Symbolische Boolesche Manipulation mit geordneten binären Entscheidungsdiagrammen gibt für bestimmte Funktionsklassen untere und obere Grenzen vor (symmetrisch, binäre Arithmetik repräsentierend). Ich denke, dass im durchschnittlichen Fall 2n*log n >= 2^k gilt, wobei n die Anzahl der Knoten im Diagramm und k die Anzahl der Variablen der Funktion ist. Die obere Grenze ist n <= 2^(k+1) - 1 erreicht mit dem vollständigen Binärbaum.
Tags und Links computer-science data-structures compression binary-decision-diagram