Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
1. Predstavuje problémy ako booleovské vzorce:
* kódovanie: Základná myšlienka používania SAT riešiteľov je kódovanie Daný problém (napr. Plánovanie, návrh obvodu, plánovanie) do booleovského vzorca v spojivej normálnej forme (CNF). Zahŕňa to identifikáciu rozhodovacích premenných problému a predstavovanie obmedzení týchto premenných ako logických doložiek. Krása spočíva v tom, že v tomto formáte je možné vyjadriť širokú škálu problémov.
* spojivá normálna forma (CNF): Takmer všetci riešitelia SAT pracujú na vzorcoch v CNF. CNF je logický vzorec, ktorý je spojením (a) klauzúl, kde každá klauzula je disjunkciou (alebo) literálov. Doslovník je buď premenná, alebo jej negácia. Napríklad:`(x alebo nie y alebo z) a (nie x alebo y)`. Byť v CNF robí proces vyhľadávania štruktúrovanejší a efektívnejší.
2. Algoritmus Davis-Putnam-Logemann-Loveland (DPLL):
* Prihliadač: DPLL je základný algoritmus na riešenie problémov SAT. Je to kompletný algoritmus vyhľadávania, ktorý systematicky skúma priestor možných priradení premenných.
* Rozhodnutie: Algoritmus vyberie premennú, ktorá je v súčasnosti nepriradená, a priraďuje ju buď „true“ alebo `false`. Táto voľba vytvára dve vetvy v strome vyhľadávania.
* Dopracia jednotky: Po rozhodnutí DPLL vykonáva šírenie jednotky. Klauzula jednotky je klauzula, ktorá obsahuje iba jeden nepriradený doslovný. Ak existuje klauzula jednotky (napr. „X`), algoritmus * musí * priradiť premennú` x` k hodnote, ktorá robí klauzulu pravdivou (v tomto prípade `x =true`). Propagácia jednotiek môže kaskádovať, čo vedie k ďalším premenným. To je rozhodujúce pre zjednodušenie problému a zabránenie zbytočným vyhľadávaním.
* čisté doslovné eliminácia: Čistý literál je doslovný, ktorý sa objavuje iba v jednej polarite (pozitívnej alebo negatívnej) v celom vzorci. Ak existuje čistý doslovný literál, je možné priradiť hodnotu, aby sa všetky klauzuly obsahovali pravdivé. Zjednodušuje to vzorec bez ovplyvnenia uspokojivosti.
* backtracking: Ak vetva vyhľadávania vedie ku konfliktu (t. J. Klauzula sa stane nepravdivou), algoritmus *spätne *. To znamená zrušenie posledného rozhodnutia a vyskúšať opačné zadanie. Celý proces pokračuje, až kým sa nenájde buď uspokojivé priradenie (vzorec je SAT) alebo všetky možné priradenia boli vyčerpané (vzorec sa nespája).
3. Učenie klauzuly založeného na konfliktoch (CDCL):
* učenie sa z konfliktov: Moderní SAT Solvers sú založené na CDCL, rozšírení DPLL. Kľúčovou inováciou je, že keď sa vyskytne konflikt, riešiteľ analyzuje dôvody konfliktu a naučí sa novú doložku (doložka o konflikte), ktorá bráni tomu istému konfliktu v budúcnosti znova.
* Analýza konfliktov: Proces analýzy konfliktov používa implikáciu grafu (graf predstavujúci závislosti medzi premennými priradeniami) na určenie podmnožiny rozhodnutí, ktoré viedli ku konfliktu.
* učenie sa: Klauzula o konflikte sa pridá do vzorca, zvyčajne s použitím schémy „First Unique Implication Point (UIP)“. Výsledná klauzula je logickým dôsledkom pôvodného vzorec, takže pridanie jej nemení uspokojivosť.
* NECHRONOLOGICKÉ ZAKNATEĽA (Backjumping): Riešitelia CDCL môžu nekronologicky spätne. Namiesto toho, aby len zrušili posledné rozhodnutie, môžu skočiť späť na predchádzajúcu úroveň rozhodnutia, ktorá bola zodpovedná za konflikt. To umožňuje riešiteľovi efektívnejšie skúmať vyhľadávací priestor.
* klauzula vymazanie: Aby sa zabránilo príliš veľkému rastu receptúry, riešitelia pravidelne odstraňujú niektoré z naučených klauzúl. Heuristiky sa používajú na rozhodnutie, ktoré doložky sa majú vymazať, čím sa vyvažuje potreba zapamätať si užitočné informácie s potrebou udržať vzorec zvládnuteľný.
4. Variabilné usporiadanie heuristiky (vetvenie heuristiky):
* Vplyv na efektívnosť: Poradie, v ktorom sú premenné vybrané na rozhodnutie (vetvenie), má dramatický vplyv na výkonnosť riešiteľov SAT. Dobrá heuristika môže výrazne znížiť veľkosť stromu vyhľadávania.
* VSIDS (Variabilný stav nezávislého rozpadu): Populárnou heuristikou sú VSIDS. Udržiava skóre pre každú premennú, ktorá sa zvyšuje vždy, keď je premenná zapojená do konfliktu. Skóre sa pravidelne rozkladajú, pričom uprednostňujú premenné, ktoré sa nedávno zapojili do konfliktov. Táto heuristika zameriava hľadanie na „aktívne“ časti vzorca.
* Ostatné heuristiky: Iné heuristiky zvažujú frekvenciu premenných v klauzulách, počet nevyriešených klauzúl obsahujúcich premennú, alebo používajú techniky strojového učenia na učenie stratégií vetvenia.
5. Klauzula nariadenie heuristiky:
* šírenie jednotky: Poradie, v ktorom sa doložky uvažujú o šírení jednotky, môže tiež ovplyvniť výkon.
* Sledované literály: Väčšina riešiteľov používa techniku nazývanú sledované literály. Pre každú klauzulu sú dva literály vybrané ako „sledované“. Šírenie jednotky je potrebné spustiť iba vtedy, keď sa stane nepravdivým jedným z sledovaných literálov. To výrazne znižuje počet klauzúl, ktoré je potrebné preskúmať.
6. Stratégie reštartu:
* Uniknutie miestnych minima: Riešitelia CDCL sa niekedy môžu zaseknúť v časti vyhľadávacieho priestoru, ktorý je ťažké preskúmať. Pravidelné reštartovanie riešiteľa môže pomôcť uniknúť z týchto miestnych minima.
* Restart na báze glukózy: Moderní riešitelia často používajú stratégie reštartu založené na kvalite učencových klauzúl. Napríklad stratégia spustenia glukózy reštartuje riešiteľ častejšie, keď sa učí mnoho klauzúl na nízku kvalitu.
7. Predbežné spracovanie a spracovanie:
* Zjednodušenie vzorca: Techniky predbežného spracovania sa používajú na vzorec * skôr, ako sa začína hlavný proces vyhľadávania. Cieľom týchto techník je zjednodušiť vzorec odstránením redundantných klauzúl, nahradením premenných a vykonaním ďalších logických transformácií.
* Inprocesing: Počas * procesu vyhľadávania sa používajú techniky spracovania *. Tieto techniky môžu dynamicky zjednodušiť vzorec na základe aktuálneho stavu vyhľadávania.
* Príklady: Predbežné spracovanie a spracovanie zahŕňajú podskupovanie (odstránenie klauzúl, ktoré sú logicky implikované inými klauzulami), rozlíšenie (pridanie nových klauzulov do vzorca na základe existujúcich klauzúl) a variabilnú elimináciu (nahradenie premennej jej definíciou).
8. Riešenie paralelného SAT:
* Rozdeľte a dobyť: Paralelné SAT Solvers využívajú paralelizmus spojený s procesom vyhľadávania. Môžu rozdeliť vyhľadávací priestor na viac častí a sú súčasne preskúmať.
* Portfólio sa blíži: Ďalším prístupom je paralelne spustenie viacerých rôznych riešiteľov SAT (s rôznymi nastaveniami parametrov) a dúfať, že jeden z nich rýchlo nájde riešenie.
* Zdieľanie klauzuly: Paralelní riešitelia môžu zdieľať učenané klauzuly medzi rôznymi procesmi, aby sa zlepšila celková efektívnosť vyhľadávania.
9. Riešenie teórie (SMT):
* Beyond Boolean Logic: Riešitelia SAT sa často používajú ako základná súčasť riešiteľov spokojnosti modulových modulov (SMT). Riešitelia SMT môžu uvažovať o vzorcoch, ktoré obsahujú premenné a obmedzenia z iných teórií, ako sú aritmetika, reťazce alebo polia.
* Kombinácia SAT s riešiteľmi špecifickými pre teóriu: Riešitelia SMT používajú na určenie uspokojivosti vzorcov kombináciu techník riešenia SAT a riešiteľov špecifických pre teóriu.
V súhrne sa kľúčové princípy SAT riešia, ktoré sa točia okolo efektívneho skúmania priestoru možných premenných priradení, učia sa z konfliktov, aby sa predišlo opakovaným chybám a zjednodušili vzorec, aby sa znížil vyhľadávací priestor. Moderní SAT riešitelia sú vysoko sofistikované nástroje, ktoré dokážu vyriešiť problémy s miliónmi premenných a klauzúl.