Eine Zero-Suppressed Binary Decision Diagram (ZDD) ist eine kompakte, datenstrukturierte Darstellung von Mengen. Sie wird speziell für kombinatorische Probleme verwendet, bei denen eine Vielzahl von Teilmengen einer universellen Menge untersucht werden muss. Durch die Eliminierung redundanter Pfade in der Repräsentation bietet die ZDD eine effiziente Möglichkeit, diese Probleme zu lösen^[1][2].

Grundstruktur der ZDD^[1:1]

1. Knoten:

   • Jeder innere Knoten der ZDD repräsentiert eine Entscheidung, ob ein Element (z. B. eine Kante e_i) in einer Lösung enthalten ist oder nicht.
   • Die Elemente der universellen Menge U = \{e_1, e_2, \dots, e_{\lvert U \rvert}\} werden in einer festen Reihenfolge verarbeitet.

2. 0- und 1-Kanten:

   • Eine 1-Kante (durchgezogene Linie) bedeutet, dass das aktuelle Element e_i in die Lösung aufgenommen wird.
   • Eine 0-Kante (gestrichelte Linie) bedeutet, dass das aktuelle Element e_i nicht Teil der Lösung ist.

3. Terminalknoten:

   • Terminalknoten 1 repräsentiert gültige Lösungen .
   • Terminalknoten 0 repräsentiert ungültige Zustände oder Teilmengen.

4. Reduktion:

   • Die ZDD reduziert redundante Teilgraphen (gleiche Teilmengen mit denselben Eigenschaften) zu einem einzigen Knoten. Dadurch bleibt die Struktur kompakt und effizient.

Die reduzierte ZDD, die Z(1) = \{\{a\}, \{b\}, \{c\}, \{a, c\}, \{b, c\}\} darstellt. E = \{a, b, c\} wobei a < b < c. Gestrichelte Linien repräsentieren 0-Kanten und durchgezogene Linien repräsentieren 1-Kanten.

Der SIMPATH-Algorithmus nach Knuth^[1:2]

Der SIMPATH-Algorithmus von Donald Knuth ist ein Ansatz zur Konstruktion einer ZDD, die alle s-t-Pfade in einem ungerichteten Graphen G = (V, E) repräsentiert. Dabei stellt die ZDD sicher, dass nur gültige Pfade (ohne Zyklen und mit korrekten Start- und Endpunkten) erfasst werden.

Die Mate-Funktion ist ein zentrales Konzept des SIMPATH-Algorithmus. Sie verfolgt den Verbindungszustand der Knoten im Graphen basierend auf den bisher getroffenen Entscheidungen über die Kanten. Weitere Details zur Mate-Funktion finden Sie hier.

Schritte des SIMPATH-Algorithmus

Betrachten wir den Graphen G mit den Knoten V = { p, q, r, s } und den Kanten E = { e_1, e_2, e_3, e_4 }. .

Hinweis:
Jede Kante wird in einer festen Reihenfolge verarbeitet, wobei gilt: e_1 \leq e_2 \leq \dots. Diese Reihenfolge sorgt für Konsistenz und erleichtert den Aufbau der Zero-Suppressed Decision Diagram (ZDD)

Ziel:
Unser Ziel ist es, ein Path Matching zu erreichen.

1. Initialisierung

• Der Wurzelknoten n_{\text{root}} repräsentiert den leeren Pfad (E(\pi) = \emptyset).

Definition von E(\pi)

Ein Pfad \pi in einer ZDD ist gültig, wenn er in einem Terminalknoten 1 endet. Die Menge E(\pi) umfasst alle Kanten e_j, die durch 1-Kanten im Pfad \pi ausgewählt wurden:
„E(\pi) = \{ e_j \mid \text{die 1-Kante eines Knotens mit } e_j \text{ in } \pi \text{ auftritt} \}“.
Kurz: E(\pi) ist die Menge der Kanten, die im Pfad \pi enthalten sind.

• Anfangszustand der Mate-Funktion: \text{mate}(v) = v für alle v \in V. Dies bedeutet, dass alle Knoten zunächst auf sich selbst abgebildet sind, da noch keine Kanten gewählt wurden.

2. Entscheidung für die Kante e_1

Jeder innere Knoten repräsentiert eine Entscheidung für eine Kante e_i: Aufnahme (1-Kante) oder Nichtaufnahme (0-Kante).

• 0-Kante: e_1 wird nicht aufgenommen. Die Mate-Funktion bleibt unverändert.
  
  

• 1-Kante: e_1 wird aufgenommen. Die Mate-Funktion wird aktualisiert, z. B.: \text{mate}(p) = q und \text{mate}(q) = p.
  
  

3. Wiederholung für die Kanten e_2

Der Algorithmus wendet die gleiche Entscheidungsmethode für die nächste Kante e_2 an, wobei die Mate-Funktion entsprechend angepasst wird.

4. Wiederholung für die restlichen Kanten bis |E|

• Der Algorithmus prüft alle Kanten e_i und erstellt schrittweise die ZDD, indem |E| Phasen aufgebaut werden.
• Ungültige Knoten (z. B. durch Zyklen oder unvollständige Verbindungen) werden ausgeschlossen.

5. Abschluss

• Nach der Verarbeitung aller Kanten enthält die ZDD nur gültige Lösungen.
• Redundante Teilgraphen wurden durch die Reduktion zusammengefasst.
• Am Ende sind alle Pfade, die in einem Terminalknoten 1 enden, die möglichen Pfad-Matchings, die wir suchen.

Mate Funktion^[1:3]

Die Mate-Funktion ordnet jedem Knoten im Graphen einen Zustand zu. Dieser Zustand beschreibt, wie der Knoten im aktuellen Pfad verbunden ist.

Definition der Mate-Funktion:

Die Mate-Funktion mate(v) gibt für jeden Knoten v im Graphen den Zustand des Knotens an:

mate(v) =
\begin{cases}
v & \text{wenn } v \text{ Grad 0 hat (nicht verbunden)} \\
u & \text{wenn } u \text{ und } v \text{ verbunden sind} \\
0 & \text{wenn } v \text{ wenn der Knoten v ein Zwischenpunkt(Grad 2), ist (nicht mehr relevant für den Pfad)} \\
\end{cases}

Erklärung der Zustände:

Aufgaben der Mate-Funktion

1. Prüfung auf Zyklen:

   • Die Mate-Funktion verhindert die Bildung von Zyklen im Pfad.

   • Falls ein Zyklus entsteht, wird der entsprechende Knoten aus der ZDD entfernt.

2. Verfolgung von Verbindungen:

   • Die Mate-Funktion stellt sicher, dass Start- und Endknoten korrekt miteinander verbunden werden.

3. Effizienzsteigerung:

   • Ungültige Pfade werden frühzeitig ausgeschlossen, was die Konstruktion der ZDD beschleunigt.

Algorithmus ^[1:4]

Dieser Algorithmus stellt alle möglichen Pfad-Zuordnungen in einem Graphen dar, indem er eine Zero-Suppressed Binary Decision Diagram (ZDD) verwendet. Der Algorithmus durchläuft alle Kanten eines Graphen und prüft, ob diese Kanten in den Pfad aufgenommen werden können.

Pseudocode

 begin

   Erstelle einen Wurzelknoten und zwei Terminalknoten 0 und 1

   Setze N1 ← {n_root}, Ni ← ∅ für i = 2, . . . , |E| und mate_(n_root) als Identität auf V

   Für jede Kante i = 1, . . . , |E|:

     Für jeden Knoten n ∈ Ni:

       Setze das 0-Kind von n auf GN(i + 1, mate_n|V ≥ei+1)

       Wenn maten die Kante ei ablehnt, setze das 1-Kind von n auf 0

       Andernfalls setze das 1-Kind von n auf GN(i + 1, MU(mate_n, ei)|V ≥ei+1)

   Ende

 Rückgabe des erstellten Diagramms

 Ende

Pseudocode-Erklärung

Dieser Algorithmus beschreibt, wie eine Zero-Suppressed Binary Decision Diagram (ZDD) aufgebaut wird, um alle möglichen s-t-Pfade in einem Graphen G=(V, E) zu finden.

Schritt-für-Schritt-Erklärung

1. Initialisierung (Zeilen 2–3)

• Wurzelknoten und Terminalknoten erstellen:

  In Zeile 2 wird der Wurzelknoten n_root erstellt, der den Ausgangspunkt repräsentiert. Zusätzlich werden zwei Terminalknoten (0 und 1) erstellt, um ungültige und gültige Pfade darzustellen.

• Startzustand der Mate-Funktion:

  In Zeile 3 wird die Mate-Funktion des Wurzelknotens initialisiert: Jeder Knoten wird zunächst mit sich selbst verbunden, da zu Beginn keine Kanten ausgewählt wurden.

2. Äußere Schleife: Verarbeitung jeder Kante (Zeile 4)

• Diese Schleife iteriert über alle Kanten des Graphen: e_1, e_2, \dots, e_{|E|}.

• Für jede Kante entscheidet der Algorithmus, ob sie in den Pfad aufgenommen wird oder nicht. Zu jedem Zeitpunkt enthält die Menge N_i die aktiven Knoten für die i-te Phase.

3. Innere Schleife: Verarbeitung jedes Knotens (Zeilen 5–8)

Für jeden Knoten n in der Menge N_i wird geprüft, wie die Kante e_i verarbeitet werden soll:

• Zeile 6: 0-Kante (Ausschluss der Kante):

  Wird die Kante e_i nicht in den Pfad aufgenommen, wird ein Kindknoten über die Funktion GN erstellt. Die Mate-Funktion bleibt dabei unverändert.

• Zeilen 7–8: 1-Kante (Aufnahme der Kante):

  • Wird die Kante e_i in den Pfad aufgenommen, wird die Mate-Funktion durch die Operation MU aktualisiert, um die Verbindung der Knoten widerzuspiegeln.

  • Falls die Aufnahme der Kante zu einem ungültigen Zustand (z. B. Zyklus) führt, wird der Knoten über die 1-Kante mit dem Terminalknoten 0 verbunden.

4. Abschluss der ZDD (Zeile 10)

• Nach der Verarbeitung aller Kanten enthält der ZDD nur gültige Lösungen. Redundante Teilgraphen werden dabei zu einem einzigen Knoten zusammengefasst.

• Schließlich wird das erzeugte Diagramm zurückgegeben, das alle s-t-Pfade repräsentiert.

Schlüsseloperationen

GN(i, m) (Zeilen 6, 8):
Diese Funktion erstellt einen neuen Knoten für die Kante e_i und die Mate-Funktion m. Falls ein Knoten mit demselben Zustand bereits existiert, wird der vorhandene Knoten wiederverwendet.

MU(m, e_i) (Zeile 8):
Diese Funktion aktualisiert die Mate-Funktion, wenn die Kante e_i in den Pfad aufgenommen wird. Sie sorgt dafür, dass die Verbindung zwischen den Knoten korrekt abgebildet wird.

Vorteile der ZDD

1. Effiziente Speicherverwaltung:

   Durch die Reduktion redundanter Teilgraphen benötigt die ZDD deutlich weniger Speicherplatz als andere Methoden.^[3]

2. Kompakte Darstellung:

   Die ZDD stellt nur gültige Lösungen dar, wodurch ungültige Pfade systematisch eliminiert werden.^[1:5]

Referenzen

Abbildungsverzeichnis

Abb. 1,2,3,4,5,6,7: Yoshinaka, Ryo, Toshiki Saitoh, Jun Kawahara, Koji Tsuruma, Hiroaki Iwashita, and Shin-ichi Minato. “Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs.” Algorithms 5, no. 2 (April 5, 2012): 176–213. https://doi.org/10.3390/a5020176.[URL](https://www.mdpi.com/1999-4893/5/2/176)

Literaturverzeichnis