Erfüllbarkeitsproblem der Aussagenlogik
Das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von {{#invoke:Vorlage:lang|full|CODE=en|SCRIPTING=Latn|SERVICE=englisch}} „Erfüllbarkeit“) ist ein Entscheidungsproblem der theoretischen Informatik. Es beschäftigt sich mit der Frage, ob eine gegebene aussagenlogische Formel <math>F</math> erfüllbar ist. Mit anderen Worten: Existiert eine Belegung der Variablen von <math>F</math> mit den Werten wahr oder falsch, sodass <math>F</math> zu wahr ausgewertet wird?
SAT gehört zur Komplexitätsklasse NP der Probleme, die von einer nichtdeterministischen Turingmaschine in polynomieller Zeit gelöst werden können. Außerdem war SAT das erste Problem, für das NP-Vollständigkeit nachgewiesen wurde (Satz von Cook). Damit kann jedes Problem aus NP in polynomieller Zeit auf SAT zurückgeführt werden (Polynomialzeitreduktion). NP-vollständige Probleme stellen also eine Art obere Schranke für die Schwierigkeit von Problemen in NP dar.
Eine deterministische Turingmaschine (etwa ein konventioneller Computer) kann SAT in exponentieller Zeit entscheiden, zum Beispiel durch das Aufstellen einer Wahrheitstabelle. Es ist kein effizienter Algorithmus für SAT bekannt und es wird allgemein vermutet, dass ein solcher Polynomialzeitalgorithmus nicht existiert. Die Frage, ob SAT in polynomieller Zeit gelöst werden kann, ist äquivalent zum P-NP-Problem, einem der bekanntesten offenen Probleme der theoretischen Informatik.
Ein Großteil der Forschung beschäftigt sich mit der Entwicklung möglichst effizienter Verfahren zur Lösung von SAT in der Praxis (sogenannter SAT-Solver). Moderne SAT-Solver können Instanzen mittlerer Schwierigkeit mit hunderten Millionen Variablen oder Klauseln in praktikabler Zeit lösen.<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:|{{{autor}}}: }}{{#if:|{{#if:SAT Competition 2020|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=SAT Competition 2020}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://satcompetition.github.io/2020/downloads.html%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=SAT Competition 2020}}}}|[{{#invoke:URLutil|getNormalized|1=https://satcompetition.github.io/2020/downloads.html}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=SAT Competition 2020}}}}]}}{{#if:| ({{{format}}}{{#if:{{#if: 2020-11-09 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
| )
| {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ;
| )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://satcompetition.github.io/2020/downloads.html%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://satcompetition.github.io/2020/downloads.html}}%7C%7C}}}}{{#if:SAT Competition 2020|{{#if:{{#invoke:WLink|isValidLinktext|1=SAT Competition 2020|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: | {{{hrsg}}}{{#if: |,|{{#if: 2020-11-09 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
|{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
|{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: |,|{{#if: 2020-11-09 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2020-11-09 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:65083||(?)}}}}}}{{#if: 2020-11-09|;}}}}{{#if: 2020-11-09| {{#if:{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2020-11-09 |ISO|noerror=1}} }}
|4=im Jahr
|7=im
|10=am
|#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2020-11-09|class=Zitationswartung}} }} {{#invoke:DateTime|format|2020-11-09|T._Monat JJJJ}}
| {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:{{#if: 2020-11-09 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
| (
| {{#if: | | (}}
}}{{#ifeq:{{#if:de|de|de}}|de||
{{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2020-11-09 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}|{{#if: |: {{
#if:
| „{{
#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
| Vorlage:Str trim
| {{#invoke:Vorlage:lang|flat}}
}}“
| {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
| „Vorlage:Str trim“
| {{#invoke:Text|quote
|1={{#if:
| {{#invoke:Vorlage:lang|flat}}
| {{#invoke:Vorlage:lang|flat}} }}
|2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
|3=1}} }}
}}{{#if:
| (<templatestyles src="Person/styles.css" />{{#if: | : }}{{#if: | , deutsch: „“ }})
| {{#if:
| ({{#if: | , deutsch: „“ }})
| {{#if: | (deutsch: „“) }}
}}
}}{{#if: {{{zitat}}}
| {{#if:
| {{#if: {{{zitat}}}
| Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
| Vorlage:": Text= fehlt }}{{#if: | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
| Vorlage:": Ungültiger Wert: ref=
| {{{ref}}} }}
}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch:
|0|=Vorlage:Toter Link/Core{{#if: https://satcompetition.github.io/2020/downloads.html | {{#if: | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }} }} | (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.) }}{{#switch: |no|0|= |#default={{#if: || }} }}{{#invoke:TemplatePar|check |opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://satcompetition.github.io/2020/downloads.html | {{#if:{{#invoke:URLutil|isWebURL|https://satcompetition.github.io/2020/downloads.html}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://satcompetition.github.io/2020/downloads.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#if: | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch: |no|0|= |#default= {{#if: || }} }}{{#invoke:TemplatePar|check |all = inline= url= |opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://satcompetition.github.io/2020/downloads.html | {{#if:{{#invoke:URLutil|isWebURL|https://satcompetition.github.io/2020/downloads.html}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}[https://satcompetition.github.io/2020/downloads.html }}|{{#switch: |0|=Vorlage:Toter Link/Core{{#if: https://satcompetition.github.io/2020/downloads.html | {{#if: | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: | {{#if: | | Vorlage:Toter Link/archivebot }} }} | (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.) }}{{#switch: |no|0|= |#default={{#if: || }} }}{{#invoke:TemplatePar|check |opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://satcompetition.github.io/2020/downloads.html | {{#if:{{#invoke:URLutil|isWebURL|https://satcompetition.github.io/2020/downloads.html}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://satcompetition.github.io/2020/downloads.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#if: | {{#if: | | Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch: |no|0|= |#default= {{#if: || }} }}{{#invoke:TemplatePar|check |all = inline= url= |opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://satcompetition.github.io/2020/downloads.html | {{#if:{{#invoke:URLutil|isWebURL|https://satcompetition.github.io/2020/downloads.html}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}[https://satcompetition.github.io/2020/downloads.html }} }}}}}}}}}}{{#if:| {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}
}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref> Das ist ausreichend für praktische Anwendungen, z. B. in der formalen Verifikation,<ref name="Verification">{{#invoke:Vorlage:Literatur|f}}</ref> in der künstlichen Intelligenz,<ref name="10.5555/145448.146725">{{#invoke:Vorlage:Literatur|f}}</ref> in der Electronic Design Automation<ref name="10.1145/337292.337611">{{#invoke:Vorlage:Literatur|f}}</ref> und in verschiedenen Planungs- und Schedulingalgorithmen.<ref name="10.2991/icmse-18.2018.126">{{#invoke:Vorlage:Literatur|f}}</ref>
Sie gehören zu den Constraint Satisfaction Problems (CSP).
Terminologie
Eine aussagenlogische Formel besteht aus Variablen, Klammern und den aussagenlogischen Verknüpfungen Konjunktion („und“, oft notiert mit ∧), Disjunktion („oder“, ∨) und Negation („nicht“, ¬). Eine Variable kann entweder den Wert wahr oder den Wert falsch annehmen. Ein Literal ist ein Auftreten einer Variable (positives Literal) oder ihrer Negation (negatives Literal). Ein Literal heißt pur, wenn es nur in einer Ausprägung, also entweder positiv oder negativ, vorkommt. Ein Monom ist eine endliche Menge von Literalen, die ausschließlich konjunktiv verknüpft sind. Eine Klausel ist eine endliche Menge von Literalen, die ausschließlich disjunktiv verknüpft sind. Eine Einheitsklausel ist eine Klausel, die nur aus einem einzelnen Literal besteht. Eine Horn-Klausel ist eine Klausel mit höchstens einem positiven Literal.
Eine aussagenlogische Formel ist in konjunktiver Normalform (KNF), wenn sie nur aus Konjunktionen von Klauseln besteht. Eine Horn-Formel ist eine konjunktive Normalform, die ausschließlich aus Horn-Klauseln besteht. Die Formel <math>(x_1 \lor \lnot x_2) \land (\lnot x_1 \lor x_2 \lor x_3) \land \lnot x_1</math> befindet sich in konjunktiver Normalform. Da nur die erste und die dritte Klausel Horn-Klauseln sind, ist sie aber keine Horn-Formel. Die dritte Klausel ist eine Einheitsklausel.
Eine aussagenlogische Formel ist in disjunktiver Normalform (DNF), wenn sie nur aus Disjunktionen von Monomen besteht. Die Formel <math>(x_1 \land \lnot x_2) \lor (\lnot x_1 \land x_2 \land x_3) \lor \lnot x_1</math> befindet sich in disjunktiver Normalform.
Definition und Varianten
Eine Formel <math>F</math> heißt genau dann erfüllbar, wenn eine Zuweisung von Werten wahr oder falsch zu jeder Variable existiert, sodass die Formel wahr ist. Formal ist SAT definiert als die formale Sprache
<math>SAT = \{F\ |\ F</math> ist aussagenlogische Formel und erfüllbar <math>\}</math>
In der Praxis versteht man unter SAT meistens das Problem, herauszufinden ob eine Formel <math>F</math> erfüllbar ist. Es existieren zahlreiche Varianten und für die meisten Komplexitätsklassen existiert eine Variante von SAT, die bezüglich dieser Klasse vollständig ist.
Polynomiell entscheidbare Varianten von SAT
- HORNSAT beschränkt SAT auf Horn-Formeln, das heißt auf Formeln in konjunktiver Normalform bei der jede Klausel höchstens ein positives Literal enthält. HORNSAT ist P-vollständig und in Linearzeit entscheidbar.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>
- DNF-SAT beschränkt SAT auf Formeln, die in disjunktiver Normalform gegeben sind. DNF-SAT ist in polynomieller Zeit entscheidbar, da eine in DNF gegebene Formel genau dann erfüllbar ist, wenn es ein Monom gibt das keine komplementären Literale enthält.
- 2-SAT beschränkt SAT auf Formeln, deren Klauseln maximal 2 Literale enthalten. 2-SAT ist in Linearzeit entscheidbar.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>
3-SAT
Das Problem 3-SAT schränkt die Anzahl Literale auf 3 Literale pro Klausel ein. Trotz dieser Einschränkung ist 3-SAT NP-vollständig, da SAT sich in polynomieller Zeit auf 3-SAT reduzieren lässt. Dasselbe gilt für alle Probleme k-SAT mit k > 3.
P3-SAT
Eine Instanz des Problems 3-SAT, bestehend aus p Variablen und q Klauseln, lässt sich auch mittels eines Graphen mit (p + q) vielen Knoten darstellen. Eine Formel ist in P3-SAT, wenn sie in 3-SAT ist und dieser Graph planar ist. P3-SAT ist NP-vollständig.
MAX-SAT
Das Problem MAX-SAT besteht darin, die maximale Anzahl erfüllbarer Klauseln einer gegebenen Formel zu bestimmen. MAX-SAT ist NP-vollständig und sogar APX-vollständig. Daraus folgt, dass kein PTAS für MAX-SAT existieren kann, falls P ≠ NP.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>
MAJ-SAT
MAJ-SAT ist das Problem zu entscheiden, ob die Mehrzahl aller möglichen Variablenbelegungen die Formel erfüllt. MAJ-SAT ist PP-vollständig.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>
QBF (QSAT)
QBF verallgemeinert SAT für quantifizierte, aussagenlogische Formeln, also Formeln, die Quantoren enthalten. QBF ist PSPACE-vollständig.
Algorithmen
Da SAT NP-vollständig ist, sind ausschließlich Exponentialzeitalgorithmen für SAT bekannt. Seit den 2000er Jahren werden aber effiziente und skalierbare Algorithmen (SAT-Solver) entwickelt, die praktikables SAT-Solving für zahlreiche Anwendungen erlauben. Beispiele für Anwendungen sind formale Verifikation,<ref name="Verification" /> Künstliche Intelligenz,<ref name="10.5555/145448.146725" /> Electronic Design Automation<ref name="10.1145/337292.337611" /> und verschiedene Planungs- und Schedulingalgorithmen.<ref name="10.2991/icmse-18.2018.126" />
SAT-Solver können aufgrund ihrer Funktionsweise in verschiedene Klassen eingeteilt werden.
Ein grundlegender randomisierter Algorithmus zur Lösung des k-SAT-Problems stammt von Uwe Schöning (1999), die Randomisierung konnte später von Robin A. Moser vollständig entfernt werden (um 2009). Der schnellste bekannte (randomisierte) Algorithmus für allgemeines k-SAT ist PPSZ (Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane),<ref>Paturi, Pudlàk, Saks, Zane, An improved exponential-time algorithm for K-SAT, J. ACM, Band 52, 2005, S. 337–364</ref><ref>Dominik Schweder, John P. Steinberger, PPSZ for General k-SAT – Making Hertli’s Analysis Simpler and 3-SAT Faster, 2017, Online</ref> entstanden aus dem Vorläufer PPZ von 1999, der nicht so gut wie der Algorithmus von Schöning war, und basierend auf Encoding. 2014 gab Timon Hertli Verbesserungen für den Fall unique 3-SAT.<ref>Hertli: Breaking the PPSZ Barrier for Unique 3-SAT. In: Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias (Hrsg.): Automata, Languages, and Programming – 41st International Colloquium, ICALP 2014, Kopenhagen, Juli 2014. Teil 1: Proceedings, Part I: Lecture Notes in Computer Science 8572. Springer 2014, S. 600–611</ref>
Backtracking und DPLL
Der Davis-Putnam-Logemann-Loveland-Algorithmus (DPLL oder DLL) aus den 1960er Jahren war der erste SAT-Solver, der eine systematische Suche mittels Backtracking implementierte.<ref>{{#invoke:Vorlage:Literatur|f}}</ref><ref>{{#invoke:Vorlage:Literatur|f}}</ref> Er ist nicht zu verwechseln mit dem Davis-Putnam-Algorithmus, auf dem er basiert. Viele moderne Ansätze basieren auf dem gleichen Konzept und optimieren oft lediglich die Effizienz des Algorithmus für bestimmte Klassen von Eingaben, wie z. B. zufällige SAT-Instanzen oder Instanzen, die in Anwendungen der Industrie auftreten.<ref>{{#invoke:Vorlage:Literatur|f}}</ref> DPLL löst das CNF-SAT-Problem. Das bedeutet, die aussagenlogischen Formeln müssen in der konjunktiven Normalform vorliegen (Menge von Klauseln).
Ein grundlegender Backtracking-Algorithmus für eine Formel <math>F</math> funktioniert wie folgt:
- Wähle ein Literal <math>l</math> aus <math>F</math>.
- Weise <math>l</math> einen Wahrheitswert wahr oder falsch zu.
- Vereinfache <math>F</math> zu <math>F_l</math>, indem alle Klauseln entfernt werden, die nun wahr sind und alle Literale entfernt werden, die nun falsch sind.
- Splitting Rule. Prüfe rekursiv, ob <math>F_l</math> erfüllbar ist.
- <math>F_l</math> ist erfüllbar <math>\implies</math> <math>F</math> ist erfüllbar.
- <math>F_l</math> ist nicht erfüllbar: Weise <math>l</math> den komplementären Wahrheitswert zu. Vereinfache und prüfe dann erneut rekursiv, ob die resultierende Formel <math>F_{\lnot l}</math> erfüllbar ist. Ist <math>F_{\lnot l}</math> erfüllbar, so ist auch <math>F</math> erfüllbar. Ist <math>F_{\lnot l}</math> nicht erfüllbar, so ist auch <math>F</math> nicht erfüllbar.
Der Algorithmus terminiert, wenn eine Klausel leer wird (nicht erfüllbar, ihr letztes Literal wurde falsch) oder wenn alle Variablen belegt sind (erfüllbar).
DPLL verbessert den simplen Backtracking-Algorithmus durch zwei Regeln.
Einheitsresolution (Unit Propagation)
Tritt eine Einheitsklausel <math>\psi</math> auf, so muss ihr einziges Literal wahr sein. Weise dem Literal den entsprechenden Wahrheitswert zu und entferne alle Klauseln, die <math>\psi</math> enthalten. Entferne Vorkommen des Literals <math>\lnot \psi</math> aus allen Klauseln.
In der Praxis führt Einheitsresolution oft dazu, dass wiederum Einheitsklauseln erzeugt werden und somit der naive Suchraum signifikant verkleinert wird.
Pure Literal Elimination
Kommt ein Literal als pures Literal vor, so kann ihm ein Wert zugewiesen werden, sodass alle Klauseln, die das Literal enthalten, wahr werden. Entferne diese Klauseln.
Der Algorithmus zusammengefasst im Pseudocode:
function DPLL(F : set of clauses)
# Konsistent bedeutet, es kommt ausschließlich ¬l oder l vor
if F is a consistent set of literals then
# Hier können zusätzlich die Literale zurückgegeben werden
return true;
if F contains an empty clause then
return false;
for every unit clause {l} in F do
F ← unit-propagate(l, F);
for every literal l that occurs pure in F do
F ← pure-literal-assign(l, F);
l ← choose-literal(F);
# Mit Kurzschlussauswertung für das Oder
return DPLL({F : l = true}) or DPLL({F : l = true}); #
Dabei wenden unit-propagate(l, F) und pure-literal-assign(l, F) die beiden Regeln entsprechend an und geben die vereinfachte Formel zurück.
Die Effizienz von DPLL hängt sehr stark von der Auswahl des Literals <math>l</math> (Branching Literal) ab. Für manche Instanzen kann diese Wahl den Unterschied zwischen konstanter und exponentieller Laufzeit ausmachen.<ref>{{#invoke:Vorlage:Literatur|f}}</ref> Darum definiert DPLL vielmehr eine ganze Familie von Algorithmen, die unterschiedliche Heuristiken für die Wahl von <math>l</math> verwenden.
Die Probleme von DPLL können in drei Punkten zusammengefasst werden:
- Die Entscheidungen für Branching Literals werden naiv getroffen.
- Aus Konflikten wird nichts gelernt, außer dass die aktuelle (partielle) Variablenbelegung zu einem Konflikt führt. Dabei lassen sich mehr Informationen über die Ursache des Konfliktes extrahieren und so große Teile des Suchraumes ausschließen.
- Backtracking springt nur jeweils eine Ebene im Suchbaum nach oben, was zu einem sehr großen Suchraum führt.
In der Praxis werden diese Probleme gelöst durch
- Heuristiken, z. B. in einem Look-Ahead-Solver
- Clause Learning (CDCL)
- Backjumping (CDCL)
Conflict-Driven Clause Learning (CDCL)
Modernes Conflict-driven Clause Learning (CDCL) erweitert DPLL um die Konzepte Clause Learning und Backjumping, implementiert Two Watched Literals (TWL, 2WL), um die Suche nach Einheitsklauseln zu beschleunigen und verwendet Random Restarts, um schwierigen Situationen nach einer Reihe von schlechten Entscheidungen für Variablenbelegungen zu entfliehen.
Backjumping und Clause Learning
Bei CDCL findet das Backtracking nicht mehr chronologisch statt, sondern es werden Ebenen des Suchbaumes übersprungen. Außerdem werden Informationen über Variablenbelegungen, die in Kombination einen Konflikt verursachen, als Klausel der Klauselmenge hinzugefügt.
-
Backtracking ohne Backjumping
-
Backtracking mit Backjumping
Um Backjumping zu ermöglichen, merkt sich CDCL, welche Zuweisungen von Wahrheitswerten zu Variablen willkürlich waren und welche Zuweisungen durch Unit Propagation erzwungen wurden. In der Praxis funktioniert das mittels eines Implikationsgraphen.
Ein Implikationsgraph ist ein gerichteter, azyklischer Graph <math>G=(V,E)</math>. Jeder Knoten <math>v \in V</math> besteht dabei aus einem Tupel <math>(x \in \{false, true\}, \ d)</math> oder einem Element <math>c</math>. Während das Tupel für eine Zuweisung von wahr oder falsch für ein Literal <math>x</math> auf Ebene <math>d</math> des Suchbaumes steht, steht <math>c</math> für einen aufgetretenen Konflikt. Ein Konflikt tritt auf, wenn ein Literal gleichzeitig den Wert wahr und den Wert falsch annehmen müsste.
Wenn der Algorithmus ein Literal willkürlich mit einem Wahrheitswert belegt, wird der entsprechende Knoten <math>v</math> mit dem Tupel, das diese Zuweisung repräsentiert, zu <math>G</math> hinzugefügt. Erzwingt diese Zuweisung durch Unit Propagation eine weitere Zuweisung, so wird ein weiterer Knoten <math>w</math> und eine Kante <math>e = (v, w)</math> zum Graphen hinzugefügt.
Im Folgenden ein Beispiel mit der Formel: (<math>x_1</math> ∨ <math>x_4</math>) ∧ (<math>x_1</math> ∨ <math>\lnot x_3</math> ∨ <math>\lnot x_8</math>) ∧ (<math>x_1</math> ∨ <math>x_8</math> ∨ <math>x_{12}</math>) ∧ (<math>x_2</math> ∨ <math>x_{11}</math>) ∧ (<math>\lnot x_7</math> ∨ <math>\lnot x_3</math> ∨ <math>x_9</math>) ∧ (<math>\lnot x_7</math> ∨ <math>x_8</math> ∨ <math>\lnot x_9</math>) ∧ (<math>x_7</math> ∨ <math>x_8</math> ∨ <math>\lnot x_{10}</math>) ∧ (<math>x_7</math> ∨ <math>x_1</math> ∨ <math>\lnot x_{12}</math>)
-
Implikationsgraph nach dem 8. Schritt
-
Implikationsgraph mit Konflikt
- Wähle <math>x_1</math> willkürlich und belege es (wieder willkürlich) mit false.
- Unit Propagation erzwingt eine Belegung von <math>x_4</math> mit true. Damit wird die Klausel (<math>x_1</math> ∨ <math>x_4</math>) wahr.
- Wähle <math>x_3</math> und belege es mit true.
- Unit Propagation erzwingt nun die Belegung von <math>x_8</math> mit false (wegen <math>x_1</math> = false). Die Klausel (<math>x_1</math> ∨ <math>\lnot x_3</math> ∨ <math>\lnot x_8</math>) wird wahr.
- Unit Propagation erzwingt die Belegung von <math>x_{12}</math> mit true (wegen <math>x_8</math> = false). Die Kausel (<math>x_1</math> ∨ <math>x_8</math> ∨ <math>x_{12}</math>) wird wahr.
- Wähle <math>x_2</math> und belege es mit false.
- Unit Propagation erzwingt nun die Belegung von <math>x_{11}</math> mit true. Die Klausel (<math>x_2</math> ∨ <math>x_{11}</math>) wird wahr.
- Wähle <math>x_7</math> und belege es mit true. Die Klauseln (<math>x_7</math> ∨ <math>x_8</math> ∨ <math>\lnot x_{10}</math>) und (<math>x_7</math> ∨ <math>x_1</math> ∨ <math>\lnot x_{12}</math>) werden wahr.
- Ein Konflikt tritt auf für <math>x_9</math>. Unit Propagation muss die Klauseln (<math>\lnot x_7</math> ∨ <math>\lnot x_3</math> ∨ <math>x_9</math>) ∧ (<math>\lnot x_7</math> ∨ <math>x_8</math> ∨ <math>\lnot x_9</math>) erfüllen, die inzwischen zu <math>x_9</math> ∧ <math>\lnot x_9</math> reduziert wurden. Der Konfliktknoten <math>c</math> wird in den Implikationsgraphen eingefügt.
Der Algorithmus analysiert nun den Konflikt mithilfe des Implikationsgraphen und entscheidet, welche Klausel gelernt werden soll und zu welchem Entscheidungslevel im Suchbaum zurückgesprungen werden soll. In Frage kommende Klauseln heißen conflict clause und sollen verhindern, dass die Fehlentscheidung des Algorithmus, die zum Konflikt geführt hat, wiederholt wird. Eine solche conflict clause wird zur Klauselmenge hinzugefügt. Das maximale Entscheidungslevel der Variablen aus der conflict clause bestimmt das Entscheidungslevel für das Backjumping.
Eine abstrakte Beschreibung von CDCL im Pseudocode sieht wie folgt aus:<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Emina Torlak|Emina Torlak: }}{{#if:|{{#if:A Modern SAT Solver Lecture, University of Washington|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=A Modern SAT Solver Lecture, University of Washington}}]{{#if:PDF| (PDF)}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=A Modern SAT Solver Lecture, University of Washington}}}}|[{{#invoke:URLutil|getNormalized|1=https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=A Modern SAT Solver Lecture, University of Washington}}}}]}}{{#if:PDF| (PDF{{#if:{{#if: 2020-11-08 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
| )
| {{#if:{{#ifeq:en|de||{{#if:en|1}}}}| ;
| )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf}}%7C%7C}}}}{{#if:A Modern SAT Solver Lecture, University of Washington|{{#if:{{#invoke:WLink|isValidLinktext|1=A Modern SAT Solver Lecture, University of Washington|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: | {{{hrsg}}}{{#if: |,|{{#if: 2020-11-08 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
|{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
|{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: |,|{{#if: 2020-11-08 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2020-11-08 | {{#if:{{#invoke:TemplUtl|faculty|}}||,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:65083||(?)}}}}}}{{#if: 2020-11-08|;}}}}{{#if: 2020-11-08| {{#if:{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2020-11-08 |ISO|noerror=1}} }}
|4=im Jahr
|7=im
|10=am
|#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2020-11-08|class=Zitationswartung}} }} {{#invoke:DateTime|format|2020-11-08|T._Monat JJJJ}}
| {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:en|de||{{#if:en|1}}}}|{{#if:{{#if: 2020-11-08 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
| (
| {{#if:PDF | | (}}
}}{{#ifeq:{{#if:en|en|de}}|de||
{{#invoke:Multilingual|format|en|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:en|en|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2020-11-08 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}en|{{#if: |: {{
#if:
| „{{
#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
| Vorlage:Str trim
| {{#invoke:Vorlage:lang|flat}}
}}“
| {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
| „Vorlage:Str trim“
| {{#invoke:Text|quote
|1={{#if:
| {{#invoke:Vorlage:lang|flat}}
| {{#invoke:Vorlage:lang|flat}} }}
|2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
|3=1}} }}
}}{{#if:
| (<templatestyles src="Person/styles.css" />{{#if: | : }}{{#if: | , deutsch: „“ }})
| {{#if:
| ({{#if: | , deutsch: „“ }})
| {{#if: | (deutsch: „“) }}
}}
}}{{#if: {{{zitat}}}
| {{#if:
| {{#if: {{{zitat}}}
| Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
| Vorlage:": Text= fehlt }}{{#if: | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
| Vorlage:": Ungültiger Wert: ref=
| {{{ref}}} }}
}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch:
|0|=Vorlage:Toter Link/Core{{#if: https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf | {{#if: | [3] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }} }} | (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.) }}{{#switch: |no|0|= |#default={{#if: || }} }}{{#invoke:TemplatePar|check |opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf | {{#if:{{#invoke:URLutil|isWebURL|https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#if: | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch: |no|0|= |#default= {{#if: || }} }}{{#invoke:TemplatePar|check |all = inline= url= |opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf | {{#if:{{#invoke:URLutil|isWebURL|https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: deadurl |checked|deadurl|= |#default= {{#if: || }} }}[https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf }}|{{#switch: |0|=Vorlage:Toter Link/Core{{#if: https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf | {{#if: | [4] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: | {{#if: | | Vorlage:Toter Link/archivebot }} }} | (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.) }}{{#switch: |no|0|= |#default={{#if: || }} }}{{#invoke:TemplatePar|check |opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf | {{#if:{{#invoke:URLutil|isWebURL|https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf}} || {{#if: || }} }} | {{#if: | {{#if: || }} | {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. ) {{#if: | {{#if: | | Vorlage:Toter Link/archivebot }} }}Vorlage:Toter Link/Core{{#switch: |no|0|= |#default= {{#if: || }} }}{{#invoke:TemplatePar|check |all = inline= url= |opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= |cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link |errNS = 0 |template = Vorlage:Toter Link |format = |preview = 1 }}{{#if: https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf | {{#if:{{#invoke:URLutil|isWebURL|https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf}} || {{#if: || }} }} }}{{#if: | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}} || {{#if: || }} }} }}{{#switch: |checked|deadurl|= |#default= {{#if: || }} }}[https://courses.cs.washington.edu/courses/cse507/17wi/lectures/L02.pdf }} }}}}}}}}}}{{#if:| {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}
}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref>
function CDCL(F : set of clauses)
G <- Implikationsgraph();
if unit-propagate(F, G) findet Konflikt then
return false;
level ← 0;
while F hat nicht zugewiesene Variablen do
level ← level + 1;
choose-literal(F, G);
while unit-propagate(F, G) findet Konflikt do
# Ermittle Ebene für Backjump und zu lernende Klausel
(d, c) ← analyzeConflict(G);
# Lerne
F ← F ∪ {c};
# Wenn der Konflikt nicht aufgelöst werden kann
if d < 0 then
return false;
else
backjump(F, d);
level ← d;
return true;
Dabei aktualisieren unit-propagate(F, G) und choose-literal(F, G) jeweils entsprechend den Implikationsgraphen. Die Funktion analyzeConflict(G) wird durch die Strategie des clause learning bestimmt.
Conflict Clauses
Um eine conflict clause zu ermitteln untersucht man Schnitte im Implikationsgraphen. Ein Schnitt generiert eine conflict clause genau dann, wenn er den Graph so in zwei Hälften partitioniert, dass eine Hälfte (die decision side) alle decision nodes enthält und die andere Hälfte den Konfliktknoten. Die decision nodes sind dabei die willkürlichen Entscheidungen, die zum Konflikt geführt haben.
Aus dem Implikationsgraphen wird ersichtlich, dass z. B. für <math>x_3</math> und <math>x_7</math> eine willkürliche Entscheidung getroffen wurde, aber die Entscheidung für die Belegung von <math>x_8</math> eine Konsequenz aus der Entscheidung für die Belegung von <math>x_1</math> und <math>x_3</math> war. Die Knoten für <math>x_1</math>, <math>x_3</math>, <math>x_7</math> sind also die decision nodes.
Ein Beispiel für einen Schnitt, der eine conflict clause generiert, ist ein Schnitt durch die eingehenden Kanten des Konfliktknotens (roter Schnitt in der Abbildung). Die Knoten auf der decision side repräsentieren die Ursache des Konfliktes, nämlich <math>x_3 \land x_7 \land \lnot x_8 \implies Konflikt</math>. Durch Kontraposition erhält man <math> \lnot Konflikt \implies \lnot x_3 \lor \lnot x_7 \lor x_8 </math>, ein Beispiel für eine conflict clause. Eine andere Möglichkeit stellt der blaue Schnitt durch die ausgehenden Kanten der decision nodes dar. Er generiert die conflict clause <math> \lnot x_1 \lor x_3 \lor x_7 </math>. Diese Variante wurde in Rel_sat<ref>{{#invoke:Vorlage:Literatur|f}}</ref> implementiert, einem der ersten CDCL SAT-Solver.<ref>{{#invoke:Vorlage:Literatur|f}}</ref> Eine fortgeschrittene Variante wird von der Implementierung GRASP<ref>{{#invoke:Vorlage:Literatur|f}}</ref> eingesetzt.
Two Watched Literals (TWL, 2WL)
Es bleibt das Problem, Einheitsklauseln für die Unit Propagation und Konflikte effizient zu finden. Lange Zeit haben Solver dafür die Anzahl Literale, die in einer Klausel noch nicht mit Wahrheitswerten belegt worden sind, mitgezählt. Wenn sich dieser Zähler von 2 auf 1 ändert wendet man Unit Propagation an. Da uns der genaue Wert des Zählers aber eigentlich nicht interessiert, sondern wir nur wissen müssen, wann sich die Zahl auf eins ändert, verfolgen wir nicht die Klauseln selbst, sondern jeweils zwei Literale pro Klausel – die two watched literals. TWL ist also eine Datenstruktur, die die Suche nach Konflikten oder Einheitsklauseln beschleunigt.
Jede Klausel, die noch nicht erfüllt ist, besitzt zwei watched literals. Die Information wird dabei nicht von den Klauseln gespeichert, sondern von den Literalen selbst. Jeder Literal <math> l </math> besitzt also eine Liste mit Klauseln, in denen er vorkommt. Diese Klauseln werden in einer Liste verkettet, der watch list.
Die TWL einer Klausel erfüllen folgende Invariante:
{{#ifeq: {{{vor}}}@@-@@{{{nach}}} | -@@-@@-
| {{#if:trim|Solange kein Konflikt gefunden wurde darf ein watched literal nur false sein, solange der andere watched literal true ist und alle unwatched literals false sind.}}
| {{#ifeq: {{#if:|{{{vor}}}|@#@}}{{#if:|{{{nach}}}|@#@}} | @#@@#@
| {{#ifeq: de | de
| „{{#if:trim|Solange kein Konflikt gefunden wurde darf ein watched literal nur false sein, solange der andere watched literal true ist und alle unwatched literals false sind.}}“
| {{#invoke:Text|quoteUnquoted| Solange kein Konflikt gefunden wurde darf ein watched literal nur false sein, solange der andere watched literal true ist und alle unwatched literals false sind. | {{{lang}}} }} }}
| {{#ifeq: {{#if:|{{{vor}}}|-}} | -
| „
| {{{vor}}} }}{{#if:trim|Solange kein Konflikt gefunden wurde darf ein watched literal nur false sein, solange der andere watched literal true ist und alle unwatched literals false sind.}}{{
#ifeq: {{#if:|{{{nach}}}|-}} | -
| “
| {{{nach}}} }} }} }}{{
#if: || <ref>{{#invoke:Vorlage:Literatur|f}}</ref> }}
{{#if:
|
„{{{Latn}}}“{{#if: || <ref>{{#invoke:Vorlage:Literatur|f}}</ref> }}
}}{{#if:
|
„{{{de}}}“{{#if: || <ref>{{#invoke:Vorlage:Literatur|f}}</ref> }}
}}|{{#if:
|}}}}
{{#if: <ref>{{#invoke:Vorlage:Literatur|f}}</ref> |
{{#if: {{#invoke:Text|unstrip|<ref>{{#invoke:Vorlage:Literatur|f}}</ref>}}
| }} }}{{#if: Solange kein Konflikt gefunden wurde darf ein watched literal nur false sein, solange der andere watched literal true ist und alle unwatched literals false sind. | {{
#if: | {{#if: Solange kein Konflikt gefunden wurde darf ein watched literal nur false sein, solange der andere watched literal true ist und alle unwatched literals false sind. |
Vorlage:Zitat: Doppelangabe 1=Text=}}
}}| }}{{#if: | {{#if: |
Vorlage:Zitat: Doppelangabe 2=Autor=}}
}}{{#if: | {{#if: |
Vorlage:Zitat: Doppelangabe 3=Quelle=}}
}}{{#if: | {{#if: |
Vorlage:Zitat: Doppelangabe Umschrift=Latn=}}
}}{{#if: | {{#if: |
Vorlage:Zitat: Doppelangabe Sprache=lang=}}
}}{{#if: | {{#if: |
Vorlage:Zitat: Doppelangabe Übersetzung=de=}}
}}
Die Invariante führt dazu, dass die Belegung eines unwatched literals mit einem Wahrheitswert niemals zu einer unit propagation oder einem Konflikt führen wird. Wenn wir nun aber einem watched literal <math>l</math> einen Wahrheitswert zuweisen, müssen wir eventuell die Invariante reparieren, unit propagation anwenden oder einen Konflikt auflösen. Betrachten wir die Klauseln, in denen die Negation von <math>l</math>, also <math>\lnot l</math> vorkommt. Diese können durch die watch list effizient gefunden werden. Wir verfahren für diese wie folgt:
- Ist der andere watched literal der Klausel true, müssen wir nichts tun.
- Ist einer der unwatched literals <math>l'</math> der Klausel nicht false, wählen wir <math>l'</math> als watched literal, der <math>\lnot l</math> ersetzt.
- Ist der andere watched literal <math>l'</math> für diese Klausel noch nicht mit einem Wahrheitswert belegt, führe unit propagation für <math> l'</math> durch. Ansonsten ist <math>l'</math> false und ein Konflikt wurde gefunden.
TWL wurde für den SAT-Solver Chaff<ref>{{#invoke:Vorlage:Literatur|f}}</ref> entwickelt, um die unit propagation in der Praxis zu optimieren.
Random Restart
Random Restarts setzen alle Variablenbelegungen zurück und starten die Suche mit einer anderen Reihenfolge der Variablenbelegung neu. Damit wird das Problem umgangen, dass manche dieser Zuweisungsreihenfolgen zu sehr viel länger andauernden Berechnungen mit vielen Konflikten führen, während geeignete Reihenfolgen das Problem schneller lösen. Dabei werden gelernte Klauseln und die aktuell zugewiesenen Werte der Variablen übernommen. Wann ein Restart durchgeführt wird bestimmt eine Strategie, z. B. fixed nach n Konflikten, in Abständen, die einer Reihe wie der geometrischen Reihe folgen oder dynamisch, wenn sich Konflikte beginnen zu häufen. Restart-Strategien sind häufig an eine bestimmte Klasse von Instanzen angepasst und aggressivere Strategien haben sich in vielen Fällen als effizient herausgestellt.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>
Lokale Suche
SAT-Solver, die auf dem Prinzip der lokalen Suche basieren, führen im Grunde folgende Schritte aus:
- Weise jeder Variable einen Zufallswert true oder false zu.
- Wenn alle Klauseln erfüllt sind, terminiere und gebe die Variablenbelegung zurück.
- Ansonsten negiere eine Variable und wiederhole.
Die aussagenlogische Formel ist dabei als konjunktive Normalform gegeben. Unterschiede zwischen SAT-Solvern, die lokale Suche implementieren, finden sich vor allem bei der Wahl der Variable, die negiert wird.
GSAT<ref>{{#invoke:Vorlage:Literatur|f}}</ref> negiert die Variable, die die Zahl an nicht erfüllten Klauseln minimiert oder wählt mit einer gewissen Wahrscheinlichkeit eine zufällige Variable.
WalkSAT<ref>{{#invoke:Vorlage:Literatur|f}}</ref> wählt eine zufällige, nicht erfüllte Klausel und negiert eine Variable. Dabei wird die Variable ausgewählt, die am wenigsten bereits erfüllte Klauseln nicht erfüllt werden lässt. Die Wahrscheinlichkeit, dass eine falsche Variablenzuweisung korrigiert wird, ist der Kehrwert der Anzahl der Variablen in der Klausel. Mit einer gewissen Wahrscheinlichkeit wird auch hier einfach eine zufällige Variable der Klausel ausgewählt.
Beide Varianten erlauben zufällige Zuweisungen mit einer gewissen Wahrscheinlichkeit, um das Problem der lokalen Maxima zu umgehen. Außerdem werden zufällige Neustarts erlaubt, wenn für eine zu lange Zeit keine Lösung gefunden wurde.
Parallelisierung
{{#if: Parallele Algorithmen für das Erfüllbarkeitsproblem|{{#ifexist:Parallele Algorithmen für das Erfüllbarkeitsproblem|
|{{#if: |{{#ifexist:{{{2}}}|
|{{#if: |{{#ifexist:{{{3}}}|
|}}|}}|}}|}}|}}|Einbindungsfehler: Die Vorlage Hauptartikel benötigt immer mindestens ein Argument.}}
Parallele SAT-Solver können in drei Kategorien eingeteilt werden: Portfolio, Divide-and-conquer und parallele lokale Suche.
Portfolio
Portfolio SAT-Solver beruhen auf der Tatsache, dass die meisten SAT-Solver auf bestimmten Probleminstanzen effizient sind, aber auf anderen Instanzen langsamer sind als andere Algorithmen. Gegeben eine beliebige Instanz von SAT, so gibt es keine verlässliche Möglichkeit, um vorherzusagen, welcher Algorithmus die Instanz am schnellsten lösen wird. Der Portfolio-Ansatz verwendet nun verschiedene Ansätze parallel, um die Vorteile verschiedener SAT-Solver zu kombinieren. Ein Nachteil der Methode ist natürlich, dass alle parallelen Prozesse im Prinzip die gleiche Arbeit verrichten. Trotzdem haben sich Portfolio-Solver in der Praxis als effizient herausgestellt.
Cube-And-Conquer
Divide-and-conquer Algorithmen beruhen auf dem Ansatz, ein Problem in kleinere Teilprobleme aufzuteilen, diese rekursiv zu bearbeiten und die Teilergebnisse zu kombinieren. DPLL und CDCL sind divide-and-conquer Algorithmen, die den Suchraum bei jeder Entscheidung für eine Variablenbelegung in zwei Hälften aufteilen. Durch unit propagation und pure literal elimination können diese Hälften aber sehr unterschiedlich schwer zu lösende Teilinstanzen von SAT darstellen. CDCL verschärft dieses Problem durch die Anwendung weiterer Techniken. Cube-and-conquer ist ein Ansatz, der dieses Problem in zwei Phasen löst.
- Cube Phase. Die Instanz von SAT wird von einem SAT-Solver in viele (einige Tausend bis einige Millionen) Teilprobleme aufgeteilt, sogenannte Würfel. Ein Würfel ist dabei eine Konjunktion einer Teilmenge der Literale der Originalformel F.
- Konjunktiv mit F verknüpft ergibt sich eine neue Formel F′, die unabhängig von den anderen Teilproblemen gelöst werden kann (z. B. CDCL). Die Disjunktion aller F′ ist äquivalent zu F. Der Algorithmus terminiert also, sobald ein Teilproblem erfüllbar ist.
Für die Cube Phase wird in der Regel ein Look-Ahead-Solver eingesetzt, da diese sich für kleine, aber schwere Probleme bewährt haben und globaler arbeiten als z. B. CDCL.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>
Parallele lokale Suche
Parallele lokale Suche ist leicht zu parallelisieren: Flips von verschiedenen Variablen werden parallel durchgeführt oder ein Portfolio-Ansatz wird verwendet, indem unterschiedliche Strategien für die Variablenauswahl gleichzeitig angewandt werden.
Praxis
Die SAT-Competition ist ein Wettbewerb<ref>The International SAT Competition Web Page</ref> für SAT-Solver, der jährlich im Rahmen der International Conference on Theory and Applications of Satisfiability Testing stattfindet.<ref>The International Conferences on Theory and Applications of Satisfiability Testing (SAT)</ref> In verschiedenen Disziplinen werden unterschiedliche Qualitäten von SAT-Solvern evaluiert:
- Sequentielle Performance (teilweise existieren separate Wettbewerbe für bestimmte Klassen von Instanzen, z. B. Instanzen aus dem Automated Planning)
- Mäßige Parallelisierung auf einer einzelnen Maschine mit Shared Memory
- Massive Parallelisierung auf verteilten Maschinen
- Inkrementelle SAT-Solver, also SAT-Solving für Anwendungen, die mehrere Lösungsschritte benötigen. Dabei wird eine Sequenz verwandter SAT-Instanzen gelöst, wobei bereits gelernte Informationen aus früheren Instanzen wiederverwendet werden.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>
Die SAT-Association ist eine Vereinigung, die sich zum Ziel gesetzt hat, Forschung im Bereich SAT, SAT-Solver und der formalen Verifikation voranzubringen und die SAT-Community zu repräsentieren.<ref>The SAT Association</ref> Sie beaufsichtigt die Organisation der genannten Konferenzen und Wettbewerbe und gibt das Journal on Satisfiability, Boolean Modeling, and Computation (JSAT) heraus.<ref>Journal on Satisfiability, Boolean Modeling and Computation {{#invoke:URIutil|{{#ifeq:1|1|linkISSN|targetISSN}}|1574-0617|0}}{{#ifeq:1|0|[!] }}{{#ifeq:0|1
|{{#switch:00
|11= (print/online)
|10= (print)
|01= (online)
}}
}}{{#ifeq:0|0
|{{#ifeq:0|0
|{{#if:{{#invoke:URIutil|isISSNvalid|1=1574-0617}}
|
|{{#invoke:TemplUtl|failure|ISSN ungültig}}}}}}
}}</ref>
Siehe auch
- Aussagenlogik
- Resolution (Logik)
- Komplexitätstheorie
- NP-Vollständigkeit
- Formale Verifikation
- Erfüllbarkeitsproblem für Schaltkreise
Einzelnachweise
<references />
{{safesubst:#ifeq:0|10| {{#switch: Erfüllbarkeitsproblem der Aussagenlogik |Navigationsleiste|NaviBlock|0=|#default= Vorlage:Templatetransclusioncheck Vorlage:Dokumentation/ruler }}}}Vorlage:Klappleiste/Anfang {{#if:
|
Erfüllbarkeitsproblem der Aussagenlogik | Cliquenproblem | Mengenpackungsproblem | Knotenüberdeckungsproblem | Mengenüberdeckungsproblem | Feedback Arc Set | Feedback Vertex Set | Hamiltonkreisproblem | Integer Linear Programming | 3-SAT | graph coloring problem | Covering by cliques | Problem der exakten Überdeckung | 3-dimensional matching | Steinerbaumproblem | Hitting set | Rucksackproblem | Job sequencing | Partitionsproblem | Maximaler Schnitt
|
Erfüllbarkeitsproblem der Aussagenlogik | Cliquenproblem | Mengenpackungsproblem | Knotenüberdeckungsproblem | Mengenüberdeckungsproblem | Feedback Arc Set | Feedback Vertex Set | Hamiltonkreisproblem | Integer Linear Programming | 3-SAT | graph coloring problem | Covering by cliques | Problem der exakten Überdeckung | 3-dimensional matching | Steinerbaumproblem | Hitting set | Rucksackproblem | Job sequencing | Partitionsproblem | Maximaler Schnitt }} Vorlage:Klappleiste/Ende
- Seiten mit defekten Dateilinks
- Wikipedia:Vorlagenfehler/Parameter:URL
- Wikipedia:Vorlagenfehler/Parameter:Linktext
- Wikipedia:Vorlagenfehler/Parameter:Datum
- Wikipedia:Vorlagenfehler/Vorlage:"
- Wikipedia:Weblink offline fix-attempted
- Wikipedia:Vorlagenfehler/Vorlage:Toter Link
- Wikipedia:Vorlagenfehler/Vorlage:Toter Link/URL fehlt
- Wikipedia:Vorlagenfehler/Vorlage:Zitat
- Wikipedia:Vorlagenfehler/Parameter:ISSN
- Komplexitätstheorie
- Mathematische Logik
- Aussagenlogik