Binäre Entscheidungsgraphen

Worin wir uns auf die Studienreise in ein anderes Gebiet der Informatik begeben.

Schaltkreisentwerfer wollen möglichst viele nette Dinge auf möglichst wenig Platz unterbringen. Da sind sie schon ganz schon erfinderisch in der Wahl ihrer Methoden. Besonders die Implementation boolescher Schaltungen liegt diesen Leuten am Herzen, weil die meisten Dinge sich um 0 und 1 und deren Verknüpfungen dreht. Im ersten Semester gab es die Primimplikandenmethode zum Verkleinern boolescher Schaltungen. Nun gibt es die optimalen binären Entscheidungsgraphen.

Gegeben sei eine n-stellige boolesche Funktion $f:\{0,1\}^n \longrightarrow \{0,1\}$.Basis der Überlegungen ist eine brute-force-Implementation der Funktion durch eine Kaskade von Anfragen nach den Werten der Argumente. Es entsteht ein Entscheidungsbaum,   dessen innere Knoten Fragen nach einzelnen Argumentwerten und dessen Blätter zugehörige Ergebnisse sind.

Die Abbildung zeigt einen binären Entscheidungsbaum für die gute alte Implikation.

 

Abbildung: Entscheidungsbaum für die Implikation

Alles klar, oder? Der Faulheit zuliebe beschließen wir, daß ab sofort die 0-Ausgänge von Frageknoten mit gestrichelten und die 1-Ausgänge mit durchgezogenen Linien gemalt werden. Dann brauchen wir die Beschriftung mit 1 und 0 nicht extra hinzuschreiben. Außerdem ist klar, daß man jede beliebige n-stellige boolesche Funktion auf diese Weise durch einen Baum der Tiefe n repräsentieren kann. Also einen mit um die 2ⁿ Knoten.

Der Baum ist, wenn man einmal die Ordnung der Argumente festgelegt hat, bis auf Graphisomorphie eindeutig bestimmt. Also eindeutig. Alles, was jetzt passiert, beruht auf einer festgelegten Reihenfolge der Argumentabfragen. Man kann nämlich jede Menge Speicher sparen, wenn man den Baum nach den folgenden beiden Regeln verkleinert.

Regel 1: Wenn Du zwei gleiche Teilbäume findest, streiche den einen und leite seine Eingänge zum anderen um.

 

Abbildung: Gleiche Teilbäume kann man verschmelzen

Regel 2: Wenn beide Ausgänge einer Frage zum selben Knoten führen, lasse die Frage weg.

 

Abbildung 6.3: Redundante Fragen kann man weglassen

Man sieht, daß man anhand des kleineren Entscheidungsgraphen (es ist längst kein Baum mehr) immer noch jeden beliebigen Funktionswert durch eine beim Wurzelknoten beginnende Kaskade von Fragen herausbekommen kann.

Definition 13692 (Entscheidungsgraph)

    Ein azyklischer beschrifteter Graph heißt n-stelliger binärer Entscheidungsgraph, falls

• es genau einen Knoten ohne Vorgänger gibt (die Wurzel);
• die Beschriftungen der Knoten aus $\{ \fbox {0} , \fbox {1} ,x_1,\dots,x_n\}$sind;
• jeder mit x_i beschriftete Knoten genau eine mit 0 und eine mit 1 beschriftete ausgehende Kante besitzt;
• Knoten mit Beschriftung $\fbox {0}$ bzw. $\fbox {1}$ keine Nachfolger haben;
• Die Beschriftung von Kantenquelle immer kleiner als die Beschriftung von Kantenziel ist (per Def. ist x_i < x_j falls i < j und x_i ist immer kleiner als $\fbox {0}$ und $\fbox {1}$).

Die Knoten x_i repräsentieren natürlich Fragen nach dem i-ten Argument der Funktion.

Entscheidungsbäume sind Entscheidungsgraphen. Die beiden Regeln überführen Entscheidungsgraphen wieder in Entscheidungsgraphen. Ein Entscheidungsgraph heißt irreduzibel,   falls keine der Regeln 1 und 2 auf diesen Graphen anwendbar sind.

Die erste nette Eigenschaft von binären Entscheidungsgraphen ist:

Satz 13696

Bei festgelegter Reihenfolge zwischen den x_i gibt es zu jeder booleschen Funktion genau einen irreduziblen Entscheidungsgraphen.

Diesen Graphen können wir mit fug und recht als den optimalen Entscheidungsgraphen bzw. die Normalform der Funktion bezeichnen.

Alles in diesem Kapitel dreht sich einzig und allein um optimale Entscheidungsgraphen. Deren englischer Name ist übrigens (optimal) binary decision diagram, also (O)BDD. Manche Leute spielen damit, die fixe Argumentordnung aufzugeben. Damit machen sie die Sache aber viel komplizierter.

Die Größe eines optimalen Entscheidungsgraphen hängt sehr stark von der gewählten Reihenfolge der Abfrage der Argumente ab. Betrachten wir zum Beispiel die 2n-stellige Funktion $\bigvee_{i=1}^n (a_i \wedge b_i)$.Eine Ordnung der Argumente könnte z.B. $a_1 < b_1 < a_2 < b_2 < \dots < a_n < b_n$ sein. Dann sieht der optimale Entscheidungsgraph wie in dieser Abbildung aus.

 

Abbildung 6.4: Ein optimaler Entscheidungsgraph bei guter Argumentordnung

Dieser Graph hat 2n+2 Knoten, was durchaus linear ist.

Wählen wir statt dessen die Ordnung $a_1 < a_2 < \dots a_n < b_1 < b_2 < \dots b_n$,so sieht der Graph für n = 3 so aus:

 

Abbildung 6.5: Ein nicht so guter, aber auch optimaler Entscheidungsgraph

Man sieht, daß bis zur Hälfte des Baumes gar keine Reduktion passiert. Das muß auch so sein, denn der arme Graph muß sich bis zu diesem Zeitpunkt genau merken, welche der a_i erfüllt sind. Nur dadurch bekommt es heraus, welche b_i es auf Erfülltheit testen muß. Der Graph bleibt exponentiell groß.

Es gibt natürlich auch Sahnebeispiele, z.B. die symmetrischen Funktionen. Eine Funktion ist symmetrisch, falls für alle $x_1 \dots x_n$ und alle i,j gilt: $f(x_1 \dots x_i \dots x_j \dots x_n) = f(x_1 \dots x_j \dots x_i \dots x_n)$.Das heißt, daß der Wahrheitswert nur von der Anzahl der Stellen abhängt, die den Wert eins bekommen.

Wir können zu einer beliebigen Argumentordnung einen (noch nicht optimalen) Graphen konstruieren, der pro Argument max. n Knoten enthält. Zu einem Argument x_i führen wir die Knoten x_i⁽⁰⁾ bis x_i⁽ⁿ⁾ ein. Als Wurzel nehmen wir x₁⁽⁰⁾. Von einem Knoten x_i^(j) ziehen wir den 0-Ausgang zu x_i+1^(j) und den 1-Ausgang zu x_i+1^(j+1). Damit steht jeder Knoten für eine bisherige Zwischensumme. Da das Gesamtergebnis nur von der Anzahl der Einsen abhängt, kann man an den letzten Knoten geeignet Bögen zu den termninalen Knoten $\fbox {0}$ und $\fbox {1}$ ziehen. Wir schmeißen nachträglich alle nicht von der Wurzel erreichbaren Knoten weg. Wenn es also einen Entscheidungsgraph dieser Form, also quadratischer Größe gibt, so hat der optimale Graph höchstens diese Größe. Im Extremfall kann der Graph natürlich konstante Größe haben. So sind die optimalen Graphen für die immer wahre bzw. die immer falsche Funktion einfach $\fbox {0}$ und $\fbox {1}$.

Leider gibt es auch äußerst unsympathische Funktionen. Multipliziert man z.B. zwei n-stelligen Binärzahlen, so entsteht eine maximal 2n-stellige Binärzahl. Die Bestimmung eines jeden dieser 2n Bit kann man einer 2n-stelligen booleschen Funktion überlassen, die beide Argumentzahlen als Input und ihr Ergebnisbit als Output hat. Die beiden Funktionen für die beiden mittleren Bits des Ergbnisses sind die grausamsten. Die haben unabhängig von der Variablenordnung immer einen exponentiell großen optimalen binären Entscheidungsgraphen. Schade drum. Dabei ist Multiplikation soooo wichtig. Wir lernen also, daß die schlußendliche Größe eines optimalen Graphen stark von der repräsentierten Funktion und der gewählten Argumentordnung abhängt. Zu einer zufällig gewürfelten Funktion ist die Größe des Graphen kaum vorhersagbar. Macht aber nix. Wir sind Optimisten und sagen: Immerhin gibt es genug Fälle, wo der optimale Graph deutlich kleiner als der Entscheidungsbaum wird. Und das allein ist schon ziemlich gut.

Das eigentliche Geheimnis der Entscheidungsgraphen ist, daß man optimale Graphen nicht unbedingt aus einem Baum gewinnen muß. Vielmehr kann man neue optimale Graphen aus vorhandenen, schon optimalen Graphen konstruieren.

Wir studieren Konstruktionen, die zu zwei optimalen Graphen für f und g optimale Graphen für h₁ und h₂ konstruieren, wobei $h_1(x_1,\dots,x_n) = f(x_1,\dots,x_n) \circ g(x_1,\dots,x_n)$ ist ($\circ$ ist irgendeine zweistellige boolesche Funktion) und $h_2(x_1,\dots,x_n) = f(x_1,\dots,x_{i-1},b,x_{i+1},\dots,x_n)$($b \in \{0,1\}$). Die erste Konstruktion nennen wir APPLY (apply binary boolean function), die zweite RESTRICT (restrict x_i to value b).

Wir beginnen mit einem Spezialfall von RESTRICT, setzen dann mit APPLY fort und wenden uns zuletzt RESTRICT in voller Allgemeinheit zu.

Zuerst beobochten wir, daß Knoten für Argumente, von denen der Wert der Funktion nicht wirklich abhängt, im Graph auf keinen Fall vorkommen. Wenn wir also die Restriktion   von f auf den Wert b für x_i betrachten (wir schreiben $f \mid_{x_i \mapsto b}$), dann ist der optimale Graph für diese Funktion derselbe, egal ob wir definieren

$$f \mid_{x_1 \mapsto b}(x_1,\dots,x_n) = f(b,x_2,\dots,x_n)$$

oder ob wir definieren

$$f \mid_{x_1 \mapsto b}(x_2,\dots,x_n) = f(b,x_2,\dots,x_n)$$

ob wir also eine neue n-stellige oder eine neue (n-1)-stellige Funktion definieren.

Merksatz 13742

Man kann Argumente, von denen der Funktionswert nicht abhängt, beliebig einfügen oder entfernen, ohne daß sich der optimale Entscheidungsgraph ändert.

Wir konstruieren nun als erste Aufgabe einen optimalen Graph für die Funktion $f \mid_{x_i \mapsto b}$ für den Fall, daß x_i in der Argumentordnung kleiner oder gleich des Arguments im Wurzelknoten ist. Das heißt also, daß der Funktionswert von f von keinem Argument kleiner als dem i-ten (in unserer Ordnung) abhängt. Wir unterscheiden nun zwei Fälle.

Erster Fall: x_i ist nicht die Variable des Wurzelknotens des optimalen Graphen für f. Dann ist der optimale Graph für $f \mid_{x_i \mapsto b}$ genau derselbe wie für f, denn die Restriktion eines Variablenwertes auf einen Wert, von dem der Funktionswert gar nicht abhängt, ändert die Funktion und damit den optimalen Graphen nicht.

Zweiter Fall: x_i ist das Argument des Wurzelknotens. Dann wird in der restriktierten Funktion die Frage nach dem Argument immer mit dem Ausgang b beantwortet. Der optimale Graph für $f \mid_{x_i \mapsto b}$ist also einfach derjenige Teilgraph, der beim Nachfolger des Wurzelknotens über die mit b beschriftete Kante beginnt. Es gibt ja, wenn ein Argument im Wurzelknoten behandelt wird, nur diesen einen Knoten für dieses Argument. Man sieht leicht, daß der entstehende Graph optimal ist.

Beispiel 13761

Wir betrachten die Funktion $f(x_1,x_2,x_3) = x_2 \implies x_3$.Der Graph für f und die Graphen für $f1 = f \mid_{x_1 \mapsto 1}$,$f2 = f \mid_{x_1 \mapsto 0}$, $f3 = f \mid_{x_2 \mapsto 1}$, $f4 = f \mid_{x_2 \mapsto 0}$ sind im nächsten Bild aufgemalt.

 

Abbildung: Einschränkung einer Funktion für weit vorn stehende Argumente

Beachte, daß die Korrektheit der Konstruktion wie auch die Optimalität des Ergebnisses von der Optimalität des Graphen für f abhängen!

Das ist auch bei der zweiten Operation so, schon deshalb, weil wir die erste Konstruktion dort verwenden. Wir geben uns zwei n-stellige Funktionen f und g sowie eine zweistellige Operation $\circ$ vor. Unser Ziel ist es, aus optimalen Graphen für f und g einen optimalen Graphen für $f \circ g$ (mit $f \circ g(x_1,\dots,x_n) = f(x_1,\dots,x_n) \circ g(x_1,\dots,x_n)$) zu konstruieren. Grundlage der Konstruktion ist die sogenannte SHANNON-Expansion.   Diese heißt so, obwohl schon BOOLE sie kannte. Vielleicht, weil nach BOOLE schon so viele Sachen heißen...

Die Shannon-Expansion ist eine logische Äquivalenz, die da für beliebige Funktionen f und alle i zwischen 1 und n lautet:

$$f \equiv (x_i \wedge f \mid_{x_i \mapsto 1}) \vee (\neg x_i \wedge f \mid_{x_i \mapsto 0})$$

Die Bedeutung dieser Formel liegt in deren Nähe zum Prinzip des Entscheidungsbaumes. Sie besagt: Schaue nach, ob x_i gilt oder nicht. Wenn ja, gehe zu einem Teilbaum, der $f \mid_{x_i \mapsto 1}$ repräsentiert, wenn nicht, gehe zu einem Teilbaum, der $f \mid_{x_i \mapsto 0}$ repräsentiert. Verfolgt man die Expansion, beim ersten Argument beginnend, rekursiv weiter und ersetzt konstante Funktionen durch $\fbox {0}$ bzw. $\fbox {1}$, so entsteht haargenau der Entscheidungsbaum. Diese nette Eigenschaft der Expansion wollen wir uns zunutze machen. Denn es gilt weiter:

Diese Formel liefert die Grundlage für unseren Algorithmus APPLY. Wir bilden $f_{x_i \mapsto b}$ und $g_{x_i \mapsto b}$ mit Hilfe der einfachen Version von RESTRICT (wir nehmen einfach immer das am weitesten vorn stehende Argument) und rufen rekursiv unseren Algorithmus APPLY. Bei jedem Ruf von APPLY sinkt die Zahl der Argumente, von denen der Funktionswert potentiell abhängen kann. Zwei konstante Funktionen werden verknüpft, indem $\circ$ angewendet wird und dadurch eine neue konstante Funktion entsteht. Die beiden rekursiven Rufe von APPLY liefern Graphen für $f \mid_{x_i \mapsto 1} \circ g \mid_{x_i \mapsto 1}$und $f \mid_{x_i \mapsto 0} \circ g \mid_{x_i \mapsto 0}$. Wir setzen vor diese beiden Graphen einfach eine neue Wurzel für x_i mit den beiden Resultaten als Nachfolger und fertig ist der neue Graph. Das ist soweit die Grundidee. Sie liefert einen korrekten Graphen. Nur leider keinen optimalen und den auch noch zu langsam.

Beispiel 13791

Betrachte die Funktionen f und g, die durch folgende optimale Graphen gegeben sind. Ich habe jedem Knoten einen Namen gegeben. Im wirklichen Leben kann man diese Namen durch Pointer realisieren. Wir wollen $f \vee g$ berechnen.

 

Abbildung: Zwei zu verknüpfende Funktionen

Als Argumente für den rekursiven Ruf von APPLY geben wir ja immer das Ergebnis eines einfachen RESTRICT mit, also entweder den Eingabegraph oder einen Nachfolgergraph. Wir können der Einfachheit halber die Argumentgraphen völlig unverändert lassen und nur den Pointer auf die jeweils aktuelle Wurzel mitgeben. Dann kann man die rekursive Aufrufstruktur (wo der Ruf für die Restriktion auf 0 wieder gestrichelt und die auf 1 wieder voll gezeichnet wird) durch folgenden Rekursionsbaum (mit Angabe der Argumentpointer) darstellen.

 

Abbildung 6.8: Aufrufstruktur der naiven Implementation

Diese Struktur berücksichtigt schon eine erste Optimierung. Die ODER-Funktion hat nämlich die 1 als dominanten Wert (also braucht man das andere Argument nicht). Kommt man mit ODER also in einen APPLY-Ruf, wo ein Argument die konstante 1 ist (A5 bzw B4), so kann man ungesehen den terminalen Knoten $\fbox {1}$ als Resultat zurückgeben.

Trotz dieser Optimierung wird bei der naiven Implementation mit Zeit und Platz nur so umhergeschmissen. Die Aufrufe mit den Argumenten A3,B2 (und dem Schwanz dahinter) sowie A5,B2 werden doppelt bearbeitet, obwohl doch bei zwei Aufrufen mit ein und denselben Argumenten normalerweise dasselbe Resultat kommen sollte. Erschwerend kommt hinzu, daß im Resultatgraph zweimal derselbe Teilgraph (als Resultat der jeweiligen Aufrufe) erscheint. Das muß verhindert werden. Zu diesem Zweck führen wir eine Tabelle ein, die eine Spalte für jedes Pointerpaar der Argumente hat und eine Spalte für das jeweilige Ergebnis. Am Ende eines Unterrufes von APPLY wird das Argumentpaar mit dem Pointer auf das Ergebnis in die Tabelle eingetragen. Bei jedem APPLY-Ruf wird, bevor so richtig losgerechnet wird, erst in der Tabelle nachgeschaut, ob APPLY für dieses Argumentpaar schon mal gerufen war, und gegebenenfalls das Ergebnis aus der Tabelle entnommen, anstatt es noch mal auszurechnen. Dadurch werden bereits eine Reihe gleicher Teilgraphen verschmolzen. Die Tabelle kann man als Hash-Tabelle mit dem Argumentpaar als Index organisieren, so daß bei hervorragender Streuung konstante Zugriffszeiten resultieren.

Wir schauen uns die neue Aufrufstruktur an, wobei wir den Rückgriff auf die Tabelle durch Umlenken der Aufrufkante dokumentieren. Den entstehenden Graph und die vollständig (in der richtigen Reihenfolge) gefüllte Tabelle malen wir dahinter.

 

Abbildung: Vermeidung doppelter Rufe für gleiche Argumente

9 Rufe anstatt 13. Wenn das nix ist!? Ach so, der Resultatgraph und die Tabelle. Die Pointer für den Resultatgraphen sind in der Reihenfolge ihrer Entstehung numeriert.

 

Abbildung 6.10: Entstehender Graph nach erster Optimierung

 

Argumente Ergebnis

A4,B3 C1

A5,B4 C2

A3,B2 C3

A5,B2 C4

A6,B2 C5

A2,B2 C6

A3,B4 C7

A6,B5 C8

A1,B1 C9

Leider immer noch nicht optimal. Nicht nur, daß wir viel zu viele Kopien der terminalen Knoten haben, nach deren Verschmelzung entstehen auch noch zusätzliche Unoptimalitäten (gibt es dieses Wort?). In unserem Beispiel wird der rechte Test auf x3 redundant. Eine zweite Hash-Tabelle muß her, um dieses Problem zu beseitigen. Dort tragen zu jedem erzeugten Knoten des neuen Baumes eine Zeile ein. Wir tragen als Index die Beschriftung des Knotens ein ($\fbox {0} , \fbox {1} ,x_1,\dots,x_n$) und für nichtterminale Knoten die beiden Nachfolgeknotenpointer. Als andere Spalte tragen wir den Pointer auf den neu erzeugten Knoten ein. Diese Tabelle würde, wenn wir sie in unserem Beispiel einfach erzeugen, aber nicht auswerten, so aussehen.

Knotenstruktur Pointer C1 C2

x4, C1,C2 C3 C4

x3,C3,C4 C5

x2,C3,C5 C6 C7

x3,C4,C7 C8

x1,C6,C8 C9

Man sieht, daß die zu verschmelzende Knoten gleichen Index haben. Bevor also ein Aufruf von APPLY einen neuen Knoten erzeugt, schaut es in der zweiten Tabelle nach, ob es einen Knoten mit demselben Test und denselben Nachfolgegraphen bereitsgibt. Wenn ja, erzeugt es keinen neuen Knoten, sondern übergibt den in der Tabelle gespeicherten. Damit wird verhindert, daß der neue Graph gleiche Teilgraphen mehrfach enthält. Außerdem schaut APPLY nach, ob beide Teilgraphen vielleicht denselben Index in der zweiten Tabelle haben. In diesem Fall wird kein neuer Knoten erzeugt, sondern gibt einfach den (für beide Seiten gleichen) Pointer zurück. So verhindert man, daß im neuen Graphen redundante Tests entstehen. Mit der zweiten Tabelle erreicht man tatsächlich, daß das Resultat ein optimaler Entscheidungsgraph wird.

Um mein Skript schön dick zu machen, gebe ich noch einmal den kompletten Trace der optimalen Berechnung und die beiden dann entstehenden Tabellen an. Den Ergebnisgraph auch.

1.

Ruf von $APPLY(A1,B1,\vee)$. Beide Tabellen sind leer. Also arbeiten.

2.

Anwendung von RESTRICT mit $x1 \mapsto 0$ auf beide Argumente. Es resultieren A2 und B2.

(a)

Ruf von $APPLY(A2,B2,\vee)$. Tabelle 1 leer, also arbeiten.

(b)

RESTRICT mit $x2 \mapsto 0$. Es resultieren A3 und B2.

i.

Ruf von $APPLY(A3,B2,\vee)$. Tabelle 1 leer, also arbeiten,

ii.

RESTRICT mit $x4 \mapsto 0$. Es resultieren A4 und B3.

a.

Ruf von $APPLY(A4,B3,\vee)$. Argumenttupel in Tabelle 1 nicht vorhanden, also arbeiten.

b.

Beide Argumente konstant. Also planen wir die Erzeugung von $\fbox {0}$.

c.

Tabelle 2 leer, also: erzeuge Knoten (C1) mit Inschrift $\fbox {0}$.

d.

Eintrag $( \fbox {0} \mid C1)$ in Tabelle 2,

e.

Eintrag $(A4,B3 \mid C1)$ in Tabelle 1;

f.

fertig.

iii.

RESTRICT mit $x4 \mapsto 1$. Es resultieren A5 und B4.

a.

Ruf von $APPLY(A5,B4,\vee)$. Argumenttupel nicht in Tabelle 1, also arbeiten.

b.

Beide Argumente konstant. Also planen wir die Erzeugung von $\fbox {1}$.

c.

Tabelle 2 enthält keinen Eintrag mit $\fbox {1}$, also: erzeuge Knoten (C2) mit Inschrift $\fbox {1}$.

d.

Eintrag $( \fbox {1} \mid C2)$ in Tabelle 2,

e.

Eintrag $(A5,B4 \mid C2)$ in Tabelle 1;

f.

fertig.

iv.

Nullnachfolger hat C1 geliefert, Einsnachfolger hat C2 geliefert. Also kein redundanter Test. Also plane Erzeugung eines Knotens für x4 mit Nachfolgern C1 und C2.

v.

Es gibt keinen Eintrag mit Index (x4,C1,C2) in Tabelle 2. Also erzeuge neuen Knoten (C3) mit Inschrift C3 und Nachfolgern C1 für 0 und C2 für 1.

vi.

Eintrag $(x4,C1,C2 \mid C3)$ in Tabelle 2

vii.

Eintrag $(A3,B2 \mid C3)$ in Tabelle 1

viii.

fertig.

(c)

RESTRICT mit $x2 \mapsto 1$. Es resultieren A6 und B2.

i.

Ruf von $APPLY(A6,B2,\vee)$. Argumenttupel nicht in Tabelle 1, also arbeiten.

ii.

RESTRICT mit $x3 \mapsto 0$. Es resultieren A3 und B2.

a.

Ruf von $APPLY(A3,B2,\vee)$. Argumenttupel in Tabelle 1 drin, also Rückgabe des Tabellenwertes C3. Fertig.

iii.

RESTRICT mit $x3 \mapsto 1$. Es resultieren A5 und B2.

a.

Ruf von $APPLY(A5,B2,\vee)$. Argumenttupel hat keinen Eintrag in Tabelle 1, also arbeiten.

b.

A5 ist konstant, bei für ODER dominantem Wert. Also plane Erzeugung eines Knotens mit Inschrift $\fbox {1}$.

c.

Eintrag $\fbox {1}$ in Tabelle 2 vorhanden, also Rückgabe des Tabellenwertes C2.

d.

Eintrag von $(A5,B2\mid C2)$ in Tabelle 1

e.

fertig.

iv.

Nullnachfolger ist C3, Einsnachfolger ist C2. Beide verschieden, also kein redundanter Test. Also plane Knoten für x3 mit Nachfolgern C3 und C2.

v.

Kein Eintrag (x3,C3,C2) in Tabelle 2, also wirklich neuen Knoten erzeugen (C4) mit Inschrift x3, Nullnachfolger C3 und Einsnachfolger C2.

vi.

Eintrag $(A6,B2 \mid C4)$ in Tabelle 1.

vii.

Eintrag $(x3,C3,C2 \mid C4)$ in Tabelle 2.

viii.

fertig.

(d)

Nullruf lieferte C3, Einsruf lieferte C4. Beide verschieden, also plane neuen Knoten.

(e)

Kein Eintrag (x2,C3,C4) in Tabelle 2, also wirklich neuen Knoten (C5) mit Inschrift x2, Nullnachfolger C3 und Einsnachfolger C4 erzeugen.

(f)

Eintrag $(x2,C3,C4 \mid C5)$ in Tabelle 2

(g)

Eintrag $(A2,B2 \mid C5)$ in Tabelle 1.

(h)

fertig.

3.

RESTRICT mit $x1 \mapsto 1$ Ergebnis: A6 und B5.

(a)

Ruf von $APPLY(A6,B5,\vee)$. Argumenttupel nicht in Tabelle 1, also arbeiten.

(b)

RESTRICT mit $x3 \mapsto 0$. Ergebnis: A3 und B4.

i.

Ruf von $APPLY(A3,B4,\vee)$. Argumenttupel nicht in Tabelle 1, also arbeiten.

ii.

B4 ist konstant, bei für ODER dominantem Wert. Also plane Erzeugung von $\fbox {1}$.

iii.

Dieser Eintrag existiert in Tabelle 2, also Rückgabe des Tabellenwertes C2.

iv.

Eintrag $(A3,B4 \mid C2)$ in Tabelle 1.

v.

Fertig.

(c)

RESTRICT mit $x3 \mapsto 1$. Ergebnis: A5 und B2.

i.

Ruf von $APPLY(A5,B2,\vee)$. Argumenttupel in Tabelle 1 vorhanden, also Rückgabe des Tabellenwertes C2. Fertig.

(d)

Beide rekursiven Rufe liefern C2. Also redundanter Test.

(e)

Eintrag ($A6,B5 \mid C2$) in Tabelle 1. Rückgabe C2. Fertig.

4.

Nullruf liefert C5, Einsruf C2. Also kein redundanter Test.

5.

Plane Erzeugung eines Knotens mit Inschrift x1 und Nachfolgern C5 und C2.

6.

Kein Eintrag in Tabelle 2 für (x1,C5,C2). Also neuen Knoten (C6) erzeugen mit Inschrift x1, Nullnachfolger C5 und Einsnachfolger C2.

7.

Eintrag $(x1,C5,C2 \mid C6)$ in Tabelle 2.

8.

Eintrag (A1,B1,C6) in Tabelle 1.

9.

Endgültig fertig.

Der entstehende Graph steht in Abbildung 6.11.

  

Abbildung 6.11: Optimaler Graph des Beispielproblems

Die Tabellen haben folgende Gestalt:

 

3||c||Tabelle 1 3|c||Tabelle 2

Index Pointer Eintrag in Index Pointer Eintrag in

A4,B3 C1 2.2.2.5. C1 2.2.2.4.

A5,B4 C2 2.2.3.5. C2 2.2.3.4.

A3,B2 C3 2.2.7. x4,C1,C2 C3 2.2.6.

A5,B2 C2 2.3.3.4. x3,C3,C2 C4 2.3.7.

A6,B2 C4 2.3.6. x2,C3,C4 C5 2.6.

A2,B2 C5 2.7. x1,C5,C2 C6 7.

A3,B4 C2 3.3.4.

A6,B5 C2 3.5.

A1,B1 C6 8.

Innerhalb eines Rekursionslevels hält sich APPLY nur konstante Zeit auf, so man denn die Suche in den Tabellen mit konstanter Zeit ansetzt (das setzt gut streuende und wohldimensionierte Hash-Techniken voraus. Das einfache RESTRICT kostet im Prinzip gar nix. Dank Tabelle 1 wird jedes Argumentpaar maximal einmal wirklich bearbeitet. Demnach belaufen sich die Gesamtkosten (sowohl Zeit als auch Speicher) eines APPLY auf $O(\vert f\vert \cdot \vert g\vert)$, wobei |f| die Größe des optimalen Graphen von f sein soll. Das ist ziemlich gut. Bei anderen Repräsentationsformen boolescher Funktionen kann das Ergebnis deutlich stärker ausarten.

Wenden wir uns nun dem allgemeinen RESTRICT zu. Wir wollen also einen optimalen Graph für $f \mid_{x_i \mapsto b}$ berechnen. Dabei soll x_i aber irgendeine Variable sein und nicht eine an so angenehmer Position stehende wie vorhin. Die grundlegende Technik ist natürlich, die zu x_i gehörenden Knoten aufzusuchen und deren eingehende Kanten auf den Nachfolger des x_i-Knotens in Richtung b umzuleiten. Dadurch können allerdings Unoptimalitäten entstehen. Erfahren, wie wir sind, können wir diese Unoptimalitäten ganz souverän mit Hilfe einer Tabelle wie die APPLY-Tabelle 2 ausmerzen. Für die Suche nach den x_i-Knoten nehmen wir aus alter Gewohnheit den Tiefensuchalgorithmus.

Ein voll durchexerziertes Beispiel soll genügen, uns von der Implementierbarkeit von RESTRICT zu überzeugen.

  

Abbildung: Argument für Anwendung von RESTRICT

Für die durch Abbildung 6.12 gegebene Funktion f wollen wir $f \mid_{x2 \mapsto 1}$ berechnen.

1.

Suche beginnt Abstieg bei A1 Richtung 0.

2.

Suche bei A1 findet Knoten A2 mit x2 beschriftet.

3.

Da Tabelle leer ist, wird $(x3,A3,A5 \mid A4)$ in die Tabelle eingetragen.

4.

Rückgabe von A4 an A1.

5.

Abstieg bei A1 Richtung 1.

6.

Suche findet Knoten A6 mit x2 beschriftet.

7.

Einsnachfolger ist (x3,A3,A5). Also wird A4 lt. Tabelle zurückgegen.

8.

Suche bei A1 lieferte A4 bei 0 und A4 bei 1, also redundanter Test und demnach Rückgabe von A4 als endgültiges Ergebnis.

9.

Garbage-Collection: Streiche A1,A2,A6,A7. Implementation nach Deiner Fantasie, geht aber in Linearzeit.

Die Tabelle hat also in unserem Beispiel nur einen Eintrag, das Ergebnis besteht aus einem einzigen Test auf x3 mit Nullnachfolger und Einsnachfolger . Der Zeitaufwand ist O(|f|). Der Speicherplatz ist höchstens so groß wie vorher.

Eine besonders einfache Operation ist die Negation. Wir müssen einfach die beiden terminalen Knoten austauschen.

Der humane Verbrauch an Laufzeit für APPLY und RESTRICT ist äußerst angenehm, zumal sich weitere Operationen auf diese beiden zurückführen lassen:

• Komposition. Wenn f und g boolesche Funktionen sind, so sei $f \mid_{x_i \mapsto g}$ definiert durch $f \mid_{x_i \mapsto g}(x_1,\dots,x_n) = f(x_1,\dots,x_{i-1},g(x_1,\dots,x_n),x_{i+1},\dots,x_n)$. Es gilt mit Hilfe der Shannon-Expansion: $f \mid_{x_i \mapsto g} \equiv (\neg g \wedge f \mid_{x_i \mapsto 0}) \vee (g \wedge f \mid_{x_i \mapsto 1})$. Damit kann die Komposition durch 2 RESTRICT, eine triviale Negation und 3 APPLY implementiert werden (2 APPLY mit $\wedge$und ein APPLY mit $\vee$).
• Variablenquantifikation $\exists x_i f$ und $\forall x_i f$.Diese sind definiert durch $\exists x_i f \equiv f\mid_{x_i \mapsto 0} \vee f\mid_{x_i \mapsto 1}$ bzw. $\forall x_i f \equiv f\mid_{x_i \mapsto 0} \wedge f\mid_{x_i \mapsto 1}$. Also beide mit 2 RESTRICT und 1 APPLY zu erledigen.

Diese Operationen mögen uns genügen, so daß wir nun von unserer Reise zum Schaltkreisentwurf zurückkehren können.