SAT (booleska tillfredsställelse) är ett grundläggande problem inom datavetenskap, och dess studie har lett till utvecklingen av viktiga principer och tekniker som är i stort sett tillämpliga. Här är en uppdelning av de viktigaste principerna:
1. Representerar problem som booleska formler:
* kodning: Kärnidén att använda SAT -lösare är att kodning Ett givet problem (t.ex. schemaläggning, kretsdesign, planering) till en booleska formel i konjunktiv normalform (CNF). Detta innebär att identifiera beslutsvariablerna för problemet och representera begränsningarna på dessa variabler som logiska klausuler. Skönheten ligger i det faktum att ett brett utbud av problem kan uttryckas i detta format.
* konjunktiv normalform (CNF): Nästan alla SAT -lösare fungerar på formler i CNF. CNF är en logisk formel som är en konjunktion (och) klausuler, där varje klausul är en disjunktion (eller) av bokstäver. En bokstav är antingen en variabel eller dess negation. Till exempel:`(x eller inte y eller z) och (inte x eller y)`. Att vara i CNF gör sökprocessen mer strukturerad och effektiv.
2. Davis-Putnam-Logemann-Loveland (DPLL) Algoritm:
* Sökbaserad strategi: DPLL är grundalgoritmen för att lösa SAT -problem. Det är en komplett sökalgoritm som systematiskt undersöker utrymmet för möjliga variabla tilldelningar.
* beslut: Algoritmen väljer en variabel som för närvarande är inte tilldelad och tilldelar den antingen "sant" eller "falsk". Detta val skapar två grenar i sökträdet.
* Enhetsutbredning: Efter att ha fattat ett beslut utför DPLL enhetsutbredning. En enhetsklausul är en klausul som bara innehåller en oöverträffad bokstav. Om en enhetsklausul finns (t.ex. `x`) måste algoritmen * * tilldela variabeln` x` till värdet som gör klausulen sant (i detta fall, `x =true '). Enhetsutbredning kan kaskad, vilket leder till ytterligare variabla uppdrag. Detta är avgörande för att förenkla problemet och undvika onödig sökning.
* Ren bokstavlig eliminering: En ren bokstavlig är en bokstavlig som förekommer i endast en polaritet (antingen positiv eller negativ) i hela formeln. Om en ren bokstavlig finns kan den tilldelas ett värde för att göra alla klausuler som innehåller det sant. Detta förenklar formeln utan att påverka tillfredsställelse.
* Backtracking: Om en gren av sökningen leder till en konflikt (dvs. en klausul blir falsk), algoritmen *backtracks *. Detta innebär att ångra det sista beslutet och försöka motsatt uppdrag. Hela processen fortsätter tills antingen en tillfredsställande uppdrag hittas (formeln är SAT) eller alla möjliga uppdrag har uttömts (formeln är osatt).
3. Konfliktdriven klausulinlärning (CDCL):
* Lärande av konflikter: Moderna SAT -lösare är baserade på CDCL, en förlängning av DPLL. Den viktigaste innovationen är att när en konflikt uppstår analyserar lösaren orsakerna till konflikten och lär sig en ny klausul (en konfliktklausul) som förhindrar att samma konflikt inträffar igen i framtiden.
* Konfliktanalys: Processen med konfliktanalys använder implikationsgrafen (en graf som representerar beroenden mellan variabla uppdrag) för att bestämma en delmängd av de beslut som ledde till konflikten.
* Klausulinlärning: Konfliktklausulen läggs till i formeln, vanligtvis med hjälp av schemat "första unika implikationspunkt (UIP)". Den resulterande klausulen är en logisk konsekvens av den ursprungliga formeln, så att lägga till den ändrar inte tillfredsställelsen.
* Icke-kronologisk backtracking (backjumping): CDCL-lösare kan backtracka icke-kronologiskt. Istället för att bara ångra det sista beslutet kan de hoppa tillbaka till en tidigare beslutsnivå som var ansvarig för konflikten. Detta gör att lösaren kan utforska sökutrymmet mer effektivt.
* Klausul Radering: För att förhindra att formeln växer för stor raderar lösare regelbundet några av de lärda klausulerna. Heuristik används för att bestämma vilka klausuler som ska raderas och balansera behovet av att komma ihåg användbar information med behovet av att hålla formeln hanterbar.
4. Variabel beställning av heuristik (förgrening av heuristik):
* Påverkan på effektiviteten: Ordningen i vilken variabler väljs för beslut (förgrening) har en dramatisk inverkan på prestandan hos SAT -lösare. God heuristik kan minska sökträdets storlek avsevärt.
* Vsids (variabelt tillståndsoberoende förfallande summa): En populär heuristik är Vsids. Den upprätthåller en poäng för varje variabel, vilket ökas när variabeln är involverad i en konflikt. Poängen förfallna regelbundet, vilket ger preferens för variabler som nyligen har varit involverade i konflikter. Denna heuristik fokuserar sökningen på de "aktiva" delarna av formeln.
* Annan heuristik: Andra heuristik överväger frekvensen av variabler i klausuler, antalet olösta klausuler som innehåller en variabel eller använder maskininlärningstekniker för att lära sig förgreningstrategier.
5. Klausul Beställning heuristik:
* vägledningsenhetsförökning: Ordningen i vilken klausuler beaktas för enhetsförökning kan också påverka prestanda.
* tittade på bokstäver: De flesta lösare använder en teknik som heter Watched Liters. För varje klausul väljs två bokstäver som "bevakas." Enhetsutbredning behöver endast utlösas när en av de tittade bokstäverna blir falsk. Detta minskar antalet klausuler som måste undersökas väsentligt.
6. Starta om strategier:
* flyktar lokala minima: CDCL -lösare kan ibland fastna i en del av sökutrymmet som är svårt att utforska. Att starta om lösaren med jämna mellanrum kan hjälpa till att undkomma dessa lokala minima.
* glukosbaserad omstart: Moderna lösare använder ofta omstartsstrategier baserat på kvaliteten på de lärda klausulerna. Till exempel startar glukosstartstrategin lösaren oftare när den lär sig många klausuler med låg kvalitet.
7. Förbehandling och inbehandling:
* förenkla formeln: Förbehandlingstekniker tillämpas på formeln * före * den huvudsakliga sökprocessen börjar. Dessa tekniker syftar till att förenkla formeln genom att ta bort redundanta klausuler, ersätta variabler och utföra andra logiska transformationer.
* Inbehandling: Inbehandlingstekniker tillämpas * under * sökprocessen. Dessa tekniker kan dynamiskt förenkla formeln baserat på det aktuella tillståndet för sökningen.
* Exempel: Förbehandling och inbehandling inkluderar underlag (avlägsnande av klausuler som logiskt impliceras av andra klausuler), upplösning (tillägg av nya klausuler till formeln baserad på befintliga klausuler) och variabel eliminering (ersätter en variabel med dess definition).
8. Parallell SAT -lösning:
* divide and conquer: Parallella SAT -lösare utnyttjar parallellen som ligger i sökprocessen. De kan dela sökutrymmet i flera delar och utforska dem samtidigt.
* Portföljmetoder: Ett annat tillvägagångssätt är att köra flera olika SAT -lösare (med olika parameterinställningar) parallellt, och hoppas att en av dem kommer att hitta en lösning snabbt.
* Klausuldelning: Parallella lösare kan dela lärda klausuler mellan olika processer för att förbättra den totala sökeffektiviteten.
9. Teorilösning (SMT):
* Beyond Boolean Logic: SAT -lösare används ofta som en kärnkomponent i SMT -lösare (tillfredsställande moduloteorier (SMT). SMT -lösare kan resonera om formler som innehåller variabler och begränsningar från andra teorier, såsom aritmetik, strängar eller matriser.
* Kombination av sat med teorispecifika lösare: SMT-lösare använder en kombination av SAT-lösningstekniker och teorispecifika lösare för att bestämma formlernas tillfredsställelse.
Sammanfattningsvis, de viktigaste principerna för SAT -lösning, handlar om att effektivt undersöka utrymmet för möjliga variabla uppdrag, lära av konflikter för att undvika att upprepa misstag och förenkla formeln för att minska sökutrymmet. Moderna SAT -lösare är mycket sofistikerade verktyg som kan lösa problem med miljoner variabler och klausuler.
