DPLL-algoritme - DPLL algorithm

DPLL

I en CNF-SAT- formel: 1-Vælg en bogstavelig 2-Tildel en sandhedsværdi til den 3-Forenkle formlen 4-Kontroller tilfredsstillelse; 5-Hvis du ikke er tilfreds, skal du foretage backtracking
Klasse	Boolsk tilfredsstillelsesproblem
Datastruktur	Binært træ
Worst case ydeevne	${\ displaystyle O (2 ^ {n})}$
Bedste ydeevne	${\ displaystyle O (1)}$ (konstant)
Værste tilfælde af rumkompleksitet	${\ displaystyle O (n)}$ (grundlæggende algoritme)

Inden for logik og datalogi er Davis – Putnam – Logemann – Loveland ( DPLL ) -algoritmen en komplet , backtracking- baseret søgealgoritme til at afgøre, om propositionelle logiske formler er tilfredsstillende i konjunktiv normal form , dvs. til løsning af CNF-SAT- problemet.

Den blev introduceret i 1961 af Martin Davis , George Logemann og Donald W. Loveland og er en forbedring af den tidligere Davis – Putnam-algoritme , som er en resolutionsbaseret procedure udviklet af Davis og Hilary Putnam i 1960. Især i ældre publikationer, Davis – Logemann – Loveland-algoritme kaldes ofte "Davis – Putnam-metoden" eller "DP-algoritmen". Andre almindelige navne, der opretholder forskellen, er DLL og DPLL.

Efter mere end 50 år danner DPLL-proceduren stadig grundlaget for de mest effektive komplette SAT-opløsere. Det er for nylig blevet udvidet til automatisk sætning, der viser fragmenter af førsteordenslogik ved hjælp af DPLL (T) -algoritmen.

Implementeringer og applikationer

Det SAT Problemet er vigtig både fra teoretiske og praktiske synsvinkler. I kompleksitetsteori var det det første problem, der viste sig at være NP-komplet og kan forekomme i en bred vifte af applikationer såsom modelkontrol , automatiseret planlægning og planlægning og diagnose i kunstig intelligens .

Som sådan har det været et varmt emne inden for forskning i mange år, og konkurrencer mellem SAT-løsere finder regelmæssigt sted. DPLLs moderne implementeringer som Chaff og zChaff , GRASP eller MiniSat er de første steder i konkurrencerne de sidste år.

En anden applikation, der ofte involverer DPLL, er automatiseret sætning, der viser eller er tilfredsstillende modulo teorier (SMT), hvilket er et SAT-problem, hvor propositionelle variabler erstattes med formler af en anden matematisk teori .

Algoritmen

Den grundlæggende backtracking-algoritme kører ved at vælge en bogstavelig, tildele den en sandhedsværdi , forenkle formlen og derefter rekursivt kontrollere, om den forenklede formel er tilfredsstillende; hvis dette er tilfældet, er den oprindelige formel tilfredsstillende; ellers udføres den samme rekursive kontrol under forudsætning af den modsatte sandhedsværdi. Dette er kendt som opdelingsreglen , da det opdeler problemet i to enklere delproblemer. Forenklingstrinnet fjerner i det væsentlige alle klausuler, der bliver sande under tildelingen, fra formlen og alle bogstaver, der bliver falske fra de resterende klausuler.

DPLL-algoritmen forbedres over backtracking-algoritmen ved ivrig brug af følgende regler ved hvert trin:

Enhedsformering

Hvis en klausul er en enhedsklausul , dvs. at den kun indeholder en enkelt ikke-tildelt bogstavelig, kan denne klausul kun opfyldes ved at tildele den nødvendige værdi for at gøre denne bogstavelige sand. Derfor er intet valg nødvendigt. Enhedsformering består i at fjerne hver klausul, der indeholder en enheds klausul, og at kassere komplementet til en klausul i bogstavet fra hver klausul, der indeholder det komplement. I praksis fører dette ofte til deterministiske kaskader af enheder, hvorved en stor del af det naive søgerum undgås.

Ren bogstavelig eliminering

Hvis en propositionsvariabel forekommer med kun en polaritet i formlen, kaldes den ren . En ren bogstavelig kan altid tildeles på en måde, der gør alle klausuler indeholdende det sande. Når det således er tildelt sådan, begrænser disse klausuler ikke søgningen længere og kan slettes.

Utilfredsstillelse af en given delopgave opdages, hvis en klausul bliver tom, dvs. hvis alle dens variabler er tildelt på en måde, der gør de tilsvarende bogstaver falske. Formelens tilfredsstillelse detekteres enten når alle variabler tildeles uden at generere den tomme klausul, eller i moderne implementeringer, hvis alle klausuler er opfyldt. Utilfredsstillelse af den komplette formel kan kun detekteres efter udtømmende søgning.

DPLL-algoritmen kan opsummeres i følgende pseudokode, hvor Φ er CNF- formlen:

Algorithm DPLL
    Input: A set of clauses Φ.
    Output: A Truth Value.

function DPLL(Φ)
    if Φ is a consistent set of literals then
        return true;
    if Φ contains an empty clause then
        return false;
    for every unit clause {l} in Φ do
        Φ ← unit-propagate(l, Φ);
    for every literal l that occurs pure in Φ do
        Φ ← pure-literal-assign(l, Φ);
    l ← choose-literal(Φ);
    return DPLL(Φ ∧ {l}) or DPLL(Φ ∧ {not(l)});

I denne pseudokode, unit-propagate(l, Φ)og pure-literal-assign(l, Φ)er funktioner, der returnerer resultatet af anvendelse af henholdsvis enhedsformering og den rene bogstavelige regel til den bogstavelige log formlen Φ. Med andre ord erstatter de enhver forekomst af lmed "sand" og hver forekomst af not lmed "falsk" i formlen Φog forenkler den resulterende formel. Den ori returnerklæringen er en kortslutning operatør . betegner det forenklede resultat af at erstatte "sand" med i . Φ ∧ {l}lΦ

Algoritmen slutter i en af ​​to tilfælde. Enten viser det sig, at CNF-formlen Φomfatter et ensartet sæt af bogstaver - det vil sige, der er ingen log ¬lfor nogen bogstavelig li formlen (der er kun rene bogstaver). Hvis dette er tilfældet, kan variablerne trivielt tilfredsstilles ved at indstille dem til den respektive polaritet af den omfattende bogstav i værdiansættelsen. Ellers, når formlen indeholder en tom klausul, er klausulen vakuum falsk, fordi en disjunktion kræver mindst et medlem, der er sandt for at det samlede sæt skal være sandt. I dette tilfælde indebærer eksistensen af ​​en sådan klausul, at formlen (evalueret som en sammenhæng mellem alle klausuler) ikke kan evalueres til sandt og skal være utilstrækkelig.

Pseudokode DPLL-funktionen returnerer kun, om den endelige opgave opfylder formlen eller ej. I en reel implementering returneres den delvis tilfredsstillende opgave typisk også efter succes; dette kan afledes af det konsistente sæt af bogstaver i den første ifsætning af funktionen.

Davis – Logemann – Loveland-algoritmen afhænger af valget af forgrenings-bogstavelig , hvilket er den bogstavelige, der betragtes i backtracking-trinnet. Som et resultat er dette ikke ligefrem en algoritme, men snarere en familie af algoritmer, en for hver mulig måde at vælge den forgrenede bogstavelige. Effektivitet er stærkt påvirket af valget af forgreningens bogstavelige: der findes tilfælde, hvor køretiden er konstant eller eksponentiel, afhængigt af valget af forgreningens bogstaver. Sådanne valgfunktioner kaldes også heuristiske funktioner eller forgreningsheuristikker.

Visualisering

Davis, Logemann, Loveland (1961) havde udviklet denne algoritme. Nogle egenskaber ved denne oprindelige algoritme er:

• Det er baseret på søgning.
• Det er grundlaget for næsten alle moderne SAT-løsere.
• Det bruger ikke læring eller ikke-kronologisk backtracking (introduceret i 1996).

Et eksempel med visualisering af en DPLL-algoritme med kronologisk backtracking:

• 

  Alle klausuler, der fremstiller en CNF-formel

• 

  Vælg en variabel

• 

  Lav en beslutning, variabel a = Falsk (0), så grønne klausuler bliver sande

• 

  Efter at have taget flere beslutninger finder vi en implikationsgraf, der fører til en konflikt.

• 

  Gå tilbage til det øjeblikkelige niveau, og tildel med variabel den modsatte værdi med tvang

• 

  Men en tvungen beslutning fører stadig til en anden konflikt

• 

  Gå tilbage til det forrige niveau, og lav en tvungen beslutning

• 

  Lav en ny beslutning, men det fører til en konflikt

• 

  Lav en tvungen beslutning, men igen fører det til en konflikt

• 

  Tilbage til forrige niveau

• 

  Fortsæt på denne måde og den endelige implikationsgraf

Nuværende arbejde

I 2010'erne er der arbejdet med at forbedre algoritmen i tre retninger:

1. Definition af forskellige politikker til valg af forgreningsbogstaver.
2. Definere nye datastrukturer for at gøre algoritmen hurtigere, især delen om enhedsformering .
3. Definition af varianter af den grundlæggende backtracking-algoritme. Sidstnævnte retning inkluderer ikke-kronologisk backtracking (alias backjumping ) og klausul læring . Disse forbedringer beskriver en metode til backtracking efter at have nået en konfliktklausul, som "lærer" de grundlæggende årsager (tildelinger til variabler) af konflikten for at undgå at nå den samme konflikt igen. De resulterende konfliktdrevne klausuler, der lærer SAT-løsere, er state of the art i 2014.

En nyere algoritme fra 1990 er Stålmarcks metode . Også siden 1986 (reduceret bestilt) er binære beslutningsdiagrammer også blevet brugt til SAT-løsning.

Forhold til andre forestillinger

Kørsler af DPLL-baserede algoritmer på tilfredsstilles tilfælde svarer til træ opløsning refutationssystemer prøvetryk.

Se også

• Bevis kompleksitet
• Herbrandization

Referencer

Generel

• Davis, Martin ; Putnam, Hilary (1960). "En beregningsprocedure til kvantificeringsteori" . ACM-tidsskrift . 7 (3): 201-215. doi : 10.1145 / 321033.321034 .
• Davis, Martin; Logemann, George; Loveland, Donald (1961). "Et maskinprogram til sætning af bevis" . Kommunikation af ACM . 5 (7): 394–397. doi : 10.1145 / 368273.368557 . hdl : 2027 / mdp.39015095248095 .
• Ouyang, Ming (1998). "Hvor gode er forgreningsregler i DPLL?" . Diskret anvendt matematik . 89 (1–3): 281–286. doi : 10.1016 / S0166-218X (98) 00045-6 .
• John Harrison (2009). Håndbog med praktisk logik og automatiseret resonnement . Cambridge University Press. s. 79-90. ISBN 978-0-521-89957-4.

Bestemt

Yderligere læsning

• Malaysisk Ganai; Aarti Gupta; Dr. Aarti Gupta (2007). SAT-baserede skalerbare formelle verificeringsløsninger . Springer. s. 23–32. ISBN 978-0-387-69166-4.
• Gomes, Carla P .; Kautz, Henry; Sabharwal, Ashish; Selman, Bart (2008). "Opløselighedsopløsere". I Van Harmelen, Frank; Lifschitz, Vladimir; Porter, Bruce (red.). Håndbog om videnrepræsentation . Grundlaget for kunstig intelligens. 3 . Elsevier. s. 89–134. doi : 10.1016 / S1574-6526 (07) 03002-7 . ISBN 978-0-444-52211-5.