In der Informatik ist der Davis-Putnam-Logemann-Loveland ( DPLL ) -Algorithmus ein vollständiger, auf Rückverfolgung basierender Suchalgorithmus, um die Erfüllbarkeit zu bestimmen von aussagenlogischen Formeln in konjunktiver Normalform, dh zur Lösung des CNF-SAT-Problems.
Es wurde 1962 von Martin Davis, George Logemann und Donald W. Loveland eingeführt und ist eine Weiterentwicklung des früheren Davis-Putnam-Algorithmus, ein auf Auflösung basierendes Verfahren, das 1960 von Davis und Hilary Putnam entwickelt wurde. Besonders bei älteren Der Davis-Logemann-Loveland-Algorithmus wird häufig als "Davis-Putnam-Methode" oder "DP-Algorithmus" bezeichnet. Andere gebräuchliche Namen, die die Unterscheidung beibehalten, sind DLL und DPLL.
Nach über 50 Jahren ist das DPLL-Verfahren immer noch die Basis für die effizientesten SAT-Komplettlöser. Es wurde vor kurzem für automatisierte Theorembeweisung für Fragmente der Logik erster Ordnung erweitert. [1]
Implementierungen und Anwendungen [ edit ]
Das SAT-Problem ist sowohl aus theoretischen als auch aus praktischen Gründen wichtig Aussicht. In der Komplexitätstheorie erwies sich das erste Problem als NP-vollständig und kann in einer Vielzahl von Anwendungen auftreten, wie beispielsweise Model Checking automatisierte Planung und Planung und Diagnose in künstlicher Intelligenz.
Daher ist es seit vielen Jahren ein heißes Thema in der Forschung, und es finden regelmäßig Wettbewerbe zwischen SAT-Solvern statt. [2] Moderne Implementierungen von DPLL wie Chaff und zChaff, [3][4] GRASP oder Minisat [5] sind in der Forschung Die ersten Plätze der Wettkämpfe dieser letzten Jahre. [ when? ]
Eine andere Anwendung, die häufig DPLL beinhaltet, ist die Prüfung automatischer Theoreme oder Erfüllbarkeitsmodulo-Theorien (SMT), die ein SAT ist Problem, bei dem Aussagenvariablen durch Formeln einer anderen mathematischen Theorie ersetzt werden.
Der Algorithmus [ edit ]
Der grundlegende Backtracking-Algorithmus wird ausgeführt, indem er ein Literal auswählt, ihm einen Wahrheitswert zuweist, die Formel vereinfacht und rekursiv überprüft, ob die vereinfachte Formel zufriedenstellend ist ; Wenn dies der Fall ist, ist die ursprüngliche Formel zufriedenstellend. Andernfalls wird dieselbe rekursive Prüfung durchgeführt, wenn der entgegengesetzte Wahrheitswert angenommen wird. Dies ist als Splitting-Regel bekannt, da sie das Problem in zwei einfachere Teilprobleme aufteilt. Der Vereinfachungsschritt entfernt im Wesentlichen alle Klauseln, die unter der Zuweisung wahr werden, und alle Literale, die falsch werden, aus den verbleibenden Klauseln.
Der DPLL-Algorithmus verbessert den Backtracking-Algorithmus durch die eifrige Anwendung der folgenden Regeln in jedem Schritt:
- Einheitenausbreitung
- Wenn eine Klausel eine - Einheitsklausel ist d. H. Sie enthält nur ein einzelnes nicht zugewiesenes Literal, kann diese Klausel nur erfüllt werden, indem der erforderliche Wert zugewiesen wird, um dieses Literal wahr zu machen. Somit ist keine Wahl notwendig. In der Praxis führt dies häufig zu deterministischen Kaskaden von Einheiten, wodurch ein großer Teil des naiven Suchraums vermieden wird.
- Reine wörtliche Eliminierung
- Wenn eine Aussagevariable mit nur einer Polarität in der Formel vorkommt, wird sie als bezeichnet ] pure . Reine Literale können immer so zugewiesen werden, dass alle Klauseln, die sie enthalten, wahr sind. Daher beschränken diese Klauseln die Suche nicht mehr und können gelöscht werden.
Eine unbefriedigende Teilzuweisung wird erkannt, wenn eine Klausel leer wird, d. H. Wenn alle ihre Variablen auf eine Weise zugewiesen wurden, dass die entsprechenden Literale falsch sind. Die Erfüllbarkeit der Formel wird entweder erkannt, wenn alle Variablen zugewiesen werden, ohne die leere Klausel zu generieren, oder bei modernen Implementierungen, wenn alle Klauseln erfüllt sind. Die Unzufriedenheit der vollständigen Formel kann nur nach einer erschöpfenden Suche erkannt werden.
Der DPLL-Algorithmus kann im folgenden Pseudocode zusammengefasst werden, wobei Φ die CNF-Formel ist:
Algorithmus DPLL Eingabe: Eine Reihe von Klauseln Φ. Ausgabe: Ein Wahrheitswert.
Funktion DPLL (Φ) if Φ ist eine konsistente Menge von Literalen dann Rückkehr wahr; if Φ enthält eine leere Klausel dann Rückkehr falsch; für jede -Einheitsklausel {l} in Φ Φ ← Einheit propagieren ( l Φ); für jeden wörtlichen der rein in auftritt Φ ← rein-wörtliche Zuweisung ( l Φ); l ← Wahl-Literal (Φ); Rückkehr DPLL (1945-19003) {l}) oder DPLL (19459003) (19459004) {nicht (l)} ); - "←" bezeichnet die Zuordnung. Beispielsweise bedeutet " größte ← Position ", dass sich der Wert von größte in den Wert von Position ändert.
- " return "beendet den Algorithmus und gibt den folgenden Wert aus.
In diesem Pseudocode geben unit propagate (l, [) und rein-wörtliche Zuweisung (l,) an ) sind Funktionen, die das Ergebnis der Anwendung von Einheitsausbreitung bzw. die reine wörtliche Regel an das wörtliche l und die Formel Φ zurückgeben. Mit anderen Worten, sie ersetzen jedes Vorkommen von l durch "true" und jedes Vorkommen von nicht l durch "false" in der Formel und vereinfachen das resultierende Formel. Die Anweisung oder in der Anweisung ist ein Kurzschlussoperator. [1945 ∧ {l} bezeichnet das vereinfachte Ergebnis der Substitution von "true" für l in .
Die Pseudocode-DPLL-Funktion gibt nur zurück, ob die endgültige Zuweisung die Formel erfüllt oder nicht. In einer realen Implementierung wird die teilweise befriedigende Zuweisung typischerweise auch bei Erfolg zurückgegeben. Dies kann aus der konsistenten Literliste der ersten if -Anweisung der Funktion abgeleitet werden.
Der Davis-Logemann-Loveland-Algorithmus hängt von der Wahl des Verzweigungsliterales ab, bei dem es sich um das im Backtracking-Schritt behandelte Literal handelt. Folglich ist dies nicht genau ein Algorithmus, sondern eine Familie von Algorithmen, und zwar für jede mögliche Art der Auswahl des Verzweigungsliteral. Die Effizienz wird stark durch die Wahl des Verzweigungsliteral beeinflusst: Es gibt Fälle, für die die Laufzeit konstant oder exponentiell ist, abhängig von der Wahl der Verzweigungslitale. Solche Wahlfunktionen werden auch als heuristische Funktionen oder verzweigte Heuristiken bezeichnet. [6]
Visualization [ edit
Davis, Logemann, Loveland (1962) hatte diesen Algorithmus entwickelt. Einige Eigenschaften dieses ursprünglichen Algorithmus sind:
- Es basiert auf Suche.
- Es ist die Basis für fast alle modernen SAT-Löser.
- Es verwendet KEINEN Lern- und nicht-chronologischen Backtracking (eingeführt 1996).
Ein Beispiel mit Visualisierung eines DPLL-Algorithmus mit chronologischer Rückverfolgung:
Alle Klauseln, die eine CNF-Formel bilden
Treffen Sie eine Entscheidung, Variable a = False (0), und grüne Klauseln werden wahr
Nach mehreren Entscheidungen finden wir eine Implikationskurve, die zu einem Konflikt führt.
Kehren Sie jetzt auf die unmittelbare Ebene zurück und weisen Sie dieser Variablen einen anderen Wert zu
Eine Zwangsentscheidung führt jedoch noch zu einem weiteren Konflikt
Gehen Sie zurück zum vorherigen Level und treffen Sie eine Zwangsentscheidung
Treffen Sie eine neue Entscheidung, die jedoch zu einem Konflikt führt
Treffen Sie eine Zwangsentscheidung, die wiederum zu Konflikten führt
Zurück zum vorherigen Level
Fahren Sie auf diese Weise und die endgültige Implikationskurve fort
Aktuelle Arbeit [ edit ]
In den 2010er Jahren wurde an der Verbesserung des Algorithmus in drei Richtungen gearbeitet:
- Definieren verschiedener Richtlinien für die Auswahl der Verzweigungsliterale.
- Definieren neuer Datenstrukturen, um den Algorithmus zu beschleunigen, insbesondere den Teil auf -Einheitsausbreitung
- Definieren von Varianten des grundlegenden Backtracking-Algorithmus. Die letztere Richtung umfasst nicht-chronologisches Backtracking (alias Backjumping ) und Klausellernen . Diese Verfeinerungen beschreiben eine Methode des Backtracking nach Erreichen einer Konfliktklausel, die die Hauptursachen (Zuweisungen zu Variablen) des Konflikts "lernt", um zu vermeiden, dass derselbe Konflikt erneut erreicht wird. Die daraus resultierenden konfliktgetriebenen Klausel, die SAT-Löser lernen, sind Stand der Technik im Jahr 2014. [ Zitat benötigt ]
Ein neuerer Algorithmus aus dem Jahr 1990 ist Stålmarcks Methode. Auch binäre Entscheidungsdiagramme (1986) (reduziert geordnet) für die SAT-Lösung verwendet worden.
Beziehung zu anderen Begriffen [ edit ]
Läufe von DPLL-basierten Algorithmen auf nicht befriedigenden Fällen entsprechen Beweisen für die Auflösung der Baumauflösung. Siehe auch . ] General Specific Referenzen [ ]
Weiterführende Literatur [ ]
No comments:
Post a Comment