Zero-Suppressed Binary Decision Diagram

Ein Zero-Suppressed Binary Decision Diagram (ZDD) ist eine Spezialform von Binary Decision Diagrams. ZDDs sind unter anderem besonders geeignet, um mögliche Pfade in ungerichteten Graphen kompakt darzustellen. Daher sind sie eine sehr interessante Datenstruktur für das Lösen von Link Puzzles wie Slitherlink.

Definition

Ein ZDD ist nach Yoshinaka et. al.^[1] ein gerichteter azyklischer Graph mit Labels für die einzelnen Knoten und Kanten. Es handelt sich um eine kompakte Repräsentation von Mengenfamilien über einer universellen, total geordneten Menge $E$. Dabei muss Folgendes gelten:

• Es gibt genau einen Wurzelknoten ohne eingehenden Kanten.
• Es gibt genau zwei Endknoten ohne ausgehenden Kanten (0-terminal und 1-terminal).
• Alle Nicht-Endknoten haben zwei ausgehende Kanten mit Label 0 und 1 (0-arc und 1-arc).
• Alle Nicht-Endknoten haben ein Label aus $E$.
• Das Label eines Elternknotena muss entsprechend der totalen Ordnung kleiner als das Label seiner Kindknoten sein.

Eigenschaften

Yoshinaka et. al.^[1:1] definieren für ZDDs folgende Eigenschaften:

Für jeden Knoten $n$ sei das j-child der Knoten, der über das j-arc mit $n$ verbunden ist. Der Elternknoten eines j-childs sei dessen j-parent.

Gültiger Pfad:
Ein Pfad von der Wurzel des ZDDs sei gültig, wenn er nicht in 0-terminal endet.

Reduziert:
Ein ZDD ist reduziert, wenn Folgendes gilt:

• Es gibt keine zwei unterschiedliche Knoten mit gleichen Label, 0-child und 1-child.
• Es gibt keinen Knoten mit 0-terminal als 1-child.

Eine Mengenfamilie repräsentieren:
Für jeden gültigen Pfad \pi kann eine Menge Z(\pi)\subseteq E gebildet werden:
Z(\pi) = \{e | \text{1-arc eines Knoten mit dem Label $e$ ist in $\pi$}\}
Für jeden Knoten n \neq \text{0-terminal} kann eine Menge Z(n) \subseteq 2^E gebildet werden:
Z(n) = \{Z(\pi) | \text{$\pi$ ist ein gültiger Pfad, der in $n$ endet} \}
Das ZDD repräsentiert dann die Mengenfamilie Z(\text{1-terminal}). Für das Beispiel aus Abbbildung 1 gibt es 5 verschiedene gültige Pfade nach 1-terminal:
Z(\text{1-terminal})=\{\{A\},\{B\},\{C\},\{A,C\},\{B,C\}\}

Jedes reduzierte ZDD repräsentiert dieselbe Mengenfamilie wie das entsprechende ZDD in seiner unreduzierten Form. Die ZDDs aus Abbildung 1 und 2 stellen also die gleiche Mengenfamilie dar.

ZDDs um alle möglichen s-t Pfade zu repräsentieren

SIMPATH-Algorithmus (Knuth)

Pseudocode

Kholilurrohman und Minato haben eine Pseudocode-Formulierung für SIMPATH entwickelt^[2], welche hier in angepasster Form beschrieben wird.

initialize mate table;
create root labeled with first edge;
create 0-terminal, 1-terminal;
Q = new Queue;
Q.enqueue(root);
while Q not empty
	node = Q.dequeue;
    for 0-arc/1-arc
    		if state of node in 0-arc/1-arc is not terminal
        		childnode = create new node;
            create 0-arc/1arc from node to childnode;
            Q.enqueue(childnode);
        else
        		create 0-arc/1arc from node to 0-terminal/1-terminal;
reduce ZDD;

Arbeitsweise

SIMPATH ist ein Algorithmus von Donald Knuth^[3], welcher aus einem gegebenen ungerichteten Graphen und zwei Knoten $s, t$ ein ZDD generiert, das alle Pfade zwischen diesen Knoten repräsentiert. Die Idee ist es, Pfade als Mengen von Kanten zu betrachten. Das bedeutet, die Knoten des ZDDs werden mit Kanten aus dem Eingabegraphen gelabelt.

Vor Anwendung des Algorithmus sollten die Knoten $1, \dots, n$ so durchnummeriert werden, dass kein Knoten außer der erste ($s$) vor allen seiner Nachbarn auftritt. Dies kann durch vollständige Breitensuche erreicht werden. Durch die Nummerierung der Knoten gibt es eine Ordnung für die Kanten. Dadurch soll erreicht werden, dass man sich nicht zu viele Informationen von Knoten am Anfang bis zum Ende merken muss.

Der Zustand eines Knoten wird in einer Tabelle mate[1, \dots, n] gespeichert. Dabei gilt:

• mate[i] = i, falls i noch nicht betrachtet wurde.
• mate[i] = 0, falls i bereits zweimal betrachtet wurde.
• mate[i] = r und mate[r]=i, falls bereits untersuchte Kanten einen Pfad mit Endpunkten \{i, r\} bilden.

Initial werden mate[1]=t$, $mate[t]=1 und für alle anderen i \in \{1, \dots, n \}$ $mate[i]=i gesetzt. Zudem werden Wurzelknoten und die beiden Endknoten generiert. Die noch zu untersuchenden Kanten werden in einer Queue gemerkt. Zu Beginn befindet sich nur der Wurzelknoten, welcher die erste Kante repräsentiert, in der Queue. Dann wird in einer Art Breitensuche die Queue durchiteriert. Es wird für jeden Knoten des ZDDs 0-arc und 1-arc untersucht. Falls der Knoten nach 0-arc oder 1-arc in einem Endzustand wäre, wird dieser mit dem entsprechenden Endknoten verbunden, andernfalls wird ein neuer Knoten für das ZDD erzeugt und in die Queue hinzugefügt. Der neue Knoten wird mit der nächsten Kante in der Kantenordnung gelabelt. Für jeden Knoten, der in die Queue hinzugefügt wird, wird zusätzlich der Zustand der $mate$-Tabelle aus Sicht des ZDD-Knotens gespeichert.

mate-Tabelle updaten:
Nach Wahl einer Kante j-m (1-arc) werden die folgenden Updates gemacht:

1. j^* = mate[j]
2. m^* = mate[m]
3. mate[j]=0
4. mate[m]=0
5. mate[j^*] = m^*
6. mate[m^*] = j^*

Endzustände erkennen:
Sei j-m die aktuell zu untersuchende Kante mit j<m. Sei j'-m' die in der nächsten Iteration betrachtete Kante und $l'$ der bisherige Maximalwert für $j_e$ für bereits untersuchte Kanten \{j_1-m_1, j_2-m_2, \dots, j_k-m_k\}. Sei i der kleinste Integer mit i>j und i \neq m.

Es wird der Fall betrachtet, dass wir die Kante auswählen möchten (1-arc). Falls mate[j] = 0 oder mate[m]=0 kann diese Kante nicht ausgewählt werden, d.h. 1-arc zu 0-terminal. Für den Fall, dass mate[j]=m und mate[m]=j, haben wir einen Endzustand gefunden. Falls i \leq l' kann die Kante nicht gewählt werden, d.h. 1-arc zu 0-terminal. Sonst haben wir einen s-t Pfad gefunden, d.h. 1-arc zu 1-terminal.

Falls ein i mit j \leq i < j', mate[i] \neq 0 und mate[i] \neq i existiert, ist der Folgeknoten 0-terminal. Dies gilt sowohl für den Fall, dass die Kante ausgewählt werden soll (1-arc), als auch für den Fall, dass die Kante nicht ausgewählt werden soll (0-arc). Es gibt in diesem Fall einen offenen Endpunkt, d.h. die ein Knoten wurde über eine Kante besucht, kann aber mit den noch zu betrachtenden Knoten nicht mehr erreicht werden.

Beispiel^[3:1]:
Es soll das Vorgehen des SIMPATH-Algorithmus anhand des 3x3-Gitters aus Abbildung 4^[4] für alle Pfade von $1$ nach $9$ betrachtet werden. Sei dabei $mate'$ der Zustand der $mate$-Tabelle nach Auswahl einer Kante (1-arc). Dafür simulieren wir die ersten Iterationen der Queue, die auch in der Animation in Abbildung 3 zu sehen sind.

1. Kante j-m = 1-2.

Keiner der beiden Wege führt zu einem Endzustand. Es wird jeweils ein neuer Knoten im ZDD für die Kante 1-3 erstellt.

2. Kante 1-3, nachdem 1-2 nicht gewählt wurde.

Die nächste zu untersuchende Kante wäre 2-4, d.h. j'=2. Für i=1 gilt j \leq i < j'. Es gilt mate[1] = 9, also mate[1]\neq 0 und mate[1]\neq 1. Somit führt der 0-arc zum 0-terminal Endknoten. In diesem Fall wurde erkannt, dass es keinen Pfad von 1 nach 9 geben kann, welcher weder die Kante 1-2 noch die Kante 1-3 enthält. Der 1-arc führt zu keinem Endzustand.

3. Kante 1-3, nachdem 1-2 gewählt wurde.

Der 0-arc führt zu keinem Endzustand. Wohingegen der 1-arc zu einem Endzustand führt, da mate[j=1]=0. Es kann keinen Pfad von 1 nach 9 geben, der sowohl die Kante 1-2 als auch die Kante 1-3 enthält.

4. Kante $2-4$, nachdem $1-3$ gewählt wurde.

Keiner der beiden Wege führt zu einem Endzustand.

5. Kante 2-4, nachdem 1-2 gewählt wurde.

Keiner der beiden Wege führt zu einem Endzustand.

6. $\dots$

Nachdem alle Knoten in der Queue untersucht worden sind, kann der Graph reduziert werden und es ergibt sich ein Graph wie in Abbildung 5^[4:1].

Relevanz

Es gibt 12 verschiedene Pfade von 1 nach 9 im Graphen aus Abbildung 4. Das ZDD aus Abbildung 5 scheint kein optimaler Ansatz zu sein, um alle Pfade im 3x3-Gitter darzustellen. Bei größeren Graphen wird der Vorteil ersichtlich. Für einen 8x8-Gittergraph gibt es laut Knuth 789.360.053.252 Pfade von der obersten linken in die unterste rechte Ecke, welche durch ein ZDD mit gerade einmal 33580 Knoten dargestellt werden kann.

Referenzen