[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki8\/2020\/12\/15\/null-unterdrucktes-entscheidungsdiagramm-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki8\/2020\/12\/15\/null-unterdrucktes-entscheidungsdiagramm-wikipedia\/","headline":"Null-unterdr\u00fccktes Entscheidungsdiagramm – Wikipedia","name":"Null-unterdr\u00fccktes Entscheidungsdiagramm – Wikipedia","description":"before-content-x4 EIN Null-unterdr\u00fccktes Entscheidungsdiagramm ((ZSDD oder ZDD) ist eine bestimmte Art von bin\u00e4rem Entscheidungsdiagramm (BDD) mit fester variabler Reihenfolge. Diese","datePublished":"2020-12-15","dateModified":"2020-12-15","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki8\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki8\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/d68ccf3e86906f17c055de25e3c6574532a1b104","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/d68ccf3e86906f17c055de25e3c6574532a1b104","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/wiki8\/2020\/12\/15\/null-unterdrucktes-entscheidungsdiagramm-wikipedia\/","wordCount":10704,"articleBody":" (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4EIN Null-unterdr\u00fccktes Entscheidungsdiagramm ((ZSDD oder ZDD) ist eine bestimmte Art von bin\u00e4rem Entscheidungsdiagramm (BDD) mit fester variabler Reihenfolge. Diese Datenstruktur bietet eine kanonisch kompakte Darstellung von Mengen, die insbesondere f\u00fcr bestimmte kombinatorische Probleme geeignet ist. Erinnern Sie sich an die OBDD-Reduktionsstrategie, dh ein Knoten wird aus dem Entscheidungsbaum entfernt, wenn beide Au\u00dfenkanten auf denselben Knoten zeigen. Im Gegensatz dazu wird ein Knoten in einem ZDD entfernt, wenn seine positive Kante auf den Endknoten 0 zeigt. Dies bietet eine alternative starke Normalform mit verbesserter Komprimierung von d\u00fcnn besetzten S\u00e4tzen. Es basiert auf einer Reduktionsregel von Shin-ichi Minato im Jahr 1993. (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Table of ContentsHintergrund[edit]Definitionen[edit]Darstellung einer Familie von Sets[edit]Beispiel[edit]Eigenschaften[edit]Grundoperationen[edit]Algorithmen[edit]Anwendung[edit]ZDDs als W\u00f6rterb\u00fccher[edit]ZDDs zur Darstellung einfacher Pfade[edit]das Problem der Acht K\u00f6niginnen[edit]Das Tourproblem des Ritters[edit]Fehlersimulation[edit]Siehe auch[edit]Verf\u00fcgbare Pakete[edit]Verweise[edit]Externe Links[edit]Hintergrund[edit]In einem bin\u00e4ren Entscheidungsdiagramm kann eine boolesche Funktion als verwurzelter, gerichteter azyklischer Graph dargestellt werden, der aus mehreren Entscheidungsknoten und Endknoten besteht. 1993 modifizierte Shin-ichi Minato aus Japan Randal Bryants BDDs zur L\u00f6sung kombinatorischer Probleme. Seine “Zero-Suppressed” BDDs zielen darauf ab, sp\u00e4rliche S\u00e4tze von Bitvektoren darzustellen und zu manipulieren. Wenn die Daten f\u00fcr ein Problem als Bitvektoren der L\u00e4nge n dargestellt werden, kann jede Teilmenge der Vektoren durch die Boolesche Funktion \u00fcber n Variablen dargestellt werden, was 1 ergibt, wenn sich der der Variablenzuweisung entsprechende Vektor in der Menge befindet.Laut Bryant ist es m\u00f6glich, Formen von Logikfunktionen zu verwenden, um Probleme mit der Summe der Produkte auszudr\u00fccken. Solche Formen werden oft als S\u00e4tze von “W\u00fcrfeln” dargestellt, die jeweils durch eine Zeichenfolge mit den Symbolen 0, 1 und – gekennzeichnet sind. Zum Beispiel die Funktion (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4((x\u00af1\u2227x2)\u2228((x\u00af2\u2a01x3){ displaystyle ({ bar {x}} _ {1} land x_ {2}) lor ({ bar {x}} _ {2} bigoplus x_ {3})} kann durch das Set veranschaulicht werden {01– –,– –11,– –00}}{ displaystyle {01 -, – 11, -00 }}. Durch Verwendung der Bits 10, 01 und 00 zur Bezeichnung der Symbole 1, 0 bzw. – kann der obige Satz mit Bitvektoren in Form von dargestellt werden {011000,001010,000101}}{ displaystyle {011000,001010,000101 }}. Beachten Sie, dass der Satz von Bitvektoren d\u00fcnn ist, da die Anzahl der Vektoren weniger als 2 betr\u00e4gtnDies ist die maximale Anzahl von Bitvektoren, und die Menge enth\u00e4lt viele Elemente gleich Null. In diesem Fall kann ein Knoten weggelassen werden, wenn das Setzen der Knotenvariablen auf 1 bewirkt, dass die Funktion 0 ergibt. Dies wird unter der Bedingung gesehen, dass eine 1 an einer Bitposition impliziert, dass der Vektor nicht in der Menge ist. Bei sp\u00e4rlichen Mengen ist diese Bedingung h\u00e4ufig, und daher sind viele Knoteneliminierungen m\u00f6glich.Minato hat bewiesen, dass ZDDs besonders f\u00fcr kombinatorische Probleme geeignet sind, wie die klassischen Probleme in zweistufige Logikminimierung, Ritter-Tour-Problem, Fehlersimulation, Timing-Analyse, das N-K\u00f6niginnen-Problem sowie schwache Teilung. Durch die Verwendung von ZDDs kann die Gr\u00f6\u00dfe der Darstellung eines Satzes von n-Bit-Vektoren in OBDDs um h\u00f6chstens einen Faktor von n reduziert werden. In der Praxis ist die Optimierung statistisch signifikant. (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Definitionen[edit]Wir definieren ein Zero-Suppressed Decision Diagram (ZDD) als einen gerichteten azyklischen Graphen, so dass:1. Ein Endknoten ist entweder:Der spezielle \u22a4-Knoten (der TRUE-Knoten) oder:Der spezielle \u22a5-Knoten (der FALSE-Knoten).2. Jeder nicht terminale Knoten erf\u00fcllt die folgenden Bedingungen:ein. Der Knoten ist mit einer positiven Ganzzahl v gekennzeichnet. Diese Bezeichnung muss nicht eindeutig sein.b. Der Knoten hat einen Out-Grad von 2. Eine der ausgehenden Kanten hei\u00dft “LO” und die andere “HI”. (In Diagrammen kann man gepunktete Linien f\u00fcr LO-Kanten und durchgezogene Linien f\u00fcr HI-Kanten zeichnen.)c. Ein Zielknoten ist entweder terminal oder mit einer Ganzzahl gekennzeichnet, die streng gr\u00f6\u00dfer als v ist. Daher kann man Pfeilspitzen in Diagrammen weglassen, da die Kantenrichtungen aus den Beschriftungen abgeleitet werden k\u00f6nnen.d. Die HI-Kante zeigt niemals auf den \u22a5-Knoten.3. Es gibt genau einen Knoten mit einem Grad von Null – den Wurzelknoten. Der Wurzelknoten ist entweder terminal oder durch die kleinste Ganzzahl im Diagramm gekennzeichnet.4. Wenn zwei Knoten dieselbe Bezeichnung haben, zeigen ihre LO- oder HI-Kanten auf unterschiedliche Knoten. Mit anderen Worten, es gibt keine redundanten Knoten.Wir nennen Z eine nicht reduzierte ZDD, wenn eine HI-Kante auf einen \u22a5-Knoten zeigt oder Bedingung 4 nicht gilt. Abbildung 1 und Abbildung 2: Eliminierung von ZDD-Knoten und gemeinsame Nutzung von KnotenIn Computerprogrammen k\u00f6nnen Boolesche Funktionen in Bits ausgedr\u00fcckt werden, sodass der \u22a4-Knoten und der \u22a5-Knoten durch 1 und 0 dargestellt werden k\u00f6nnen. Aus der obigen Definition k\u00f6nnen wir Kombinationss\u00e4tze effizient darstellen, indem wir zwei Regeln auf die BDDs anwenden:1.Entfernen Sie alle Knoten, deren 1-Kante auf den 0-Terminal-Knoten zeigt. Verbinden Sie dann die Kante direkt mit dem anderen Teilgraphen, wie in Abbildung 1 dargestellt.2. Teilen Sie alle \u00e4quivalenten Untergraphen wie bei Original-BDDs.Wenn die Anzahl und die Reihenfolge der Eingabevariablen festgelegt sind, stellt eine Null-unterdr\u00fcckte BDD eine Boolesche Funktion eindeutig dar (wie in Abbildung 2 gezeigt, kann eine BDD zur Darstellung eines Booleschen Bin\u00e4rbaums verwendet werden).Darstellung einer Familie von Sets[edit]Sei F ein ZDD. Sei v sein Wurzelknoten. Dann:1. Wenn v = \u22a5, kann es keine anderen Knoten geben, und F steht f\u00fcr \u00d8, die leere Familie.2. Wenn v = \u22a4, kann es keine anderen Knoten geben, und F steht f\u00fcr die Familie, die nur die leere Menge {\u00d8} enth\u00e4lt. Wir nennen dies eine Einheitsfamilie und bezeichnen sie mit.3. Wenn v zwei Kinder hat. Sei v0 der LO-Knoten und v1 der HI-Knoten. Sei Fi die Familie, die durch das in vi verwurzelte ZDD repr\u00e4sentiert wird, was durch einen Induktionsnachweis gezeigt werden kann. Dann repr\u00e4sentiert F die FamilieF.0\u222a{\u03b1\u222a{v}}\u2223\u03b1\u2208F.1}}{ displaystyle F_ {0} cup { alpha cup {v } mid alpha in F_ {1} }}Man kann den LO-Zweig als die Mengen in F darstellen, die nicht enthalten v::F.0={\u03b1::\u03b1\u2208F.,v\u2209\u03b1}}{ displaystyle F_ {0} = { alpha: alpha in F, v notin alpha }}Und der HI-Zweig als die Mengen in F, die enthalten v::F.1={\u03b1\u2216{v}}::\u03b1\u2208F.,v\u2208\u03b1}}{ displaystyle F_ {1} = { alpha backslash {v }: alpha in F, v in alpha }} Abbildung 3: Elementarfamilie im ZDD Figur 4: {\u2205}}\u222a{\u2205\u222a{2}}}}={\u2205,{2}}}}{ displaystyle { Emptyset } cup { Emptyset cup {2 } } = { Emptyset, {2 } }}Beispiel[edit] Abbildung 5: {{2}}}}\u222a{\u2205\u222a{1}}}}={{1}},{2}}}}{ displaystyle { {2 } } cup { Emptyset cup {1 } } = { {1 }, {2 } }} Abbildung 6:{{1}}\u222a{2}}}}={{1,2}}}}{ displaystyle { {1 } cup {2 } } = { {1,2 } }}Abbildung 3: Die Familie \u2205\u222a{\u2205\u222a{2}}}}={{2}}}}{ displaystyle Emptyset Cup { Emptyset Cup {2 } } = { {2 } }}. Wir k\u00f6nnen das nennen e2{ displaystyle e_ {2}}, eine elementare Familie. Grundfamilien bestehen aus der Form {{n}}}}{ displaystyle { {n } }}und werden mit bezeichnet en{ displaystyle e_ {n}}.Abbildung 4: Die Familie {\u2205}}\u222a{\u2205\u222a{2}}}}={\u2205,{2}}}}{ displaystyle { Emptyset } cup { Emptyset cup {2 } } = { leer, {2 } }}Abbildung 5: Die Familie {{2}}}}\u222a{\u2205\u222a{1}}}}={{1}},{2}}}}{ displaystyle { {2 } } cup { Emptyset cup {1 } } = { {1 }, {2 } }}Abbildung 6: Die Familie {{1}}\u222a{2}}}}={{1,2}}}}{ displaystyle { {1 } cup {2 } } = { {1,2 } }}Eigenschaften[edit]Ein Merkmal von ZDDs ist, dass das Formular nicht von der Anzahl der Eingabevariablen abh\u00e4ngt, solange die Kombinationss\u00e4tze gleich sind. Es ist nicht erforderlich, die Anzahl der Eingabevariablen festzulegen, bevor Diagramme erstellt werden. ZDDs unterdr\u00fccken automatisch die Variablen f\u00fcr Objekte, die niemals in Kombination erscheinen, daher die Effizienz f\u00fcr die Bearbeitung sp\u00e4rlicher Kombinationen. Ein weiterer Vorteil von ZDDs besteht darin, dass die Anzahl der 1-Pfade im Diagramm genau der Anzahl der Elemente im Kombinationssatz entspricht. In urspr\u00fcnglichen BDDs bricht die Knoteneliminierung diese Eigenschaft. Daher sind ZDDs besser als einfache BDDs, um Kombinationss\u00e4tze darzustellen. Es ist jedoch besser, die urspr\u00fcnglichen BDDs zu verwenden, wenn gew\u00f6hnliche Boolesche Funktionen dargestellt werden (siehe Abbildung 7). Abbildung 7: Bitmanipulation und grundlegende Operationen. Abbildung 8: Unterdr\u00fcckung irrelevanter VariablenGrundoperationen[edit]Hier haben wir die grundlegenden Operationen f\u00fcr ZDDs, da sie sich geringf\u00fcgig von denen der urspr\u00fcnglichen BDDs unterscheiden. In Abbildung 8 sind Beispiele aufgef\u00fchrt, die aus der folgenden Tabelle hervorgehen.Empty () gibt \u00f8 zur\u00fcck (leere Menge)Base () gibt {0} zur\u00fcckSubset1 (P, var) gibt die Subset von P zur\u00fcck, wie z var = 1Subset0 (P, var) gibt die Subset von P zur\u00fcck, wie z var = 0Change (P, var) gibt P zur\u00fcck, wenn var ist invertiertUnion (P, Q) kehrt zur\u00fcck (P.\u222aQ.{ displaystyle P cup Q})Intsec (P, Q) gibt zur\u00fcck (P.\u2229Q.{ displaystyle P cap Q})Diff (P, Q) gibt zur\u00fcck (P.– –Q.{ displaystyle PQ})Count (P) kehrt zur\u00fcck |P.|{ displaystyle left vert P right vert}. (Anzahl der Elemente)In ZDDs gibt es keine NOT-Operation, was bei Original-BDDs eine wesentliche Operation ist. Der Grund ist, dass das Komplement gesetzt ist P.\u00af{ displaystyle { bar {P}}} kann nicht berechnet werden, ohne die universelle Menge zu definieren U.{ displaystyle U}. In ZDDs, P.\u00af{ displaystyle { bar {P}}} kann als Diff (U, P) berechnet werden.Algorithmen[edit]Annehmen|P.|=|P.0|+|P.1|{ displaystyle left vert P right vert = left vert P_ {0} right vert + left vert P_ {1} right vert} k\u00f6nnen wir die Anzahl der S\u00e4tze in einem ZDD rekursiv berechnen, wodurch wir den 34. Satz einer 54-k\u00f6pfigen Familie erhalten. Der Direktzugriff ist schnell und jede Operation, die f\u00fcr ein Array von S\u00e4tzen m\u00f6glich ist, kann mit einem ZDD effizient ausgef\u00fchrt werden.Laut Minato k\u00f6nnen die obigen Operationen f\u00fcr ZDDs wie urspr\u00fcngliche BDDs rekursiv ausgef\u00fchrt werden. Um die Algorithmen einfach zu beschreiben, definieren wir die Prozedur Getnode(top, P0, P1) das gibt einen Knoten f\u00fcr eine Variable top und zwei Untergraphen P0 und P1 zur\u00fcck. Wir k\u00f6nnen eine Hash-Tabelle namens uniq-table verwenden, um jeden Knoten eindeutig zu halten. Das Entfernen und Teilen von Knoten wird nur von verwaltet Getnode(). Getnode (top, P0, P1) { if (P1 == \u00f8) return P0; \/* node elimination *\/ P = search a node with (top, P0, P1 ) in uniq-table; if (P exist) return P; \/* node sharing *\/ P = generate a node with (top, P0, P1 ); append P to the uniq-table; return P; }Verwenden von Getnode()k\u00f6nnen wir dann andere grundlegende Operationen wie folgt darstellen: Subset1 (P, var) { if (P.top < var) return \u00f8; if (P.top == var) return P1; if (P.top > var) return Getnode (P.top, Subset1(P0, var), Subset1(P1, var)); } Subset0 (P, var) { if (P.top < var) return \u00f8; if (P.top == var) return P0; if (P.top > var) return Getnode (P.top, Subset0(P0, var), Subset0(P1, var)); } Change (P, var) { if (P.top < var) return Getnode (var, \u00f8, P); if (P.top == var) return Getnode (var, P1, P0); if (P.top > var) return Getnode (P.top, Change(P0, var), Change(P1, var)); } Union (P, Q) { if (P == \u00f8) return Q; if (Q == \u00f8) return P; if (P == Q) return P; if (P.top > Q.top) return Getnode (P.top, Union(P0, Q), P1); if (P.top < Q.top) return Getnode (Q.top, Union(P, Q0), Q1); if (P.top == Q.top) return Getnode (P.top, Union(P0, Q0), Union(P1, Q1)); } Intsec (P, Q) { if (P == \u00f8) return \u00f8; if (Q == \u00f8) return \u00f8; if (P == Q) return P; if (P.top > Q.top) return Intsec(P0, Q); if (P.top < Q.top) return Intsec (P, Q0); if (P.top == Q.top) return Getnode (P.top, Intsec(P0, Q0), Intsec(P1, Q1)); } Diff (P, Q) { if (P == \u00f8) return \u00f8; if (Q == \u00f8) return P; if (P == Q) return \u00f8; if (P.top > Q.top) return Getnode(P.top, Diff(P0, Q), P1;) if (P.top < Q.top) return Diff(P, Q0); if (P.top == Q.top) return Getnode (P.top, Diff(P0, Q0), Diff(P1, Q1)); } Count (P) { if (P == \u00f8) return 0; if (P == {\u00f8}) return 1; return Count(P0) + Count(P1); }Diese Algorithmen ben\u00f6tigen im schlimmsten Fall eine exponentielle Zeit f\u00fcr die Anzahl der Variablen. Wir k\u00f6nnen jedoch die Leistung verbessern, indem wir einen Cache verwenden, der die Ergebnisse der letzten Vorg\u00e4nge in BDDs auf \u00e4hnliche Weise speichert. Der Cache verhindert doppelte Ausf\u00fchrungen f\u00fcr \u00e4quivalente Subgraphen. Ohne Duplikate k\u00f6nnen die Algorithmen in einer Zeit arbeiten, die proportional zur Gr\u00f6\u00dfe der Diagramme ist (siehe Abbildung 9 und 10). Abbildung 9: Ergebnisse im N-Queens-Problem Abbildung 10: Leistung von ZDDs im Vergleich zu BDDsAnwendung[edit]ZDDs als W\u00f6rterb\u00fccher[edit]ZDDs k\u00f6nnen verwendet werden, um die W\u00f6rter mit f\u00fcnf Buchstaben des Englischen darzustellen, die Menge WORDS (Gr\u00f6\u00dfe 5757) aus dem Stanford GraphBase zum Beispiel. Eine M\u00f6glichkeit, dies zu tun, besteht darin, die Funktion zu ber\u00fccksichtigen f((x1,...,x25){ displaystyle f (x_ {1}, ..., x_ {25})} das ist genau dann als 1 definiert, wenn die f\u00fcnf Zahlen ((x1,...,x5)2{ displaystyle (x_ {1}, ..., x_ {5}) _ {2}}, ((x6,...,x10)2{ displaystyle (x_ {6}, ..., x_ {10}) _ {2}}, ..., ((x21,...,x25)2{ displaystyle (x_ {21}, ..., x_ {25}) _ {2}} codieren Sie die Buchstaben eines englischen Wortes, wobei ein=((00001)2{ displaystyle a = (00001) _ {2}}, ..., z=((11010)2{ displaystyle z = (11010) _ {2}}. Zum Beispiel,f((0,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1,0,1,1,0,0,x25)=x25{ displaystyle f (0,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,0,1,1,0,1,1,0 , 0, x_ {25}) = x_ {25}}. Die Funktion von 25 Variablen hat Z (f) = 6233 Knoten - was f\u00fcr die Darstellung von 5757 W\u00f6rtern nicht schlecht ist. Im Vergleich zu Bin\u00e4rb\u00e4umen, Versuchen oder Hash-Tabellen ist ein ZDD m\u00f6glicherweise nicht das Beste, um einfache Suchvorg\u00e4nge durchzuf\u00fchren. Es ist jedoch effizient beim Abrufen von Daten, die nur teilweise angegeben sind, oder von Daten, die nur ungef\u00e4hr einem Schl\u00fcssel entsprechen sollen. Komplexe Abfragen k\u00f6nnen problemlos bearbeitet werden. Dar\u00fcber hinaus enthalten ZDDs nicht so viele Variablen. Tats\u00e4chlich kann man mit einem ZDD diese f\u00fcnf Buchstaben als sp\u00e4rliche Funktion darstellen F.((ein1,...,z1,ein2,...,z2,...,ein5,...,z5){ displaystyle F (a_ {1}, ..., z_ {1}, a_ {2}, ..., z_ {2}, ..., a_ {5}, ..., z_ {5} )}das hat 26 \u00d7 5 = 130 Variablen, wobei Variable ein2{ displaystyle a_ {2}} Bestimmt beispielsweise, ob der zweite Buchstabe \"a\" ist. Um das Wort \"verr\u00fcckt\" darzustellen, kann man F wahr machen, wenn c1=r2=ein3=z4=y5=1{ displaystyle c_ {1} = r_ {2} = a_ {3} = z_ {4} = y_ {5} = 1} und alle anderen Variablen sind 0. Somit kann F als eine Familie betrachtet werden, die aus den 5757 Teilmengen besteht {w1,h2,ich3,c4,h5}}{ displaystyle {w_ {1}, h_ {2}, i_ {3}, c_ {4}, h_ {5} }}usw. Mit diesen 130 Variablen betr\u00e4gt die ZDD-Gr\u00f6\u00dfe Z (F) tats\u00e4chlich 5020 anstelle von 6233. Laut Knuth betr\u00e4gt die \u00e4quivalente Gr\u00f6\u00dfe von B (F) unter Verwendung eines BDD 46.189 - deutlich gr\u00f6\u00dfer als Z (F). Trotz \u00e4hnlicher Theorien und Algorithmen \u00fcbertreffen ZDDs BDDs f\u00fcr dieses Problem mit einem ziemlich gro\u00dfen Spielraum. Folglich k\u00f6nnen wir mit ZDDs bestimmte Abfragen ausf\u00fchren, die f\u00fcr BDDs zu l\u00e4stig sind. Komplexe Familien von Teilmengen k\u00f6nnen leicht aus Elementarfamilien konstruiert werden. Um nach W\u00f6rtern zu suchen, die ein bestimmtes Muster enthalten, kann man zur Berechnung die Familienalgebra auf ZDDs verwenden ((F.\/.P.)\u2294P.{ displaystyle (F \/ P) sqcup P} wobei P das Muster ist, z ein1\u2294h3\u2294e5{ displaystyle a_ {1} sqcup h_ {3} sqcup e_ {5}}. Abbildung 11: Ein Raster von drei mal dreiZDDs zur Darstellung einfacher Pfade[edit]Man kann ZDDs verwenden, um einfache Pfade in einem ungerichteten Graphen darzustellen. Zum Beispiel gibt es 12 M\u00f6glichkeiten, von der oberen linken Ecke eines Drei-mal-Drei-Gitters (siehe Abbildung 11) zur unteren rechten Ecke zu gelangen, ohne einen Punkt zweimal zu besuchen. Abbildung 12: 12 m\u00f6gliche Pfade, um eine Ecke zur anderen diagonalen Ecke zu f\u00fchrenDiese Pfade k\u00f6nnen durch das in Abbildung 13 gezeigte ZDD dargestellt werden. In diesem ZDD erhalten wir den ersten Pfad, indem wir die HI-Zweige am Knoten 13, Knoten 36, Knoten 68 und Knoten 89 des ZDD nehmen (LO-Zweige, die einfach zu \u22a5 gehen weggelassen werden). Obwohl der ZDD in Abbildung 13 keineswegs signifikant erscheint, werden die Vorteile eines ZDD offensichtlich, wenn das Gitter gr\u00f6\u00dfer wird. Beispielsweise ergibt sich f\u00fcr ein Raster von acht mal acht die Anzahl der einfachen Pfade von Ecke zu Ecke zu 789, 360.053.252 (Knuth). Die Pfade k\u00f6nnen mit 33580 Knoten unter Verwendung eines ZDD dargestellt werden. Abbildung 13: ZDD f\u00fcr die einfachen Pfade eines Drei-mal-Drei-GittersRandal Bryant schlug ein Beispiel aus der Praxis f\u00fcr einfache Wege vor: \u201eAngenommen, ich wollte eine Fahrt durch die kontinentalen USA machen, alle Landeshauptst\u00e4dte besuchen und nur einmal durch jeden Staat fahren. Welchen Weg sollte ich nehmen, um die Gesamtentfernung zu minimieren? \u201c Abbildung 14 zeigt ein ungerichtetes Diagramm f\u00fcr diese Roadmap, wobei die Zahlen die k\u00fcrzesten Entfernungen zwischen benachbarten Hauptst\u00e4dten angeben. Das Problem besteht darin, eine Teilmenge dieser Kanten auszuw\u00e4hlen, die einen Hamilton-Pfad mit der kleinsten Gesamtl\u00e4nge bilden. Jeder Hamilton-Pfad in diesem Diagramm muss entweder in Augusta, Maine (ME) beginnen oder enden. Angenommen, man beginnt in CA. Man kann ein ZDD finden, das alle Pfade von CA nach ME charakterisiert. Laut Knuth hat dieses ZDD nur 7850 Knoten und zeigt effektiv, dass genau 437.525.772.584 einfache Pfade von CA nach ME m\u00f6glich sind. Nach Anzahl der Kanten ist die Erzeugungsfunktion 4z11+124z12+1539z13+...+33385461z46+2707075z47{displaystyle 4z^{11}+124z^{12}+1539z^{13}+...+33385461z^{46}+2707075z^{47}};Die l\u00e4ngsten derartigen Pfade sind also Hamilton-Pfade mit einer Gr\u00f6\u00dfe von 2.707.075. ZDDs sind in diesem Fall f\u00fcr einfache Pfade und Hamilton-Pfade effizient. Abbildung 14: Eine ungerichtete Grafik der kontinentalen US-Bundesstaatendas Problem der Acht K\u00f6niginnen[edit]Definieren Sie 64 Eingabevariablen, um die Quadrate auf einem Schachbrett darzustellen. Jede Variable bezeichnet die Anwesenheit oder Abwesenheit einer K\u00f6nigin auf diesem Feld. Ber\u00fccksichtige das,In einer bestimmten Spalte ist nur eine Variable \"1\".In einer bestimmten Zeile ist nur eine Variable \"1\".Auf einer bestimmten diagonalen Linie ist eine oder keine Variable \"1\".Obwohl man dieses Problem durch die Konstruktion von OBDDs l\u00f6sen kann, ist es effizienter, ZDDs zu verwenden. Die Erstellung eines ZDD f\u00fcr das 8-Queens-Problem erfordert 8 Schritte von S1 bis S8. Jeder Schritt kann wie folgt definiert werden:S1: Repr\u00e4sentiert alle M\u00f6glichkeiten, eine K\u00f6nigin in die erste Reihe zu setzen.S2: Repr\u00e4sentiert alle M\u00f6glichkeiten, eine K\u00f6nigin in die zweite Reihe zu setzen, um die erste K\u00f6nigin nicht zu verletzen.S3: Stellt alle M\u00f6glichkeiten dar, eine K\u00f6nigin in die dritte Reihe zu setzen, damit die vorherigen K\u00f6niginnen nicht verletzt werden.\u2026S8: Stellt alle M\u00f6glichkeiten dar, eine K\u00f6nigin in die achte Reihe zu setzen, damit sie nicht gegen die vorherigen K\u00f6niginnen verst\u00f6\u00dft.\t\tDas ZDD f\u00fcr S8 besteht aus allen m\u00f6glichen L\u00f6sungen des 8-Queens-Problems. F\u00fcr dieses spezielle Problem kann das Zwischenspeichern die Leistung des Algorithmus erheblich verbessern. Die Verwendung des Cache zur Vermeidung von Duplikaten kann die N-Queens-Probleme bis zu 4,5-mal schneller verbessern als die Verwendung der nur grundlegenden Operationen (wie oben definiert) (siehe Abbildung 10).Das Tourproblem des Ritters[edit]\t\tDas Tourproblem des Ritters hat eine historische Bedeutung. Die Grafik des Ritters enth\u00e4lt n2 Eckpunkte zur Darstellung der Quadrate des Schachbretts. Die Kanten veranschaulichen die legalen Bewegungen eines Ritters. Der Ritter kann jedes Feld des Bretts genau einmal besuchen. Olaf Schr\u00f6er, M. L\u00f6bbing und Ingo Wegener n\u00e4herten sich diesem Problem, und zwar auf einer Tafel, indem sie jeder Kante im Diagramm Boolesche Variablen zuweisen, wobei insgesamt 156 Variablen zur Bezeichnung aller Kanten verwendet wurden. Eine L\u00f6sung des Problems kann durch einen 156-Bit-Kombinationsvektor ausgedr\u00fcckt werden. Laut Minato ist der Aufbau eines ZDD f\u00fcr alle L\u00f6sungen zu gro\u00df, um direkt gel\u00f6st zu werden. Es ist einfacher zu teilen und zu erobern. Durch Aufteilen der Probleme in zwei Teile des Boards und Erstellen von ZDDs in Teilr\u00e4umen kann das Tourproblem von The Knight mit jeder L\u00f6sung mit 64 Kanten gel\u00f6st werden. Da der Graph jedoch nicht sehr d\u00fcnn ist, ist der Vorteil der Verwendung von ZDDs nicht so offensichtlich.Fehlersimulation[edit]\t\tN. Takahashi et al. Schlugen eine Fehlersimulationsmethode f\u00fcr mehrere Fehler unter Verwendung von OBDDs vor. Diese deduktive Methode \u00fcbertr\u00e4gt die Fehlers\u00e4tze von den prim\u00e4ren Eing\u00e4ngen zu den prim\u00e4ren Ausg\u00e4ngen und erfasst die Fehler an den prim\u00e4ren Ausg\u00e4ngen. Da diese Methode unate Cube-Set-Ausdr\u00fccke umfasst, sind ZDDs effizienter. Die Optimierungen von ZDDs in Unate-Cube-Set-Berechnungen zeigen, dass ZDDs bei der Entwicklung von VLSI-CAD-Systemen und in einer Vielzahl anderer Anwendungen n\u00fctzlich sein k\u00f6nnten.Siehe auch[edit]Verf\u00fcgbare Pakete[edit]CUDD: Ein in C geschriebenes BDD-Paket, das BDDs und ZBDDs implementiert, University of Colorado, BoulderJDD, Eine Java-Bibliothek, die allgemeine BDD- und ZBDD-Operationen implementiertGraphillion, Eine auf Python basierende ZDD-Softwareimplementierung[1], Eine CWEB ZDD-Implementierung von Donald Knuth.Verweise[edit]Shin-ichi Minato, \"Null-unterdr\u00fcckte BDDs zur Manipulation von S\u00e4tzen bei kombinatorischen Problemen\", DAC '93: Vortr\u00e4ge der 30. internationalen Konferenz \u00fcber Designautomatisierung, 1993CH. Meinel, T. Theobald, \"Algorithmen und Datenstrukturen im VLSI-Design: OBDD - Grundlagen und Anwendungen \", Springer-Verlag, Berlin, Heidelberg, New York, 1998.Minato, Shin-ichi. \"Null-unterdr\u00fcckte BDDs und ihre Anwendungen.\" https:\/\/eprints.lib.hokudai.ac.jp\/dspace\/bitstream\/2115\/16895\/1\/IJSTTT3-2.pdf, Hokkaido University, Mai 2001, https:\/\/eprints.lib.hokudai.ac.jp\/dspace\/bitstream\/2115\/16895\/1\/IJSTTT3-2.pdf.Minato, Shin-ichi. \"Null unterdr\u00fcckte BDDs f\u00fcr die Manipulation von S\u00e4tzen bei kombinatorischen Problemen.\" 1993, doi:https:\/\/pdfs.semanticscholar.org\/9593\/6223362a16a50de2959475d87aefe2a1fec7.pdf.Bryant, Randal E. \"Bin\u00e4re Entscheidungsdiagramme und dar\u00fcber hinaus: Erm\u00f6glichung von Technologien f\u00fcr die formale \u00dcberpr\u00fcfung.\" http:\/\/Repository.cmu.edu\/Cgi\/Viewcontent.cgi?Article=1245&Context=Compsci, Carnegie Mellon University, November 1995, repository.cmu.edu\/cgi\/viewcontent.cgi?article=1245&context=compsci.Lynn, Ben. \"ZDDs.\" ZDDs - Einf\u00fchrung, Stanford University, 2005, crypto.stanford.edu\/pbc\/notes\/zdd\/.Mischchenko, Alan. \"Eine Einf\u00fchrung in Null-unterdr\u00fcckte bin\u00e4re Entscheidungsdiagramme.\" 5. Februar 2014, doi:https:\/\/people.eecs.berkeley.edu\/~alanmi\/publications\/2001\/tech01_zdd_.pdf.Knuth, Donald E. Die Kunst der Computerprogrammierung, Band 4. 22. Dezember 2008.Externe Links[edit]Minato, Shin-ichi. \"Null-unterdr\u00fcckte BDDs und ihre Anwendungen.\" https:\/\/Www.researchgate.net\/Profile\/Shin-ichi_Minato\/Publication\/37555760_Zero-suppressed_BDDs_and_their_applications\/Links\/02e7e52b85cd639cb5000000.Pdf, Hokkaido University, Mai 2001, www.researchgate.net\/profile\/Shin-ichi_Minato\/publication\/37555760_Zero-suppressed_BDDs_and_their_applications\/links\/02e7e52b85cd639cb5000000.pdf.Minato, Shin-ichi. \"Null unterdr\u00fcckte BDDs f\u00fcr die Manipulation von S\u00e4tzen bei kombinatorischen Problemen.\" 1993, doi:https:\/\/pdfs.semanticscholar.org\/9593\/6223362a16a50de2959475d87aefe2a1fec7.pdf.Bryant, Randal E. \"Bin\u00e4re Entscheidungsdiagramme und dar\u00fcber hinaus: Erm\u00f6glichung von Technologien f\u00fcr die formale \u00dcberpr\u00fcfung.\" http:\/\/Repository.cmu.edu\/Cgi\/Viewcontent.cgi?Article=1245&Context=Compsci, Carnegie Mellon University, November 1995, repository.cmu.edu\/cgi\/viewcontent.cgi?article=1245&context=compsci.Lynn, Ben. \"ZDDs.\" ZDDs - Einf\u00fchrung, Stanford University, 2005, crypto.stanford.edu\/pbc\/notes\/zdd\/.Alan Mishchenko, Alan. \"Eine Einf\u00fchrung in nullunterdr\u00fcckte bin\u00e4re Entscheidungsdiagramme.\" 5. Februar 2014, doi:https:\/\/people.eecs.berkeley.edu\/~alanmi\/publications\/2001\/tech01_zdd_.pdf.Alan Mishchenko, Eine Einf\u00fchrung in nullunterdr\u00fcckte bin\u00e4re EntscheidungsdiagrammeDonald Knuth, Spa\u00df mit nullunterdr\u00fcckten bin\u00e4ren Entscheidungsdiagrammen (ZDDs) (Videovorlesung, 2008)Minato Shin-ichi, Pfade in Graphen z\u00e4hlen (Grundlagen des ZDD) (Videoillustration auf Miraikan) (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki8\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki8\/2020\/12\/15\/null-unterdrucktes-entscheidungsdiagramm-wikipedia\/#breadcrumbitem","name":"Null-unterdr\u00fccktes Entscheidungsdiagramm – Wikipedia"}}]}]