DPLL-algoritme - DPLL algorithm

DPLL

I en CNF-SAT- formel: 1-Velg en bokstavelig 2-Tildel en sannhetsverdi til den 3-Forenkle formelen 4-Sjekk tilfredshet; 5-Hvis du ikke er fornøyd, gjør backtracking
Klasse	Boolsk tilfredsstillelsesproblem
Data struktur	Binært tre
Verste fall ytelse	${\ displaystyle O (2 ^ {n})}$
Best-case ytelse	${\ displaystyle O (1)}$ (konstant)
Verste tilfelle av kompleksitet i rommet	${\ displaystyle O (n)}$ (grunnleggende algoritme)

Innen logikk og informatikk er Davis – Putnam – Logemann – Loveland ( DPLL ) -algoritmen en komplett , backtracking- basert søkealgoritme for å avgjøre om det er tilfredsstillende med proposisjonelle logiske formler i konjunktiv normalform , dvs. for å løse CNF-SAT- problemet.

Den ble introdusert i 1961 av Martin Davis , George Logemann og Donald W. Loveland og er en forbedring av den tidligere algoritmen Davis – Putnam , som er en oppløsningsbasert prosedyre utviklet av Davis og Hilary Putnam i 1960. Spesielt i eldre publikasjoner, Davis – Logemann – Loveland-algoritmen blir ofte referert til som "Davis – Putnam-metoden" eller "DP-algoritmen". Andre vanlige navn som opprettholder skillet, er DLL og DPLL.

Etter mer enn 50 år danner DPLL-prosedyren fremdeles grunnlaget for mest effektive komplette SAT-løsere. Den har nylig blitt utvidet for automatisert setning som viser for fragmenter av førsteordenslogikk ved hjelp av DPLL (T) -algoritmen.

Implementeringer og applikasjoner

Den lør Problemet er viktig både fra teoretiske og praktiske ståsteder. I kompleksitetsteori var det det første problemet som viste seg å være NP-komplett , og det kan vises i et bredt spekter av applikasjoner som modellkontroll , automatisert planlegging og planlegging og diagnose i kunstig intelligens .

Som sådan har det vært et hett tema i forskning i mange år, og konkurranser mellom SAT-løsere finner regelmessig sted. DPLL moderne implementasjoner som Chaff og zChaff , GRASP eller Minisat er i de første stedene i konkurranser de siste årene.

En annen applikasjon som ofte involverer DPLL, er automatisert teorem bevisende eller tilfredshet modulo teorier (SMT), som er et SAT problem der proposisjonsvariabler erstattes med formler av en annen matematisk teori .

Algoritmen

Den grunnleggende backtracking-algoritmen løper ved å velge en bokstavelig, tildele den en sannhetsverdi , forenkle formelen og deretter rekursivt sjekke om den forenklede formelen er tilfredsstillende; hvis dette er tilfelle, er den opprinnelige formelen tilfredsstillende; ellers gjøres den samme rekursive kontrollen forutsatt den motsatte sannhetsverdien. Dette er kjent som delingsregelen , da den deler problemet i to enklere delproblemer. Forenklingstrinnet fjerner i hovedsak alle klausuler som blir sanne under oppgaven fra formelen, og alle bokstavene som blir falske fra de resterende klausulene.

DPLL-algoritmen forbedrer seg over backtracking-algoritmen ved ivrig bruk av følgende regler ved hvert trinn:

Enhetsutbredelse

Hvis en klausul er en enhetsklausul , dvs. at den bare inneholder en enkelt ikke tildelt bokstavelig, kan denne klausulen bare oppfylles ved å tildele den nødvendige verdien for å gjøre denne bokstavelige sanne. Dermed er ikke noe valg nødvendig. Enhetsutbredelse består i å fjerne hver ledd som inneholder en enhetsklausul bokstavelig og i å forkaste komplementet til en enhetsklausul bokstavelig fra hver ledd som inneholder det komplementet. I praksis fører dette ofte til deterministiske kaskader av enheter, og dermed unngås en stor del av det naive søkeområdet.

Ren bokstavelig eliminering

Hvis en proposisjonsvariabel forekommer med bare en polaritet i formelen, kalles den ren . En ren bokstav kan alltid tildeles på en måte som gjør alle klausuler som inneholder den sanne. Når det tildeles slik, begrenser ikke disse punktene søket lenger, og kan slettes.

Utilfredshet av en gitt deloppgave oppdages hvis en ledd blir tom, dvs. hvis alle variablene er tildelt på en måte som gjør de tilsvarende bokstavene falske. Formelens tilfredsstillelse oppdages enten når alle variablene tildeles uten å generere den tomme klausulen, eller i moderne implementeringer hvis alle klausuler er oppfylt. Mangelfullhet med den komplette formelen kan bare oppdages etter uttømmende søk.

DPLL-algoritmen kan oppsummeres i følgende pseudokode, der Φ er CNF- formelen:

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 pseudokoden, unit-propagate(l, Φ)og pure-literal-assign(l, Φ)er funksjoner som returnerer resultatet av å bruke enhetsforplantning og den rene bokstavlige regelen, henholdsvis til bokstavelig log formel Φ. Med andre ord, de erstatter hver forekomst av lmed "sann" og hver forekomst av not lmed "falsk" i formelen Φ, og forenkler den resulterende formelen. Den ori returnsetningen er en kortslutning operatør . betegner det forenklede resultatet av å erstatte "sann" med i . Φ ∧ {l}lΦ

Algoritmen avsluttes i ett av to tilfeller. Enten blir CNF-formelen Φfunnet å utgjøre et jevnt sett med bokstaver - det vil si at det ikke er noen log ¬lfor noen bokstavelige li formelen (det er bare rene bokstaver). Hvis dette er tilfelle, kan variablene tilfredsstilles trivielt ved å sette dem til den respektive polariteten til den omfattende bokstavene i verdsettelsen. Ellers, når formelen inneholder en tom klausul, er klausulen vakuum falsk fordi en disjunksjon krever minst ett medlem som er sant for at det totale settet skal være sant. I dette tilfellet innebærer eksistensen av en slik klausul at formelen (evaluert som en sammenheng av alle ledd) ikke kan evalueres til sant og må være utilfredsstillende.

Pseudokode DPLL-funksjonen returnerer bare om den endelige tildelingen tilfredsstiller formelen eller ikke. I en reell implementering blir den delvis tilfredsstillende oppgaven vanligvis også returnert etter suksess; Dette kan utledes fra det konsistente settet med bokstaver i den første ifsetningen av funksjonen.

Algoritmen Davis – Logemann – Loveland avhenger av valget av forgreningsbokstavelig , som er bokstavelig sett i tilbakesporingstrinnet. Som et resultat er dette ikke akkurat en algoritme, men snarere en familie av algoritmer, en for hver mulig måte å velge forgreningen bokstavelig på. Effektivitet påvirkes sterkt av valget av forgreningsbokstavelig: det finnes tilfeller der kjøretiden er konstant eller eksponentiell, avhengig av valget av forgreningsbokstavene. Slike valgfunksjoner kalles også heuristiske funksjoner eller forgreningsheuristikk.

Visualisering

Davis, Logemann, Loveland (1961) hadde utviklet denne algoritmen. Noen egenskaper ved denne opprinnelige algoritmen er:

• Det er basert på søk.
• Det er grunnlaget for nesten alle moderne SAT-løsere.
• Den bruker ikke læring eller ikke-kronologisk backtracking (introdusert i 1996).

Et eksempel med visualisering av en DPLL-algoritme som har kronologisk tilbakesporing:

• 

  Alle ledd som lager en CNF-formel

• 

  Velg en variabel

• 

  Ta en beslutning, variabel a = Falsk (0), og dermed blir grønne ledd sanne

• 

  Etter å ha tatt flere avgjørelser, finner vi en implikasjonsgraf som fører til en konflikt.

• 

  Gå tilbake til umiddelbar nivå, og tildel med variabel motsatt verdi med makt

• 

  Men en tvungen avgjørelse fører fremdeles til en annen konflikt

• 

  Gå tilbake til forrige nivå og ta en tvungen avgjørelse

• 

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

• 

  Ta en tvungen avgjørelse, men igjen fører det til en konflikt

• 

  Gå tilbake til forrige nivå

• 

  Fortsett på denne måten og den endelige implikasjonsgrafen

Nåværende arbeid

I 2010-årene har arbeidet med å forbedre algoritmen blitt gjort i tre retninger:

1. Definere forskjellige retningslinjer for valg av forgreningslitteratur.
2. Definere nye datastrukturer for å gjøre algoritmen raskere, spesielt delen om enhetsformering .
3. Definere varianter av den grunnleggende backtracking-algoritmen. Sistnevnte retning inkluderer ikke-kronologisk backtracking (aka backjumping ) og paragraflæring . Disse forbedringene beskriver en metode for tilbakesporing etter å ha nådd en konfliktklausul som "lærer" de grunnleggende årsakene (tilordninger til variabler) for konflikten for å unngå å nå den samme konflikten igjen. De resulterende konfliktdrevne satselærerne SAT-løsere er toppmoderne i 2014.

En nyere algoritme fra 1990 er Stålmarcks metode . Også siden 1986 (redusert bestilt) har binære beslutningsdiagrammer også blitt brukt for SAT-løsning.

Forhold til andre forestillinger

Kjøringer av DPLL-baserte algoritmer på unsatisfiable tilfeller samsvarer med tre oppløsnings imøtegåelse prøvetrykk.

Se også

• Bevis kompleksitet
• Herbrandization

Referanser

Generell

• Davis, Martin ; Putnam, Hilary (1960). "En databehandlingsprosedyre for kvantifiseringsteori" . Tidsskrift for ACM . 7 (3): 201–215. doi : 10.1145 / 321033.321034 .
• Davis, Martin; Logemann, George; Loveland, Donald (1961). "Et maskinprogram for teoriproving" . Kommunikasjon av 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 matematikk . 89 (1–3): 281–286. doi : 10.1016 / S0166-218X (98) 00045-6 .
• John Harrison (2009). Håndbok for praktisk logikk og automatisert resonnement . Cambridge University Press. s. 79–90. ISBN 978-0-521-89957-4.

Spesifikk

Videre lesning

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