Neue Frage
0

BDDs: Restrict Algorithmus

gefragt 2014-08-25 17:20:18 +0200

Kej Gravatar-Bild

aktualisiert 2014-11-07 17:11:21 +0200

FachschaftsIT Gravatar-Bild

Hallo,

Ich verstehe den Restrict-Algorithmus für BDDs nicht. Der Apply Algorithmus ist kein Problem, aber der Restrict Algorithmus wurde irgendwie nur sehr knapp behandelt. Hätte jemand eine Erklärung und ein paar Beispiele?

LG und danke

bearbeiten retag Als beleidigend melden schließen löschen

Kommentare

Was genau verstehst du denn nicht? Also wenn du den Algorithmus im Script z.B. durchgehst, oder ein Beispiel rechnest, wo kommst du nicht weiter?

contradictioned ( 2014-11-06 16:16:40 +0200 )bearbeiten

Der Admin bittet: Wenn eine Antwort richtig ist, markier sie doch als solche. Danke.

contradictioned ( 2015-07-30 20:53:09 +0200 )bearbeiten

2 Antworten

0

geantwortet 2015-06-24 19:34:13 +0200

PS Gravatar-Bild

Die gegebene Antwort ist leider nicht richtig. Der Name "Restrict" ist leider von den Entwicklern dieses Algorithmus etwas missverständlich gewählt worden, so dass man auf die vorige Antwort kommen könnte. Aber das ist leider dennoch falsch.

Betrachten wir eine boolesche Funktion f(x1,...,xn) mit n Variablen. Was in der vorigen Antwort geschildert wurde, war dass man Kofaktoren zu f bilden könnte, indem man eine Variable durch eine Konstante true/false ersetzt. Das kann man z.B. durch die BDD-Funktion Compose erledigen, die die meisten BDD-Pakete anbieten. Dabei wird eine der Variablen durch eine andere boolesche Funktion, in diesem Fall einfach durch true oder false ersetzt. Wenn egal ist, ob man true oder false einsetzt, kann man auch über die nicht mehr interessante Variable quantifizieren.

Restrict macht aber was ganz anderes: Hierzu muss zu der booleschen Funktion f(x1,...,xn) noch ein "Care-Set" angegeben werden, d.h. die Belegungen der Variablen x1,...,xn, die einen wirklich interessieren. Wenn alle Belegungen von Interesse sind, dann kann Restrict nur beim BDD der Funktion f bleiben. Andernfalls versucht Restrict, die Belegungen im "don't care" Bereich so abzuändern, dass das neue BDD kleiner wird.

Man ändert mit Restrict also die boolesche Funktion f so im "don't care" Bereich ab, dass das BDD unter der gewählten Variablenordnung kleiner wird. Hierzu gibt es verschiedene Heuristiken (denn das Optimum zu finden ist NP-schwierig) und Restrict ist eine davon (der Constraint-Algorithmus eine andere).

bearbeiten Als beleidigend melden löschen publish Link mehr
0

geantwortet 2015-03-31 00:08:31 +0200

BDDs repräsentieren ja immer aussagelogische Formeln (auch Bool-Funktionen genannt). Diese liefern abhängig von einigen binären Variablen immer einen binären Wert. BDDs verwenden zur Darstellung der Funktionen eine Baumstruktur. Am jedem inneren Knoten des Baumes steht ein Variablenname dran. An den Blattknoten stehen Ausgabewerte.

Willst du nun die Formel (bzw. Bool-Funktion) auswerten, läufst du den Baum von der Wurzel zu einem Blatt. An jedem Knoten entscheidest du dich, welcher Wert der zugehörigen Variable zugewiesen ist. Abhängig davon wählst du einen der beiden Kindknoten und setzt dort deine Reise fort. Du endest an einem Blatt des Baumes. Der dort stehende Wert gibt dir an, mit welchem Wert die Formel für die gegebene Variablenbewertung bewertet wird.

Die Restrict-Funktion auf BDDs beantworten die folgende Frage: „Angenommen, ich kenne schon den Wert einer meiner binären Variablen, wie sieht dann die (verkleinerte) Funktion/Formel aus, die mir abhängig von den verbleibenden Variablen einen Wert für die Auswertung der ursprünglichen Formel bestimmt?“

Zu abstrakt? Machen wir ein einfaches Beispiel: Stell dir die Formel „p oder q“ vor (Logik-Notation: p ∨ q, E-Technik-Notation: p + q) und nimm an, p sei auf falsch festgesetzt. Wann kann die Formel jetzt noch wahr werden? Wenn q hingegen wahr wird. Die (atomare) Formel „q“ beschreibt also, wie sich die Formel „p oder q“ verhält, wenn p als falsch angenommen wird.

Wie könntest du nun aus einem BDD für eine Formel einen BDD für die verkürzte Formel bekommen, bei der schon eine Variable bewertet wurde? Wir erinnern, dass jeder innere Knoten für eine Variable steht und das Entscheiden für einen der beiden Kindknoten beim Abstieg in dem Baum für das Bewerten der Variablen steht. Ist ein Wert einer Variable gegeben, ist also für jeden Knoten, der diese Variable repräsentiert, festgelegt, zu welchen Kind abgestiegen werden muss.

Das heißt für den BDD, dass die Kindknoten, die den festgesetzten Variablenwert repräsentieren, die Positionen der Knoten einnehmen, die die entsprechende Variable repräsentieren.

Vorsicht bei reduzierten BDDs! Ein reduzierter BDD hat zum Einen keine Knoten, dessen Kinder beide gleich sind, und zum Anderen auch keine zwei Teilgraphen, die bis zu den Blättern hin gleich sind. Dies kann bei der oben genannten Methode verletzt werden! Warum? Durch restrict bleibt bei jedem Vorkommen der eingeschränkten Variable nur einer der beiden darunter stehenden Teilbäume übrig. Der wegfallende Teil kann vorher den Unterschied ausgemacht haben. Übrig bleiben unter Umständen gleiche Kinder oder gleiche Teilgraphen.

Folglich muss ein reduzierter BDD nach der oben stehenden restrict-Methode wieder reduziert werden.

bearbeiten Als beleidigend melden löschen publish Link mehr

Ihre Antwort

Du kannst deinen Eintrag bereits als Gast verfassen. Deine Antwort wird zwischengespeichert, bis du dich eingeloggt oder registriert hast.
Bitte nur konstruktive Antworten auf diese konkrete Frage posten.
Falls du eine Frage stellen willst, dann stelle eine neue Frage.
Für kurze Diskussionen und Nachfragen benutze bitte die Kommentar-Funktion.
Deine Fragen und Antworten kannst du jederzeit nachbearbeiten und verbessern.
Gute Fragen und Antworten kannst du mit einem Upvote oder Downvote bewerten.

Schreibe deine Antwort auf diese Frage

[Vorschau ausblenden]

Fragen-Tools

Beobachten
1 Follower

Statistik

Gefragt: 2014-08-25 17:20:18 +0200

Gesehen: 4,667 mal

Letztes Update: Jun 24 '15