Učení klauzule založené na konfliktech - Conflict-driven clause learning - Wikipedia

v počítačová věda, učení založené na konfliktech (CDCL) je algoritmus pro řešení Booleovský problém uspokojivosti (SAT). Vzhledem k booleovskému vzorci si problém SAT vyžádá přiřazení proměnných, aby se celý vzorec vyhodnotil jako true. Interní fungování řešičů CDCL SAT bylo inspirováno Řešitelé DPLL.

Konfliktní učení klauzule navrhli Marques-Silva a Sakallah (1996, 1999)^[1]^[2] a Bayardo a Schrag (1997).^[3]

Pozadí

Pro jasnou představu o algoritmu CDCL jsou potřebné základní znalosti o následujících problémech.

Booleovský problém uspokojivosti

Problém uspokojivosti spočívá v nalezení uspokojivého zadání pro daný vzorec v konjunktivní normální forma (CNF).

Příklad takového vzorce je:

( (ne A) nebo (ne C) ) a (B nebo C),

nebo pomocí běžné notace:^[4]

{ displaystyle (A ' lor C') land (B lor C)}

kde A,B,C jsou booleovské proměnné, ${ displaystyle A '}$ , ${ displaystyle C '}$ , ${ displaystyle B}$ , a ${ displaystyle C}$ jsou literály a ${ displaystyle A ' lor C'}$ a ${ displaystyle B lor C}$ jsou klauze.

Uspokojivým úkolem pro tento vzorec je např .:

{ displaystyle A = False, B = False, C = True}

protože dělá první klauzuli pravdivou (od ${ displaystyle A '}$ je pravda), stejně jako druhý (od ${ displaystyle C}$ je pravda).

Tento příklad používá tři proměnné (A, B, C) a pro každé z nich existují dvě možná přiřazení (True a False). Takže jeden má ${ displaystyle 2 ^ {3} = 8}$ možnosti. V tomto malém příkladu lze použít vyhledávání hrubou silou vyzkoušet všechna možná přiřazení a zkontrolovat, zda splňují vzorec. Ale v realistických aplikacích s miliony proměnných a klauzí je vyhledávání hrubou silou nepraktické. Odpovědností řešitele SAT je najít uspokojivé zadání efektivně a rychle použitím různých heuristik pro složité vzorce CNF.

Pravidlo klauzule jednotky (šíření jednotky)

Pokud má neuspokojená klauzule všechny své literály nebo proměnné kromě jedné hodnocené na False, pak musí být volný literál True, aby klauzule byla True. Například pokud je níže neuspokojená klauzule vyhodnocena pomocí ${ displaystyle A = False}$ a ${ displaystyle B = False}$ musíme ${ displaystyle C = True}$ za účelem doložky ${ displaystyle (A lor B lor C)}$ být pravdivý.

Šíření logických omezení (BCP)

Iterovaná aplikace pravidla klauzule jednotky se označuje jako šíření jednotek nebo šíření booleovských omezení (BCP).

Rozlišení

Zvažte dvě věty ${ displaystyle (A lor B lor C)}$ a ${ displaystyle ( neg C lor D lor neg E)}$ Doložka ${ displaystyle (A lor B lor D lor neg E)}$ , získané sloučením dvou klauzulí a odstraněním obou ${ displaystyle neg C}$ a ${ displaystyle C}$ , se nazývá řešení dvou klauzulí.

Algoritmus DP

Algoritmus DP zavedli Davis a Putnam v roce 1960. Algoritmus neformálně iterativně provádí následující kroky, dokud ve vzorci nezůstanou žádné další proměnné:

Vyberte proměnnou ${ displaystyle A}$ a přidejte všechna tautologická řešení ${ displaystyle A}$ (rezoluce není tautologická, pokud neobsahuje ${ displaystyle V}$ a ${ displaystyle neg V}$ pro nějakou proměnnou ${ displaystyle V}$ ).
Odeberte všechny původní klauzule, které obsahují ${ displaystyle A}$ .

Algoritmus DPLL

Tento algoritmus vyvinuli Davis, Putnam, Logemann, Loveland (1962). Některé vlastnosti tohoto algoritmu jsou:

Je založen na vyhledávání.
Je základem pro téměř všechny moderní SAT řešení.
Využívá chronologické zpětné sledování bez učení.

Příklad s vizualizací algoritmu DPLL s chronologickým zpětným sledováním:

Všechny klauzule tvořící vzorec CNF
Vyberte proměnnou
Rozhodněte se, proměnná a = False (0), zelené klauze se tak stanou True
Po několika rozhodnutích jsme našli implikační graf který vede ke konfliktu.
Nyní se vraťte zpět na okamžitou úroveň a silou přiřaďte této proměnné opačnou hodnotu
Ale vynucené rozhodnutí stále vede k dalšímu konfliktu
Vraťte se zpět na předchozí úroveň a proveďte vynucené rozhodnutí
Udělejte nové rozhodnutí, ale vede to ke konfliktu
Udělejte vynucené rozhodnutí, ale opět to vede ke konfliktu
Zpět na předchozí úroveň
Pokračujte tímto způsobem a konečný implikační graf

CDCL (konfliktní učení klauzule)

Hlavní rozdíl mezi CDCL a DPLL spočívá v tom, že zpětný skok CDCL není chronologický.

Konfliktní učení klauzule funguje následovně.

Vyberte proměnnou a přiřaďte True nebo False. Toto se nazývá rozhodovací stav. Pamatujte na zadání.
Použít šíření booleovských omezení (šíření jednotek).
Sestavte implikační graf.
Pokud dojde ke konfliktu
1. Najděte řez v implikačním grafu, který vedl ke konfliktu
2. Odvozte novou klauzuli, která je negací úkolů, které vedly ke konfliktu
3. Non-chronologicky backtrack ("back jump") na příslušnou rozhodovací úroveň, kde byla přiřazena první přiřazená proměnná zapojená do konfliktu
Jinak pokračujte od kroku 1, dokud nejsou přiřazeny všechny hodnoty proměnných.

Příklad

Vizuální příklad algoritmu CDCL:

Nejprve vyberte větvenou proměnnou, jmenovitě x1. Žlutý kruh znamená svévolné rozhodnutí.
Nyní použijte šíření jednotek, které to vede x4 musí být 1 (tj. True). Šedý kruh znamená vynucené přiřazení proměnné během šíření jednotky. Výsledný graf se nazývá implikační graf.
Libovolně vybrat jinou proměnnou větvení, x3.
Použijte šíření jednotek a najděte nový implikační graf.
Zde proměnná x8 a x12 jsou nuceni být 0, respektive 1.
Vyberte jinou proměnnou větvení, x2.
Najděte implikační graf.
Vyberte jinou proměnnou větvení, x7.
Najděte implikační graf.
Nalezen konflikt!
Najděte řez, který vedl k tomuto konfliktu. Z řezu najděte konfliktní podmínku.
Vezměte negaci této podmínky a udělejte z ní klauzuli.
Přidejte k problému kolizní klauzuli.
Nechronologický zpětný skok na příslušnou rozhodovací úroveň, což je v tomto případě druhá nejvyšší rozhodovací úroveň literálů v naučené klauzi.
Skok zpět a odpovídajícím způsobem nastavte hodnoty proměnných.

Úplnost

DPLL je zdravý a kompletní algoritmus pro SAT. Řešitelé CDCL SAT implementují DPLL, ale mohou se naučit nové klauze a zpětně sledovat chronologicky. Doložka učení s analýzou konfliktu nemá vliv na spolehlivost ani úplnost. Analýza konfliktů identifikuje nové klauzule pomocí operace řešení. Proto lze každou naučenou klauzuli odvodit z původních klauzulí a dalších naučených klauzulí posloupností kroků řešení. Pokud cN je nová naučená klauzule, pak ϕ je uspokojivé právě tehdy, když ϕ ∪ {cN} je také uspokojivé. Kromě toho upravený krok zpětného sledování také nemá vliv na spolehlivost nebo úplnost, protože informace o zpětném sledování jsou získány z každé nové naučené klauzule.^[5]

Aplikace

Hlavní aplikace algoritmu CDCL je v různých řešitelích SAT, včetně:

MiniSAT
Zchaff SAT
Z3
Glukóza^[6]
ManySAT atd.

Algoritmus CDCL učinil SAT solvers tak silnými, že jsou efektivně využívány v několika aplikačních oblastech reálného světa, jako je plánování AI, bioinformatika, generování testovacích vzorů softwaru, závislosti softwarových balíků, kontrola hardwarových a softwarových modelů a kryptografie.

Související algoritmy

Související algoritmy s CDCL jsou algoritmy DP a DPLL popsané výše. Algoritmus DP používá vyvrácení rozlišení a má potenciální problém s přístupem do paměti. Zatímco algoritmus DPLL je v pořádku pro náhodně generované instance, je špatný pro instance generované v praktických aplikacích. CDCL je výkonnější přístup k řešení těchto problémů v tom, že použití CDCL poskytuje méně hledání stavového prostoru ve srovnání s DPLL.

DPLL: žádné učení a chronologické zpětné sledování.
CDCL: konfliktní učení klauzule a nechronologické zpětné sledování.

Citované práce

^ J.P. Marques-Silva; Karem A. Sakallah (listopad 1996). "GRASP-Nový vyhledávací algoritmus pro uspokojivost". Shrnutí mezinárodní konference IEEE o navrhování podporovaném počítačem (ICCAD). str. 220–227. CiteSeerX 10.1.1.49.2075. doi:10.1109 / ICCAD.1996.569607. ISBN 978-0-8186-7597-3.
^ J.P. Marques-Silva; Karem A. Sakallah (květen 1999). „GRASP: Algoritmus vyhledávání pro výrokovou uspokojivost“ (PDF). Transakce IEEE na počítačích. 48 (5): 506–521. doi:10.1109/12.769433.
^ Roberto J. Bayardo ml .; Robert C. Schrag (1997). „Použití technik zpětného pohledu CSP k řešení skutečných případů SAT SAT“ (PDF). Proc. 14. nat. Konf. o umělé inteligenci (AAAI). 203–208.
^ Na obrázcích níže „ ${ displaystyle +}$ "se používá k označení" nebo "a násobení k označení" a ".
^ Biere, Heule, Van Maaren, Walsh (únor 2009). Příručka uspokojivosti (PDF). IOS Press. str. 138. ISBN 978-1-60750-376-7.CS1 maint: více jmen: seznam autorů (odkaz)
^ https://www.labri.fr/perso/lsimon/glucose/

Reference

Martin Davis; Hilary Putnam (1960). "Postup výpočtu pro teorii kvantifikace". J. ACM. 7 (3): 201–215. doi:10.1145/321033.321034.
Martin Davis; George Logemann; Donald Loveland (červenec 1962). "Strojový program pro dokazování vět". Komunikace ACM. 5 (7): 394–397. doi:10.1145/368273.368557. hdl:2027 / mdp. 39015095248095.
Matthew W. Moskewicz; Conor F. Madigan; Ying Zhao; Lintao Zhang; Sharad Malik (2001). "Pleva: inženýrství efektivního SAT řešiče" (PDF). Proc. 38. Ann. Konference automatizace designu (DAC). str. 530–535.
Lintao Zhang; Conor F. Madigan; Matthew H. Moskewicz; Sharad Malik (2001). „Efektivní konfliktní učení v boolovském řešení uspokojivosti“ (PDF). Proc. IEEE / ACM Int. Konf. o počítačem podporovaném designu (ICCAD). 279–285.
Prezentace - „SAT-Solving: From Davis-Putnam to Zchaff and Beyond“ od Lintaa Zhanga. (Několik obrázků je převzato z jeho prezentace)

[1] J.P. Marques-Silva; Karem A. Sakallah (listopad 1996). "GRASP-Nový vyhledávací algoritmus pro uspokojivost". Shrnutí mezinárodní konference IEEE o navrhování podporovaném počítačem (ICCAD). str. 220–227. CiteSeerX 10.1.1.49.2075. doi:10.1109 / ICCAD.1996.569607. ISBN 978-0-8186-7597-3.

[2] J.P. Marques-Silva; Karem A. Sakallah (květen 1999). „GRASP: Algoritmus vyhledávání pro výrokovou uspokojivost“ (PDF). Transakce IEEE na počítačích. 48 (5): 506–521. doi:10.1109/12.769433.

[3] Roberto J. Bayardo ml .; Robert C. Schrag (1997). „Použití technik zpětného pohledu CSP k řešení skutečných případů SAT SAT“ (PDF). Proc. 14. nat. Konf. o umělé inteligenci (AAAI). 203–208.

[4] Na obrázcích níže „ ${ displaystyle +}$ "se používá k označení" nebo "a násobení k označení" a ".

[5] Biere, Heule, Van Maaren, Walsh (únor 2009). Příručka uspokojivosti (PDF). IOS Press. str. 138. ISBN 978-1-60750-376-7.CS1 maint: více jmen: seznam autorů (odkaz)

[6] ttps://www.labri.fr/perso/lsimon/glucose/

[1]

[2]

[3]

[4]

[5]

[6]