1/16
Looks like no tags are added yet.
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.
Šta je cilj analize konflikta?
Pronaći dublji uzrok konflikta i izvesti klauzu koja sprečava njegovo ponavljanje.
Na kom pravilu se zasniva analiza konflikata?
Na rezoluciji, kojom se izvode nove klauze iz postojećih.
Šta je nehronološko vraćanje (backjumping)?
Skok na odgovarajući raniji nivo odlučivanja, uz preskakanje nebitnih nivoa.
Šta je naučena klauza?
Logička posledica formule dobijena analizom konflikta i dodata skupu klauza.
Zašto učenje klauza čuva zadovoljivost?
Dodaju se samo klauze koje su logičke posledice postojeće formule.
Šta predstavlja C u stanju (M,C)?
Tekuću konfliktnu klauzu ili oznaku da trenutno nema konflikta.
Šta radi pravilo Conflict?
Kada je neka klauza netačna u M, postavlja je kao konfliktnu C.
Šta radi pravilo Explain?
Rezolucijom zamenjuje razlog propagiranog literala u konfliktnoj klauzi.
Šta radi pravilo Backjump?
Vraća trag na raniji nivo i propagira literal iz klauze povratnog skoka.
Šta radi pravilo Learn?
Dodaje izvedenu klauzu u F; najčešće se uče klauze povratnog skoka.
Šta radi heuristika VSIDS?
Povećava skor atoma iz skorijih konflikata i periodično umanjuje sve skorove.
Šta znači Saved polarity?
Za promenljivu se bira polaritet koji je imala pri prethodnom dodeljivanju.
Zašto CDCL zaboravlja neke naučene klauze?
Previše naučenih klauza usporava nalaženje jediničnih i konfliktnih klauza.
Zašto CDCL povremeno ponovo pokreće pretragu?
Naučene klauze mogu usmeriti novu pretragu u lakši deo prostora.
Kako se može proveriti CDCL odgovor UNSAT?
Nezavisnim proveravačem rezolucijskog sertifikata nezadovoljivosti.
Mini zadatak: šta izvodi rezolucija {¬p,q} i {¬q}?
Klauzu {¬p}; ona može biti naučena i sprečiti ponavljanje konflikta.