¶ 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 . 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 .
- 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 sei das -child der Knoten, der über das -arc mit verbunden ist. Der Elternknoten eines -childs sei dessen -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 kann eine Menge gebildet werden:
Für jeden Knoten kann eine Menge gebildet werden:
Das ZDD repräsentiert dann die Mengenfamilie . Für das Beispiel aus Abbbildung 1 gibt es 5 verschiedene gültige Pfade nach 1-terminal:
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 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 so durchnummeriert werden, dass kein Knoten außer der erste () 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 gespeichert. Dabei gilt:
- , falls noch nicht betrachtet wurde.
- , falls bereits zweimal betrachtet wurde.
- und , falls bereits untersuchte Kanten einen Pfad mit Endpunkten bilden.
Initial werden , und für alle anderen 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 -Tabelle aus Sicht des ZDD-Knotens gespeichert.
mate-Tabelle updaten:
Nach Wahl einer Kante (1-arc) werden die folgenden Updates gemacht:
Endzustände erkennen:
Sei die aktuell zu untersuchende Kante mit . Sei die in der nächsten Iteration betrachtete Kante und der bisherige Maximalwert für für bereits untersuchte Kanten . Sei der kleinste Integer mit und .
Es wird der Fall betrachtet, dass wir die Kante auswählen möchten (1-arc). Falls oder kann diese Kante nicht ausgewählt werden, d.h. 1-arc zu 0-terminal. Für den Fall, dass und , haben wir einen Endzustand gefunden. Falls 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 mit , und 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 nach betrachtet werden. Sei dabei der Zustand der -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.
- Kante .
| j | m | ||
|---|---|---|---|
| 1 | 2 | 9 2 3 4 5 6 7 8 1 | 0 9 3 4 5 6 7 8 2 |
Keiner der beiden Wege führt zu einem Endzustand. Es wird jeweils ein neuer Knoten im ZDD für die Kante erstellt.
- Kante , nachdem nicht gewählt wurde.
| j | m | ||
|---|---|---|---|
| 1 | 3 | 9 2 3 4 5 6 7 8 1 | 0 2 9 4 5 6 7 8 3 |
Die nächste zu untersuchende Kante wäre , d.h. . Für gilt . Es gilt , also und . Somit führt der 0-arc zum 0-terminal Endknoten. In diesem Fall wurde erkannt, dass es keinen Pfad von nach geben kann, welcher weder die Kante noch die Kante enthält. Der 1-arc führt zu keinem Endzustand.
- Kante , nachdem gewählt wurde.
| j | m | ||
|---|---|---|---|
| 1 | 3 | 0 9 3 4 5 6 7 8 2 | - |
Der 0-arc führt zu keinem Endzustand. Wohingegen der 1-arc zu einem Endzustand führt, da . Es kann keinen Pfad von nach geben, der sowohl die Kante als auch die Kante enthält.
- Kante , nachdem gewählt wurde.
| j | m | ||
|---|---|---|---|
| 2 | 4 | 0 2 9 4 5 6 7 8 3 | 0 4 9 2 5 6 7 8 3 |
Keiner der beiden Wege führt zu einem Endzustand.
- Kante , nachdem gewählt wurde.
| j | m | ||
|---|---|---|---|
| 2 | 4 | 0 9 3 4 5 6 7 8 2 | 0 0 3 9 5 6 7 8 4 |
Keiner der beiden Wege führt zu einem Endzustand.
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
R. Yoshinaka, T. Saitoh, J. Kawahara, K. Tsuruma, H. Iwashita und S. Minato, "Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs," Algorithms, Jg. 5, Nr. 2, S. 176–213, 2012, doi: 10.3390/a5020176. pdf ↩︎ ↩︎
M. Kholilurrohman und S. Minato, "An Efficient Algorithm for Enumerating Eulerian Paths," TCS Technical Report, 2014. pdf ↩︎
D. E. Knuth, Bitwisetricks & techniques: Binary decision diagrams (The art of computer programming / Donald E. Knuth Vol. 4, Combinatorial algorithms Fasc. 1). Upper Saddle River, NJ: Addison-Wesley, 2009. ↩︎ ↩︎
https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagram#ZDDs_to_represent_simple_paths ↩︎ ↩︎