SAT (boolsk tilfredshed) er et grundlæggende problem inden for datalogi, og dens undersøgelse har ført til udviklingen af ​​centrale principper og teknikker, der stort set er anvendelige. Her er en oversigt over de vigtigste principper:

1. Repræsenterer problemer som boolske formler:

* kodning: Kerneideen om at bruge SAT Solvers er at kode Et givet problem (f.eks. Planlægning, kredsløbsdesign, planlægning) til en boolsk formel i konjunktiv normal form (CNF). Dette involverer at identificere beslutningsvariablerne i problemet og repræsentere begrænsningerne for disse variabler som logiske klausuler. Skønheden ligger i det faktum, at en lang række problemer kan udtrykkes i dette format.

* konjunktiv normal form (CNF): Næsten alle SAT -solvere fungerer på formler i CNF. CNF er en logisk formel, der er en konjunktion (og) af klausuler, hvor hver klausul er en disjunktion (eller) af bogstaver. En bogstavelig er enten en variabel eller dens negation. For eksempel:`(x eller ikke y eller z) og (ikke x eller y)`. At være i CNF gør søgeprocessen mere struktureret og effektiv.

2. Davis-Putnam-Logemann-Loveland (DPLL) algoritme:

* søgebaseret tilgang: DPLL er den grundlæggende algoritme til løsning af SAT -problemer. Det er en komplet søgealgoritme, der systematisk undersøger rummet for mulige variable opgaver.

* Beslutning: Algoritmen vælger en variabel, der i øjeblikket ikke er tildelt og tildeler den enten "sand" eller "falsk". Dette valg skaber to grene i søgningstræet.

* Enhedsudbredelse: Efter at have truffet en beslutning udfører DPLL enhedsudbredelse. En enhedsklausul er en klausul, der kun indeholder en ikke -tildelt bogstavelig. Hvis der findes en enhedsklausul (f.eks. `X`), skal algoritmen * tildele variablen` x` til den værdi, der gør klausulen sand (i dette tilfælde `x =sandt`). Enhedsudbredelse kan kaskade, hvilket fører til yderligere variable opgaver. Dette er afgørende for at forenkle problemet og undgå unødvendig søgning.

* ren bogstavelig eliminering: En ren bogstavelig er en bogstavelig, der kun vises i en polaritet (enten positiv eller negativ) i hele formlen. Hvis der findes en ren bogstavelig, kan det tildeles en værdi for at gøre alle klausuler, der indeholder den sandt. Dette forenkler formlen uden at påvirke tilfredshed.

* backtracking: Hvis en gren af ​​søgningen fører til en konflikt (dvs. en klausul bliver falsk), bliver algoritmen *backtracks *. Dette betyder at fortryde den sidste beslutning og prøve den modsatte opgave. Hele processen fortsætter, indtil enten en tilfredsstillende opgave findes (formlen er SAT), eller alle mulige opgaver er opbrugt (formlen er UNSAT).

3. Konfliktdrevet klausul Learning (CDCL):

* Læring fra konflikter: Moderne SAT -solvers er baseret på CDCL, en udvidelse af DPLL. Den vigtigste innovation er, at når en konflikt opstår, analyserer solveren grundene til konflikten og lærer en ny klausul (en konfliktklausul), der forhindrer den samme konflikt i at opstå igen i fremtiden.

* Konfliktanalyse: Processen med konfliktanalyse bruger implikationsgrafen (en graf, der repræsenterer afhængighederne mellem variable opgaver) til at bestemme en undergruppe af de beslutninger, der førte til konflikten.

* Klausul Læring: Konfliktklausulen føjes til formlen, typisk ved hjælp af ordningen "First Unique Implication Point (UIP)". Den resulterende klausul er en logisk konsekvens af den originale formel, så at tilføje den ændrer ikke tilfredshed.

* ikke-krybronologisk backtracking (backjumping): CDCL-solvere kan ikke-krybne backtrack. I stedet for bare at fortryde den sidste beslutning, kan de hoppe tilbage til et tidligere beslutningsniveau, der var ansvarlig for konflikten. Dette gør det muligt for solver at udforske søgerummet mere effektivt.

* Sletning af klausul: For at forhindre, at formlen vokser for store, slettes opløsere med jævne mellemrum nogle af de lærte klausuler. Heuristik bruges til at beslutte, hvilke klausuler de skal slette, og afbalancere behovet for at huske nyttige oplysninger med behovet for at holde formlen håndterbar.

4. Variabel bestilling af heuristik (forgreningsheuristik):

* indflydelse på effektivitet: Den rækkefølge, i hvilken variabler er valgt til beslutning (forgrening), har en dramatisk indflydelse på ydelsen af ​​SAT -solvers. God heuristik kan reducere søgningstræet markant.

* VSIDS (variabel tilstand uafhængig forfaldne sum): En populær heuristik er VSID'er. Den opretholder en score for hver variabel, der øges, når variablen er involveret i en konflikt. Resultaterne forfaldes med jævne mellemrum, hvilket giver variabler, der for nylig er involveret i konflikter. Denne heuristik fokuserer søgningen på de "aktive" dele af formlen.

* Andet heuristik: Andre heuristikker overvejer hyppigheden af ​​variabler i klausuler, antallet af uløste klausuler, der indeholder en variabel, eller bruger maskinlæringsteknikker til at lære forgreningsstrategier.

5. Klausulbestilling af heuristik:

* Vejledende enhedsudbredelse: Den rækkefølge, i hvilken klausuler overvejes til enhedsudbredelse, kan også påvirke ydeevnen.

* så bogstaver: De fleste solvere bruger en teknik kaldet Seted Literals. For hver klausul vælges to bogstaver som "set". Enhedsudbredelse skal kun udløses, når en af ​​de overvågede bogstaver bliver falsk. Dette reducerer antallet af klausuler markant, der skal undersøges.

6. Genstart strategier:

* undslipper lokale minima: CDCL -solvere kan undertiden sidde fast i en del af søgerummet, som det er vanskeligt at udforske. Genstart af solveren med jævne mellemrum kan hjælpe med at undslippe disse lokale minima.

* glukosebaseret genstart: Moderne solvere bruger ofte genstartstrategier baseret på kvaliteten af ​​de lærde klausuler. For eksempel genstarter glukose-genstartstrategien solveren hyppigere, når den lærer mange klausuler af lav kvalitet.

7. Forarbejdning og inprocessering:

* Forenkling af formlen: Forarbejdningsteknikker anvendes på formlen * før * den vigtigste søgeproces begynder. Disse teknikker sigter mod at forenkle formlen ved at fjerne overflødige klausuler, erstatte variabler og udføre andre logiske transformationer.

* Informering: Inprocesseringsteknikker anvendes * under * søgeprocessen. Disse teknikker kan dynamisk forenkle formlen baseret på den aktuelle tilstand af søgningen.

* Eksempler: Forarbejdning og inprocesser inkluderer subsumption (fjernelse af klausuler, der logisk er underforstået af andre klausuler), opløsning (tilføjelse af nye klausuler til formlen baseret på eksisterende klausuler) og variabel eliminering (erstatning for en variabel med dens definition).

8. Parallel Sat Solving:

* Opdel og erobrer: Parallelle SAT -solvers udnytter parallelismen, der er forbundet med søgeprocessen. De kan opdele søgerummet i flere dele og udforske dem samtidigt.

* portefølje nærmer sig: En anden tilgang er at køre flere forskellige SAT -solvers (med forskellige parameterindstillinger) parallelt og håber, at en af ​​dem hurtigt finder en løsning.

* Deling af klausul: Parallelle solvere kan dele lærte klausuler mellem forskellige processer for at forbedre den samlede søgeeffektivitet.

9. Teori Solving (SMT):

* ud over boolsk logik: SAT -solvere bruges ofte som en kernekomponent i tilfredshedsmodulteorier (SMT) solvers. SMT -solvere kan resonnere om formler, der indeholder variabler og begrænsninger fra andre teorier, såsom aritmetik, strenge eller arrays.

* Kombination af SAT med teorispecifikke solvers: SMT-solvers bruger en kombination af SAT-løsningsteknikker og teorispecifikke solvers til at bestemme tilfredshed af formler.

I resumé drejer de vigtigste principper for SAT -løsning om effektivt at undersøge rummet for mulige variable opgaver, lære fra konflikter for at undgå at gentage fejl og forenkle formlen for at reducere søgerummet. Moderne SAT -solvere er meget sofistikerede værktøjer, der kan løse problemer med millioner af variabler og klausuler.