16. CDCL algoritam. Analiza konflikata, nehronološko vraćanje, učenje, zaboravljanje, restart, heuristike.

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/16

encourage image

There's no tags or description

Looks like no tags are added yet.

17 Terms

1
New cards

Zašto obično hronološko vraćanje može biti neefikasno?

Poslednja odluka možda nije uzrok konflikta, pa se uzalud pretražuju grane.

2
New cards

Šta je cilj analize konflikta?

Pronaći dublji uzrok konflikta i izvesti klauzu koja sprečava njegovo ponavljanje.

3
New cards

Na kom pravilu se zasniva analiza konflikata?

Na rezoluciji, kojom se izvode nove klauze iz postojećih.

4
New cards

Šta je nehronološko vraćanje (backjumping)?

Skok na odgovarajući raniji nivo odlučivanja, uz preskakanje nebitnih nivoa.

5
New cards

Šta je naučena klauza?

Logička posledica formule dobijena analizom konflikta i dodata skupu klauza.

6
New cards

Zašto učenje klauza čuva zadovoljivost?

Dodaju se samo klauze koje su logičke posledice postojeće formule.

7
New cards

Šta predstavlja C u stanju (M,C)?

Tekuću konfliktnu klauzu ili oznaku da trenutno nema konflikta.

8
New cards

Šta radi pravilo Conflict?

Kada je neka klauza netačna u M, postavlja je kao konfliktnu C.

9
New cards

Šta radi pravilo Explain?

Rezolucijom zamenjuje razlog propagiranog literala u konfliktnoj klauzi.

10
New cards

Šta radi pravilo Backjump?

Vraća trag na raniji nivo i propagira literal iz klauze povratnog skoka.

11
New cards

Šta radi pravilo Learn?

Dodaje izvedenu klauzu u F; najčešće se uče klauze povratnog skoka.

12
New cards

Šta radi heuristika VSIDS?

Povećava skor atoma iz skorijih konflikata i periodično umanjuje sve skorove.

13
New cards

Šta znači Saved polarity?

Za promenljivu se bira polaritet koji je imala pri prethodnom dodeljivanju.

14
New cards

Zašto CDCL zaboravlja neke naučene klauze?

Previše naučenih klauza usporava nalaženje jediničnih i konfliktnih klauza.

15
New cards

Zašto CDCL povremeno ponovo pokreće pretragu?

Naučene klauze mogu usmeriti novu pretragu u lakši deo prostora.

16
New cards

Kako se može proveriti CDCL odgovor UNSAT?

Nezavisnim proveravačem rezolucijskog sertifikata nezadovoljivosti.

17
New cards

Mini zadatak: šta izvodi rezolucija {¬p,q} i {¬q}?

Klauzu {¬p}; ona može biti naučena i sprečiti ponavljanje konflikta.