Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume ::

Binäre Entscheidungsbäume

• Digitallogikschaltungen sind einerseits die Grunglage um unsere Algorithmen ausführen zu können
• Aber Digitallogikschaltungen haben auch etwas mit Graphen und Bäumen zu tun:

1. Eine Digitallogikschaltung sowie jede Elektronikschlatung ist ein Netzwerk aus Bauelementen die miteinander verbunden sind ⇒ nicht gerichteter zyklischer Graph
2. Eine Digitallogikschaltung kann durch Boolesche Algebra, Boolesche Funktionen und Wahrheitstabellen mathematisch modelliert und behandelt werden.
3. Ein Boolesche Funktion kann in einen Baum entwickelt (transformiert) werden!

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Digitallogik

Digitallogik

Digitallogik kann auf verschiedenen Abstraktionsebenen betrachtet werden:

1. Transistorschaltungen (oder noch tiefer Mikrochip / physikalisch)
2. Gatterebene: Und-, Oder-Verknüpfung, Inverter, Kombinationen daraus
3. Blockebene: Addierer, Register, Shieberegister, Multiplexer
4. Boolesche Algebra: Boolesche Funktion (aber nur "zeitlose" kombinatorische Logik)
5. Boolesche Algebra: Entscheidungsbäume oder Entscheidundsdiagramme

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Digitallogik

Digitallogik

bddrued Bäume können auch direkt als Elektronikschaltung implementiert werden!

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Boolesche Funktionen

Boolesche Funktionen

Eine Boolesche Funktion besteht aus:

1. Konstanten, Werten 0/1/False/TRue
2. Variablen (Eingänge einer Digitallogikschaltung)
3. Termen
4. Verknüpfungen: Konjunktion (Und), Disjunktion (Oder), Negation

Eine Boolesche Funktione bildet einen Eingangsvektor x auf einen skalaren Wert y ab:

$${f{{\left(\vec{{x}}\right)}}}=\vec{{x}}\to{y}:{\mathbb{\text{B}}}^{{n}}\to{\mathbb{\text{B}}}\\ {F}{\left(\vec{{x}}\right)}=\vec{{x}}\to\vec{{y}}:{\mathbb{\text{B}}}^{{n}}\to{\mathbb{\text{B}}}^{{m}}\Leftrightarrow\\ {F}{\left(\vec{{x}}\right)}={\left({{f}_{{1}}{\left(\vec{{x}}\right)}},{{f}_{{2}}{\left(\vec{{x}}\right)}},..,{{f}_{{m}}{\left(\vec{{x}}\right)}}\right)}$$

Hat eine Digitallogikschaltung mehr als einen Ausgang y so können diese durch getrennte Boolesche Funktionen berechntet werden.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Boolesche Verknüpfungen

Boolesche Verknüpfungen

Es gibt drei grundlegende Boolesche Operatoren die Boolesche Werte und Variablen zu Termen verknüpfen:

$$\text{Konjunktion}=\text{Und}\Leftrightarrow{a}\wedge{b}\wedge{c}\wedge\ldots\Leftrightarrow{a}\cdot{b}\cdot{c}\cdot..\\ \text{Disjunktion}=\text{Oder}\Leftrightarrow{a}\vee{b}\vee{c}\vee\Leftrightarrow{a}+{b}+{c}+\ldots\\ \text{Negation}:\neg{x}\Leftrightarrow\overline{{x}}$$

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Zerlegung Boolescher Funktionen

Zerlegung Boolescher Funktionen

Man kann jeder Boolesche Funktion nach ihren variablen wie folgt zerlegen:

$${f}={x}_{{i}}·{{f}_{{{x}_{{i}}={1}}}+}\overline{{x}}_{{i}}·{{f}_{{{x}_{{i}}={0}}}}$$

Dabei werden Variablen x einzeln mit den Werten 0 und 1 festgelegt und erzeugen dabei zwei neue Teilfunktionen f_x=0 und f_x=1

Beispiel:

$${f}={a}\cdot{b}+{c}\\ ={a}\cdot{\left({b}+{c}\right)}+\overline{{a}}\cdot{\left({c}\right)}\\ ={b}\cdot{\left({a}+\overline{{a}}\cdot{c}\right)}+\overline{{b}}\cdot{\left({a}\cdot{c}+\overline{{a}}\cdot{c}\right)}$$

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Wahrheitstabellen

Wahrheitstabellen

• Es gilt die Äquivalenz:

Funktion ⇔ Tabelle ⇔ Evaluierungsbaum

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Binäre Entscheidungsbäume

Binäre Entscheidungsbäume

Zur Erinnerung: Ein Baum hat gerichtete Kanten und jeder Knoten hat maximal einen Vorgänger. Ein Graph hat diese Einschränkungen nicht.

(Links) Echter Binärer Entscheidungsbaum (Rechts) Äquivalenter Graph

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Binäre Entscheidungsbäume

Binäre Entscheidungsbäume

Ein BDD is ein Evaluierungsbaum für Boolesche Funktionen (oder Suche von y!) und besteht aus:

1. Knoten n_i die mit Variablen x_j der Booleschen Funktion f(x₁,x₂,..) verknüpft sind.
2. Jeder Knoten n_i(x_j) hat zwei ausgehende Kanten (1) und (0), jeweils eine für x_j=1 und eine (gestrichelt) für x_j=0.
3. Jeder Knoten hat mindestens einen Vorgänger außer dem Wurzelknoten
4. Jeder Ast im Baum ist wieder ein Baum
5. Es gibt nut zwei Arten von Blättern (Terminalknoten): (1) und (0). Diese liefern das Ergebnis der Booleschen Funktion y
6. Allgemein ist ein BDD ein Gerichteter azyklischer Graph (DAG)

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Binäre Entscheidungsbäume

Binäre Entscheidungsbäume

Evaluierung

function Node(xi) { return { type:'Node', left:null, right:null, xindex:xi }  }
function Leave(v) { return { type:'Leave', value:v } }
function evalBDD(root,xv) {
  function iter(node) {
    if (node.type == 'Leave') return node.value // we are done
    if (xv[node.xindex]==1) return iter(node.left)
    else                    return iter(node.right)
  }
  return iter(root)
}
// f(x1=0,x2=1,x3=1)
y=evalBDD(root,[0,1,1])

Evaluierung eines BDD mit 0/1 als Ergebnis

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Binäre Entscheidungsbäume

Erzeugung

Die Probleme:

• Es gibt unendlich viele Bäume die einer Booleschen Funktion f äquivalent sind, da:
• Es gibt unendlich viele Boolesche Funktionen f₁,f₂,... die einer Booleschen Funktion f äquivalent sind
• Die Erzeugung von vollständig geordneten und reduzierten (optimalen) BDD (ROBDD) ist ein NP-vollständiges Problem!

Lösung 1: Shanon Zerlegung wobei jeweils ein Knoten x_i geschaffen wird und die reusltierenden Funktionen den linken und rechten Teilbaum erzeugen werden.

$${f}={x}_{{i}}·{{f}_{{{x}_{{i}}={1}}}+}\overline{{x}}_{{i}}·{{f}_{{{x}_{{i}}={0}}}}$$

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Binäre Entscheidungsbäume

Erzeugung

Lösung 2: Direkt aus einer Wahrheitstabelle

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Binäre Entscheidungsbäume

Erzeugung

BDD Erzeugeung aus Wahrheitstabelle

• Das Gute zuerst: Leiten wir den Baum aus der Wahrheitstabelle durch schtittweise Reduzierung der Zeilen und Spalten (Arrays) mit gordneter Variablenreihenfolge ab dann ist der Baum symmetrisch, vollständig balanziert, und geordnert (Rechenkomplexität der Evaluierung ist O(n) bei n Variablen, die Höhe ist auch n)
• Das Schleche danach: Der Baum ist überbestimmt und kann reduziert werden.

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Binäre Entscheidungsbäume

Erzeugung

bddrued (Links) Geordneter Baum (Rechts) Nicht geordneter Baum

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Binäre Entscheidungsbäume

Erzeugung

function Node(xi) { return { type:'Node', left:null, right:null, xindex:xi }  }
function Leave(v) { return { type:'Leave', value:v } }
// [a,b,c,y]
tt = [[ 0, 0, 0, 0], [ 0, 0, 1, 0], [ 0, 1, 0, 1], [ 0, 1, 1, 1],
      [ 1, 0, 0, 1], [ 1, 0, 1, 0], [ 1, 1, 0, 1], [ 1, 1, 1, 0]]
function split(numvar,index,tt) {
  if (index==numvar-1) {
    node = Node(index)
    node.left  = Leave(tt[0][1])
    node.right = Leave(tt[1][1])
  } else {
    tt1 = map(filter(tt,(row => row[0]==1)),row => tail(row))
    tt0 = map(filter(tt,(row => row[0]==0)),row => tail(row))
    node = Node(index)
    node.left  = split(numvar,index+1,tt1)
    node.right = split(numvar,index+1,tt0) 
  }
  return node
}
root = split(3,0,tt)

Rekursive Erzeugung eines BDD aus Wahrheitstabelle

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: BDD Live

BDD Live

+

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Reduktion von BDD

Reduktion von BDD

(Links) Transformatin 1: Löschen (Rechts) Transformation 2: Zusammenführung

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Reduktion von BDD

Reduktion von BDD

Stefan Bosse - Algorithmen und Datenstrukturen - Modul BDD Binäre Entscheidungsbäume :: Reduktion von BDD

Reduktion von BDD

Der Vorgang ist iterativ und bottom-up.

• Man beginnt bei den Blättern und arbeitet sich bis zur Wurzel hoch.