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]
-
Knoten:
- Jeder innere Knoten der ZDD repräsentiert eine Entscheidung, ob ein Element (z. B. eine Kante ) in einer Lösung enthalten ist oder nicht.
- Die Elemente der universellen Menge werden in einer festen Reihenfolge verarbeitet.
-
0- und 1-Kanten:
- Eine 1-Kante (durchgezogene Linie) bedeutet, dass das aktuelle Element in die Lösung aufgenommen wird.
- Eine 0-Kante (gestrichelte Linie) bedeutet, dass das aktuelle Element nicht Teil der Lösung ist.
-
Terminalknoten:
- Terminalknoten 1 repräsentiert gültige Lösungen .
- Terminalknoten 0 repräsentiert ungültige Zustände oder Teilmengen.
-
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 darstellt. wobei . 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 --Pfade in einem ungerichteten Graphen 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 mit den Knoten und den Kanten . .
Hinweis:
Jede Kante wird in einer festen Reihenfolge verarbeitet, wobei gilt: . 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 repräsentiert den leeren Pfad ().
¶ Definition von
Ein Pfad in einer ZDD ist gültig, wenn er in einem Terminalknoten endet. Die Menge umfasst alle Kanten , die durch 1-Kanten im Pfad ausgewählt wurden:
„“.
Kurz: ist die Menge der Kanten, die im Pfad enthalten sind.
- Anfangszustand der Mate-Funktion: für alle . 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
Jeder innere Knoten repräsentiert eine Entscheidung für eine Kante : Aufnahme (1-Kante) oder Nichtaufnahme (0-Kante).
- 0-Kante: wird nicht aufgenommen. Die Mate-Funktion bleibt unverändert.
- 1-Kante: wird aufgenommen. Die Mate-Funktion wird aktualisiert, z. B.: und .
¶ 3. Wiederholung für die Kanten
Der Algorithmus wendet die gleiche Entscheidungsmethode für die nächste Kante an, wobei die Mate-Funktion entsprechend angepasst wird.
¶ 4. Wiederholung für die restlichen Kanten bis
- Der Algorithmus prüft alle Kanten und erstellt schrittweise die ZDD, indem 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 im Graphen den Zustand des Knotens an:
¶ Erklärung der Zustände:
| Zustand | Beschreibung | Beispiel |
|---|---|---|
| Nicht verbunden | Der Knoten ist nicht mit einem anderen Knoten verbunden (Grad 0) und bleibt mit sich selbst verknüpft. | Ein isolierter Knoten, der noch nicht in den Pfad aufgenommen wurde. |
| Verbunden | Knoten ist mit einem anderen Knoten verbunden (Grad 1). Wird auf abgebildet. | Knoten ist mit Knoten verbunden, somit gilt: . |
| Nicht mehr relevant | Knoten wird als Zwischenpunkt (Grad 2) betrachtet und für den aktuellen Pfad nicht mehr relevant. | Knoten , der bereits als Zwischenpunkt in einem unvollständigen Pfad betrachtet wurde. |
¶ Aufgaben der Mate-Funktion
-
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.
-
-
Verfolgung von Verbindungen:
- Die Mate-Funktion stellt sicher, dass Start- und Endknoten korrekt miteinander verbunden werden.
-
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 --Pfade in einem Graphen zu finden.
¶ Schritt-für-Schritt-Erklärung
¶ 1. Initialisierung (Zeilen 2–3)
-
Wurzelknoten und Terminalknoten erstellen:
In Zeile 2 wird der Wurzelknoten
n_rooterstellt, 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: .
-
Für jede Kante entscheidet der Algorithmus, ob sie in den Pfad aufgenommen wird oder nicht. Zu jedem Zeitpunkt enthält die Menge die aktiven Knoten für die -te Phase.
¶ 3. Innere Schleife: Verarbeitung jedes Knotens (Zeilen 5–8)
Für jeden Knoten in der Menge wird geprüft, wie die Kante verarbeitet werden soll:
-
Zeile 6: 0-Kante (Ausschluss der Kante):
Wird die Kante nicht in den Pfad aufgenommen, wird ein Kindknoten über die Funktion erstellt. Die Mate-Funktion bleibt dabei unverändert.
-
Zeilen 7–8: 1-Kante (Aufnahme der Kante):
-
Wird die Kante in den Pfad aufgenommen, wird die Mate-Funktion durch die Operation 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 --Pfade repräsentiert.
¶ Schlüsseloperationen
GN(i, m)(Zeilen 6, 8):
Diese Funktion erstellt einen neuen Knoten für die Kante und die Mate-Funktionm. 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 in den Pfad aufgenommen wird. Sie sorgt dafür, dass die Verbindung zwischen den Knoten korrekt abgebildet wird.
¶ Vorteile der ZDD
-
Effiziente Speicherverwaltung:
Durch die Reduktion redundanter Teilgraphen benötigt die ZDD deutlich weniger Speicherplatz als andere Methoden.[3]
-
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
¶ Literaturverzeichnis
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 ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎Matsuda, Kotaro, Shuhei Denzumi, and Kunihiko Sadakane. “Storing Set Families More Compactly with Top ZDDs.” Algorithms 14, no. 6 (May 31, 2021): 172. https://doi.org/10.3390/a14060172.URL ↩︎
Zero-suppressed decision diagram (2025, Jan. 19). In Wikipedia. URL ↩︎