Úvod do programování s omezujícími podmínkami (pokračování) Polynomiální a NP-úplné problémy m Polynomiální problémy existuje algoritmus polynomiální složitosti pro řešení problému NP-úplné problémy 3 řešitelné nedeterministickým polynomiálním algoritmem 3 potenciální řešení lze ověřit v polynomiálním čase 3 v nejhorším případě exponenciální složitost (pokud neplatí P=NP) Hana Rudová, Omezující podmínky, 23. září 201 9 2 Úvod do CP Složitost: polynomiální problémy Lineární rovnice nad reálnými čísly S proměnné nad doménami z R, omezení: lineární rovnice M Gaussova eliminace polynomiální složitost I Lineární nerovnice nad reálnými čísly 3 lineární programování, simplexová metoda často stačí polynomiální složitost Hana Rudová, Omezující podmínky, 23. září 201 9 3 Úvod do CP Složitost: NP-úplné problémy Boolean omezení 0/1 proměnné omezení = Boolean formule (konjunkce, disjunkce, implikace, ...) ±> příklad: proměnné A,B, C, omezení (A v B), (C => A), CSP problém (A v B) a (C => A) I M problém splnitelnosti Boolean formule (SAT problém): NP-úplný n proměnných:l2n možností I Omezení nad konečnými doménami obecný CSP problém 3 problém splnitelnosti nad obecnými relacemi 3 NP-úplný problém 3 n proměnných, d maximální velikost domény:ldn možností Hana Rudová, Omezující podmínky, 23. září 201 9 4 Úvod do CP Složitost a úplnost 3 Úplné vs. neúplné algoritmy 3 úplný algoritmus prozkoumává množinu všech řešení neúplný algoritmus: neprozkoumává celou množinu řešení 3 nevím jako možná odpověď, ziskem může být efektivita M příklad: neúplný polynomiální algoritmus pro NP-úplný problém I m Složitost řešiče I Gaussova eliminace (P), SAT řešiče (NP), obecný CSP řešič (NP) Složitost algoritmů propagace omezení většinou polynomiální neúplné algoritmy I 3 Složitost prohledávacích algoritmů 3 úplné algoritmy, příklady: backtracking, generuj & testuj 3 neúplné algoritmy, neprohledávají celý prostor řešení, příklad: omezení času prohledávání Hana Rudová, Omezující podmínky, 23. září 2019 5 Úvod do CP Grafová reprezentace CSP Reprezentace podmínek 3 intenzionální (matematická/logická formule) M extenzionální (výčet k-tic kompatibilních hodnot, 0-1 matice) I 3 Graf: vrcholy, hrany (hrana spojuje dva vrcholy) 3 Hypergraf: vrcholy, hrany (hrana spojuje množinu vrcholů) Reprezentace CSP pomocí hypergrafu podmínek I 3 vrchol = proměnná, hyperhrana = podmínka I Binární CSP Binární CSP CSP, ve kterém jsou pouze binární podmínky 3 unární podmínky zakódovány do domény proměnné Graf podmínek pro binární CSP 3 není nutné uvažovat hypergraf, stačí graf (podmínka spojuje pouze dva vrcholy) I CSP lze transformovat na binární CSP Ekvivalence CSP dva CSP problémy jsou ekvivalentní, pokud mají stejnou množinu řešení Rozšířená ekvivalence CSP 3 řešení problémů lze mezi sebou „syntakticky" převést 3 např: obecný CSP převedeme na binární CSP a porovnáme tyto binární CSP Hana Rudová, Omezující podmínky, 23. září 2019 7 Úvod do CP Duální problém Duální problém: původním omezením odpovídají nové duální proměnné proměnné: fc-ární podmínku q převedeme na duální proměnnou Ví s doménou obsahující konzistentní fc-tice ^ omezení: pro každou dvojici podmínek q a Cj sdílející proměnné zavedeme binární podmínku Ríj mezi Ví a Vj omezující duální proměnné na fc-tice, ve kterých mají sdílené proměnné stejnou hodnotu Příklad proměnné X\,... ,Xq s doménou {0,1} omezení c\ : X\ + x2 + Xq = 1... v\ c2 : X\ - X3 + x4 = 1... V2 C3 : x4 + X5 - Xq > 0... V3 C4 : X2 + Xs - Xq = 0 . . . V4 (0,0,1), (0,1,0), R21 & R33 (1,0,0) R11 ^SS\SR33 (0,0,1), (1,0,0), (1,1,1) R31 (0,0,0), (0,1,1), (1,0,1) R22 & R33 (0,1,0), (1,0,0), (1,1,0), (1,1,1) Hana Rudová, Omezující podmínky, 23. září 201 9 8 Úvod do CP Použití binarizace 3 Konstrukce duálního problému M jedna z možných metod binarizace Výhody binarizace 3 získáváme unifikovaný tvar CSP problému řada algoritmů navržena pro binární CSP M pro výukové účely je vysvětlení na binárních CSP vhodné -i* algoritmy jsou přehlednější a jednodušší na pochopení -i* verze pro nebinární podmínky je často přímým rozšířením obecné verze ±* a tyto algoritmy jsou i aplikovatelné s pomocí binarizace na obecné CSP Ale: značné zvětšení velikosti problému I Nebinární podmínky M složitější propagační algoritmy 3 lze využít jejich sémantiky pro lepší propagaci příklad: al l_di f f erent vs. množina binárních nerovností Hana Rudová, Omezující podmínky, 23. září 2019 9 Úvod do CP Hranová konzistence Propagace omezení Příklad: proměnné: A,B,C -•domény: A g {0,1} B=0 C g {0,1,2,3} omezení: A^B, B^C, A^C I => A=l, B=0, C g {2,3} 3 Algoritmy pro propagaci omezení (konzistenční algoritmy) M umožňují odstranit nekonzistentní hodnoty z domén proměnných 3 zjednodušují problém udržují ekvivalenci mezi původním a zjednodušeným problémem Hana Rudová, Omezující podmínky, 23. září 201 9 Hranová konzistence Vrcholová konzistence Vrcholová konzistence (node consistency) NC S unární podmínky převedeme do domén proměnných Vrchol reprezentující Vije vrcholově konzistentní: M každá hodnota z aktuální domény proměnné Ví splňuje všechny unární podmínky s proměnnou Ví I CSP problém je vrcholově konzistentní: M každý jeho vrchol je vrcholově konzistentní Hana Rudová, Omezující podmínky, 23. září 201 9 12 Hranová konzistence Hranová konzistence (Arc Consistency AC) Pouze pro binární CSP (až její rozšíření jsou pro nebinární CSP) podmínka odpovídá hraně v grafu podmínek více podmínek na jedné hraně převedeme do jedné podmínky Hrana (Ví, V}) je hranově konzistentní, právě když pro každou hodnotu x z aktuální domény Dí existuje hodnota y v D j tak, že ohodnocení [Ví = x,Vj = y] splňuje všechny binární podmínky nad Ví, V/. I | Hranová konzistence je směrová konzistence hrany (Ví,Vj) nezaručuje konzistenci hrany (Vj,Ví) A již zrevidované hrany opět nekonzistentní Revize hrany opakujeme, dokud dochází ke zmenšení nějaké domény & procedure AC-l(G) repeat Changed := false for V hranu (í, j) G G do Changed := revise((í,j)) or Changed until not(Changed) end AC-1 I => AB, BA, BC, CB, lAB, BA, BC, CB, lAB, BA, BC, CB Hana Rudová, Omezující podmínky, 23. září 2019 15 Hranová konzistence Složitost AC-1 proceduře AC-l(G) repeat Changed := false for V hranu (í,j) G G do Changed := revi se((í, j)) or Changed until not(Changed) end AC-1 k maximální velikost domény, e počet hran, n počet proměnných I ' m Složitost 0(enk3) I 3 cyklus přes všechny hrany 0(e) I revi se 0(k2) I 3 jeden cyklus smaže (v nejhorším případě) právě jednu hodnotu z domény proměnné, celkem nk hodnot (každá proměnná má v doméně až k hodnot) => O(nk) Hana Rudová, Omezující podmínky, 23. září 2019 16 Hranová konzistence Neefektivita AC-1 I když zmenšíme jedinou doménu, provádí se revize všech hran. Tyto hrany ale revizí nemusí být vůbec zasaženy. Jaké hrany tedy revidovat po zmenšení domény? I ty, jejichž konzistence může být zmenšením domény proměnné narušena jsou to hrany (í, k), které vedou do proměnné Vk se zmenšenou doménou ti'V (k,m) I Vk ... proměnná se zmenšenou doménou (i2,k) (m,k) při revizi (k,m) došlo ke zmenšení domény Vk 3 hranu (m, k) vedoucí z proměnné Vm, která zmenšení domény způsobila, není třeba revidovat (změna se jí nedotkne) I M příklad: Vk < Vm, Vk in 1 ..1 0, Vm in 2..11, smazání 11 z Vm, tj. Vk in 1 ..1 0, Vm in 2..1 0, důsledek: doména Vk se změní, smaže se 1 0, tj. Vk in 1 ..9, Vm in 2..1 0, a teď reaguji na změnu Vk revizemi (Ví, Vk)'. je tedy zbytečné dělat revizi (Vm, Vk) Hana Rudová, Omezující podmínky, 23. září 2019 17 Hranová konzistence Algoritmus AC-3 Opakování revizí můžeme dělat pomocí fronty stačí jediná fronta hran, které je potřeba (znova) zrevidovat přidáváme tam jen hrany, jejichž konzistence mohla být narušena zmenšením domény I V proceduře AC-3(G) Q := {(í,j) I (í,j) g hrany(G), i ± j] while Q non empty do vyber a smaž (fc,m) z Q if revise((fc,m)) then Q := Q u {(í, k) e hrany(G), i ± k, i ± m} end while . _ A O (k) 3 jakmile je omezení přidáno do fronty, doména (fc) jedné z jeho dvou proměnných (2) byla redukována alespoň o jednu hodnotu 3 Technika AC-3 je dnes asi nejpoužívánější, ale stále není optimální Hana Rudová, Omezující podmínky, 23. září 201 9 19 Hranová konzistence Podpora hodnoty AC-3: při každé revizi hrany testujeme množství dvojic hodnot na konzistenci vzhledem k podmínce. Tyto testy znova opakujeme při každé další revizi hrany. I 3 Při revizi hrany (V2,Vi) vyřadíme hodnotu a z domény proměnné V2. 3 Nyní musíme prozkoumat doménu V3, zda některá z hodnot a, b, c, d neztratila svoji podporu ve V2.1 «• Hodnoty a, b, c není třeba znova kontrolovat <= mají ve V2 také jinou podporu než a. I Podpora (support) pro a e Di = {(j,b) \ b e D j, (a, b) e Cíj} 3 a e D2 má podpory {(3, a), (3, b), (3, d)} 3 d e d3 má pouze jedinou podporu {{2, a)} 3 b g D2 má podpory {(1,a), (1, c), (3, a), (3, c)} I Podpory spočítáme jen jednou. Při opakovaných revizích je budeme používat. Hana Rudová, Omezující podmínky, 23. září 2019 20 Hranová konzistence Algoritmus na inicializaci podpor 3 Udržujeme seznam hodnot, které sami podporujeme (víme komu říct, když zmizíme). S j y. množina dvojic (í, a), pro které je (j,b) podporou 3 Udržujeme počet vlastních podpor (víme, co nám chybí). counter[(í, j), a]: počet podpor, které má hodnota a e Di u proměnné V j procedure initial i ze (G) Q := {}, S := {} // vyprázdněni datových struktur for each (Ví, V)) e h rany (G) do for each a e Di do total := 0 for each b e D j do if (a,b) konzistentní' vzhledem k aj then total := total+1 Sj,fc := Sjtb u {{í,a)} counter [(í, j), a] := total if counter[(í,j),a] = 0 then smaž a z Di Q := Q u i(í,a)} return Q // Q je fronta se smazanými hodnotami Hana Rudová, Omezující podmínky, 23. září 2019 21 Hranová konzistence Aktualizace podpor během výpočtu Situace po zpracování hrany (Ví, V}) algoritmem initialize counter^ j} 2 2 1 , , I Využití struktur s podporami: 1. Předpokládejme, že b3 je vyřazena z domény V). 2. Zjistíme v Sj,^, pro které hodnoty je b3 podporou (tj. (í, a2), (í, a3>). 3. Snížíme counter u těchto hodnot (odstraníme jim jednu podporu). 4. Pokud je některý counter vynulován (a3), potom příslušnou hodnotu vyřadíme z domény a pokračujeme s ní od kroku (1). counter(j $ i 2 a1 — 1 a2= 0 , í<^a3> I __j Hana Rudová, Omezující podmínky, 23. září 201 9 22 Hranová konzistence Algoritmus AC-4 proceduře AC-4(G) Q := i nitialize(G) while not empty(Q) do vyber a smaž libovolný (j,b) gQ for each (í, a) e Sjtb do counter[(í,j),a] : = counter[(í,j),a] - 1 if (counter[(í,j),a] = 0) a (a e D{) then smaž a z Dt Q := Q u {<í,a>} I ^ Složitost 0(ek2) => algoritmus optimální v nejhorším případě složitost initialize 0(ek2) <= (Ví, V}) g hrany(G), a e Dif b e Dj M složitost while cyklu 0(ek2): postupně musím odebrat všechny podpory a těch je 0(ek2) I Paměťová náročnost, není nejlepší v průměrném případě (inicializace zůstává) Hana Rudová, Omezující podmínky, 23. září 201 9 23 Hranová konzistence Další AC algoritmy Existuje řada dalších algoritmů pro zajištění hranové konzistence 3 AC-5, AC-6, AC-7, ... M AC-6 (Bessiěre, Cordier) M zlepšuje paměťovou náročnost a průměrný čas AC-4 drží si pouze jednu podporu, další podpory hledá až při ztrátě aktuální podpory I AC-3.1: AC-3 hledá podpory vždy od začátku, jak to vylepšit? AC-2001: AC-3 s frontou proměnných místo fronty omezení Porovnání: «• AC-3 není (teoreticky) optimální AC-4 je (teoreticky) optimální, ale (prakticky) pomalý AC-6/7 jsou (prakticky) rychlejší než AC-4, ale složité M AC-2001: v praxi je časté využití fronty proměnných Hana Rudová, Omezující podmínky, 23. září 2019 24 Hranová konzistence AC-3.1: optimální algoritmus AC-3 3 Co je na AC-3 neefektivní? hledání podpor v REVISE, které vždy začíná od nuly! if „neexistuje y e D j takové, že (x, y) je konzistentní" then AC-3.1 (Zhang, Yap) M běh stejný jako u AC-3 pro každou hodnotu si pamatuje poslední nalezenou podporu (last) v každém směru a hledání začíná u ní ' procedúre EXIST((i,x),j) y := last{{í,x),j) if y g Dj then return true while y := next(y,Dj) a y ± níl do i f (x, y) e a j then % aj omezeni s proměnými í, j last{{í,x),j) := y return true return false Hana Rudová, Omezující podmínky, 23. září 2019 25 Hranová konzistence AC-2001: jiný optimální algoritmus AC-3 proceduře AC-2001(g) Používá verzi AC-3 s frontou proměnných Q := {í\ í e vrcholy (G)} % seznam vrcholů pro revizi while neprazdna(Q) do vyber a smaž j z Q for Ví g vrcholy (G) takové, že (í, j) g hrany (G) do if REVISE2001 (í,j) then if Di = 0 then return fail Q := Q u {í} return true I procedure REVISE2001 (i, j) DELETED := false for Vx G Di do if last((í,x),j) é D j then if 3y G D/ a y > las t {{í, x), j) a (x,;y)GCíj then last((í,x),j) := y else smaž x z Dí; DELETED := true return DELETED Algoritmus fakticky pracuje s rozdílovými množinami, tj. pro každou proměnnou si pamatuje, jaké hodnoty byly smazány z domény od poslední revize (podobně jako AC-3.1) I Hana Rudová, Omezující podmínky, 23. září 201 9 26 Hranová konzistence Je hranová konzistence dostatečná (úplná)? Použitím AC odstraníme mnoho nekompatibilních hodnot 3 Dostaneme potom řešení problému? NE 3 Víme alespoň zda řešení existuje? NE I 3 X,Y,Z e {1,2}, X+Y, Y + Z, Z + X 3 hranově konzistentní 3 nemá žádné řešení I Jaký je tedy význam AC? 3 někdy dá řešení přímo i* nějaká doména se vyprázdní => řešení neexistuje všechny domény jsou jednoprvkové => máme řešení 3 v obecném případě se alespoň zmenší prohledávaný prostor Hana Rudová, Omezující podmínky, 23. září 201 9 27 Hranová konzistence Konzistence po cestě Konzistence po cestě (PC path consistency) m Příklad: X,Y,Z e {1,2}, X ± Y, Y ±Z, Z±X m Jak posílit konzistenci? Budeme se zabývat několika podmínkami najednou. Cesta (Vo, Vi,..., Vm) je konzistentní právě tehdy, když pro každou dvojici hodnot x e Do a y e Dm splňující binární podmínky na hraně Vo, Vm existuje ohodnocení proměnných Ví,... Vm-i takové, že všechny binární podmínky mezi sousedy Vj, yJ+i jsou splněny. CSP je konzistentní po cestě, právě když jsou všechny cesty konzistentní.l Definice PC nezaručuje, že jsou splněny všechny podmínky nad vrcholy cesty, zabývá se pouze podmínkami mezi sousedy l Hana Rudová, Omezující podmínky, 23. září 201 9 29 Konzistence po cestě PC a cesty délky 2 3 Zjišťování konzistence všech cest není efektivní Stačí ověřit konzistenci cest délky 2 Věta: CSPje PC právě tehdy, když každá cesta délky 2 je PCI Důkaz: 1) PC => cesty délky 2 jsou PC I 2) cesty délky 2 jsou PC => V n cesty délky n jsou PC => PC indukcí podle délky cesty a) n = 2 platí triviálně b) n + 1 (za předpokladu, že platí pro n) i) vezmeme libovolných n+ 2 vrcholů Vo, V\,..., Vn+\ ii) vezmeme libovolné dvě kompatibilní hodnoty xq g Do a xn+\ e D (kompatibilní = splňující všechny bin.podmínky mezi Xo a xn+\) iii) podle a) jsou všechny cesty délky 2 PC, a tedy i Vo, Vn, Vn+\ je PC najdeme tedy xn e Dn tak, že (xo,xn) a (xn, xn+\) jsou konzistentní iv) podle indukčního kroku najdeme zbylé hodnoty na cestě Vo, V\,..., Vni m Definici PC lze tedy upravit tak, že vyžadujeme pouze konzistenci cest délky 21 Hana Rudová, Omezující podmínky, 23. září 2019 30 Konzistence po cestě Vztah PC a AC PC => AC M pokud je cesta (í,j,í) konzistentní (PC), pak je i hrana (í, j) konzistentní (AC), tj. z PC tedy plyne AC 3 PC: ke každé „dvojici hodnot" pro í, i najdu hodnotu v j => AC: ke každé hodnotě v i tedy najdu hodnotu v ji m AC 4> PC 3 příklad: X,Y, Z e {1,2}, X^Y, Y^Z, Z^X 1 .0 je AC, ale není PC, X=0, Y=l nelze rozšířit po cestě (X,Z,Y)I AC vyřazuje nekompatibilní prvky z domény proměnných. Co dělá PC? 3 PC vyřazuje dvojice hodnot PC si pamatuje podmínky explicitně PC si pamatuje, které dvojice hodnot jsou v relaci 3 PC dělá všechny relace nad dvojicemi implicitní (A A+1