Konzistence po cestě Konzistence po cestě (PC path consistency) M Příklad: X,Y,Z e {1,2}, X ± Y, Y + Z, Z + X 3 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 Vi,... 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í. Hana Rudová, Omezující podmínky, 7. října 201 9 2 Konzistence po cestě Konzistence po cestě (PC path consistency) 3 Příklad: X,Y,Z e {1,2}, X ± Y, Y + Z, Z + X 3 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 Vi,... 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í. 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, 7. října 201 9 2 Konzistence po cestě PC a cesty délky 2 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 PC. Hana Rudová, Omezující podmínky, 7. října 201 9 3 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 PC. Důkaz: 1) PC => cesty délky 2 jsou PC 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 libov. dvě kompatibilní hodnoty xq g Do a xn+\ e Dn+i (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,Vi,...,V1 Hana Rudová, Omezující podmínky, 7. října 201 9 3 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 PC. Důkaz: 1) PC => cesty délky 2 jsou PC 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 libov. dvě kompatibilní hodnoty xq g Do a xn+\ e Dn+i (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\,...,Vn Definici PC lze tedy upravit tak, že vyžadujeme pouze konzistenci cest délky 2 Hana Rudová, Omezující podmínky, 7. října 2019 3 Konzistence po cestě Vztah PC a AC 3 PC => AC M pokud je cesta (í,j,í) konzistentní (PC), pak je i hrana (í, j) konzistentní (AC), tj. z PC tedy plyne AC St PC: ke každé „dvojici hodnot" pro í, i najdu hodnotu v j => AC: ke každé hodnotě v i tedy najdu hodnotu v j Hana Rudová, Omezující podmínky, 7. října 201 9 4 Konzistence po cestě Vztah PC a AC PC => AC pokud je cesta (í,j, í) konzistentní (PC), pak je i hrana (íj) konzistentní (AC), tj. z PC tedy plyne AC ± PC: ke každé „dvojici hodnot" pro i, i najdu hodnotu v j => AC: ke každé hodnotě v i tedy najdu hodnotu v j 3 AC £ PC # příklad: X,Y,Z e {1,2}, X^Y, Y^Z, Z^X «ť je AC, ale není PC, zdůvodnění: Hana Rudová, Omezující podmínky, 7. října 201 9 4 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 S PC: ke každé „dvojici hodnot" pro í, i najdu hodnotu v j => AC: ke každé hodnotě v i tedy najdu hodnotu v j M AC 4> PC 3 příklad: X,Y, Z e {1,2}, X^Y, Y^Z, Z^X ^ je AC, ale není PC, zdůvodnění: X=0, Y=l nelze rozšířit po cestě (X,Z,Y) Hana Rudová, Omezující podmínky, 7. října 201 9 4 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 j M AC 4> PC 3 příklad: X,Y, Z e {1,2}, X^Y, Y^Z, Z^X ^ je AC, ale není PC, zdůvodnění: X=0, Y=l nelze rozšířit po cestě (X,Z,Y) 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 již zrevidované cesty opět nekonzistentní Revize cesty opakujeme dokud jsou nějaké dvojice smazány Princip je podobný jako u AC-1 Před spuštěním algoritmu nutno inicializovat relace Rij pomocí existujících binárních (i unárních) podmínek 3 proceduře PC-l(G) repeat Changed := falše f or m : = 1 to n foř i : = 1 to n for j := 1 to n Changed := revise-3(í,m,j) or Changed until not(Changed) end PC-1 Hana Rudová, Omezující podmínky, 7. října 2019 7 Konzistence po cestě Složitost algoritmu PC-1 Celková složitost 0(n5k5) odvození podobné jako pro AC-1 Rudová, Omezující podmínky, 7. října 201 9 8 Konzistence po cestě Složitost algoritmu PC-1 Celková složitost 0(n5k5) odvození podobné jako pro AC-1 <= 3 cykly pro trojice hodnot 0(n3) <= revise-3 0(k3) 0(n2k2) počet opakování repeat cyklu <= jeden cyklus smaže (v nejhorším případě) právě jednu dvojici hodnot celkem n2k2 hodnot (n2 dvojic proměnných, k2 dvojic hodnot pro každou dvojici proměnných) Neefektivita PC-1 Hana Rudová, Omezující podmínky, 7. října 201 9 8 Konzistence po cestě Složitost algoritmu PC-1 Celková složitost 0(n5k5) odvození podobné jako pro AC-1 <= 3 cykly pro trojice hodnot 0(n3) <= revise-3 0(k3) 0(n2k2) počet opakování repeat cyklu <= jeden cyklus smaže (v nejhorším případě) právě jednu dvojici hodnot celkem n2k2 hodnot (n2 dvojic proměnných, k2 dvojic hodnot pro každou dvojici proměnných) Neefektivita PC-1 opakovaná revize všech cest, i když pro ně nedošlo k žádné změně Hana Rudová, Omezující podmínky, 7. října 201 9 8 Konzistence po cestě Složitost algoritmu PC-1 Celková složitost 0(n5k5) odvození podobné jako pro AC-1 <= 3 cykly pro trojice hodnot 0(n3) <= revise-3 0(k3) 0(n2k2) počet opakování repeat cyklu <= jeden cyklus smaže (v nejhorším případě) právě jednu dvojici hodnot celkem n2k2 hodnot (n2 dvojic proměnných, k2 dvojic hodnot pro každou dvojici proměnných) Neefektivita PC-1 M opakovaná revize všech cest, i když pro ně nedošlo k žádné změně s> při revizi stačí kontrolovat jen zasažené cesty podobně jako pro pc-i Hana Rudová, Omezující podmínky, 7. října 201 9 8 Konzistence po cestě Složitost algoritmu PC-1 Celková složitost 0(n5k5) odvození podobné jako pro AC-1 3 cykly pro trojice hodnot 0(n3) revise-3 0(k3) 0(n2k2) počet opakování repeat cyklu jeden cyklus smaže (v nejhorším případě) právě jednu dvojici hodnot celkem n2k2 hodnot (n2 dvojic proměnných, k2 dvojic hodnot pro každou dvojici proměnných) Neefektivita PC-1 opakovaná revize všech cest, i když pro ně nedošlo k žádné změně * při revizi stačí kontrolovat jen zasažené cesty podobně jako pro pc-i 3 cesty stačí brát pouze s jednou orientací ... Ríj je totéž co Rjí ± příklad: VUV2 e {a,b},V3 e {a,b,c\,Vx ŕ V2,V2 ± V,3Vi ŕ V3 důsledek revi se-3(l, 2, 3) a revi se-3 (3, 2,1) je totožný <= ke každé dvojici hodnot z Vi, V3 (V3, V\) hledám kompatibilní hodnotu z V2 Hana Rudová, Omezující podmínky, 7. října 2019 8 Konzistence po cestě Algoritmus PC-2 Cesty beru pouze s jednou orientací aktualizuji pouze jednu z R^, Rjí 3 Do fronty dávám pouze zasažené cesty podobná modifikace jako AC-3 3 revi se-3(í, m, j) mění Ríj, Hana Rudová, Omezující podmínky, 7. října 201 9 9 Konzistence po cestě Algoritmus PC-2 Cesty beru pouze s jednou orientací aktualizuji pouze jednu z R^, Rjí 3 Do fronty dávám pouze zasažené cesty podobná modifikace jako AC-3 revi se-3 (í, m, j) mění R^, stačí tedy aktualizovat Ru přes j a Rij přes í M Před spuštěním algoritmu M inicializovat relace Ríj pomocí existujících binárních (i unárních) podmínek M proceduře PC-2(G) Q := {(í,m, j) | 1 < i < j < n, 1 < m < n, m ± í, m ± j} //seznam cest pro revizi while Q non empty do vyber a smaž trojici (í,m,j) z Q i f revi se-3 (í, m, j) then Q := Q u {(l,í,j)(l,j,í) I 1 < l 0(k2) <= když je (í,m,j) přidáno do fronty, Rtj bylo redukováno alespoň o jednu hodnotu M celkem n3 trojic (í,m, j) =^> 0(n3) revise-3 0(k3) Hana Rudová, Omezující podmínky, 7. října 201 9 10 Konzistence po cestě Složitost algoritmu PC-2 Složitost 0(n3ks) 3 každé (í, m, j) může být ve frontě maximálně k2 krát => O (k2) <= když je {í,m,j) přidáno do fronty, bylo redukováno alespoň o jednu hodnotu celkem n3 trojic (í,m, j) =^> 0(n3) 3 revise-3 0(k3) Algoritmus není optimální podobně jako AC-3 3 existuje algoritmus PC-4 založen na počítání podpor složitost PC-4 je 0(n3k3), což už je optimální Hana Rudová, Omezující podmínky, 7. října 201 9 10 Konzistence po cestě Složitost algoritmu PC-2 3 Složitost 0(n3k5) 3 každé (í, m, j) může být ve frontě maximálně k2 krát => 0(k2) <= když je (í,m,j) přidáno do fronty, Rtj bylo redukováno alespoň o jednu hodnotu M celkem n3 trojic (í,m, j) =^> 0(n3) revise-3 0(k3) M Algoritmus není optimální podobně jako AC-3 existuje algoritmus PC-4 založen na počítání podpor 3 složitost PC-4 je 0(n3k3), což už je optimální Cvičení: řešte následující problém pomocí PC-2 algoritmu VI G {0,1,2,3},V2 G {0,1}, V3 G {1,2} V3 = VI + 1, V2 + V3,V1 + V2 Hana Rudová, Omezující podmínky, 7. října 201 9 10 Konzistence po cestě Složitost algoritmu PC-2 3 Složitost 0(n3k5) 3 každé (í, m, j) může být ve frontě maximálně k2 krát => 0(k2) <= když je (í,m,j) přidáno do fronty, Rtj bylo redukováno alespoň o jednu hodnotu M celkem n3 trojic (í,m, j) =^> 0(n3) revise-3 0(k3) M Algoritmus není optimální podobně jako AC-3 existuje algoritmus PC-4 založen na počítání podpor 3 složitost PC-4 je 0(n3k3), což už je optimální Cvičení: řešte následující problém pomocí PC-2 algoritmu VI G {0,1,2,3},V2 G {0,1}, V3 G {1,2} V3 = VI + 1, V2 + V3, VI + V2 3 Nápověda: zkonstruuj iniciální relace Ru Hana Rudová, Omezující podmínky, 7. října 201 9 10 Konzistence po cestě Složitost algoritmu PC-2 3 Složitost 0(n3k5) M každé (í, m, j) může být ve frontě maximálně k2 krát => O (k2) <= když je (i,m,j) přidáno do fronty, Rtj bylo redukováno alespoň o jednu hodnotu * celkem n3 trojic (í,m,j) => 0(n3) revise-3 0(k3) 3 Algoritmus není optimální podobně jako AC-3 existuje algoritmus PC-4 založen na počítání podpor složitost PC-4 je 0(n3k3), což už je optimální 3 Cvičení: řešte následující problém pomocí PC-2 algoritmu VI G {0,1, 2,3}, V2 e {0,1}, V3 G {1,2} V3 = VI + 1,V2 + V3,V1 ± V2 M Nápověda: zkonstruuj iniciální relace Rtj iniciálně přidej do fronty (VI, V2, V3), {VI, V3, V2), (V2, VI, V3) Hana Rudová, Omezující podmínky, 7. října 2019 10 Konzistence po cestě Omezení PC algoritmů Paměťové nároky M protože PC eliminuje dvojice hodnot z omezení, potřebuje používat extenzionální reprezentaci omezení (pro každou dvojici hodnot si pamatuji, zdaje/není v doméně) Poměr výkon/cena PC eliminuje více (nebo stejně) nekonzistencí jako AC * poměr výkonu ke zjednodušení problému je ale mnohem horší než u AC Změny grafu omezení PC přidává hrany (omezení) i tam, kde původně nebyly a mění tak konektivitu grafu to vadí při dalším řešení problému, kdy se nemohou používat heuristiky odvozené od grafu (resp. dané původním problémem) PC stále není dostatečné Hana Rudová, Omezující podmínky, 7. října 201 9 Konzistence po cestě Omezení PC algoritmů Paměťové nároky M protože PC eliminuje dvojice hodnot z omezení, potřebuje používat extenzionální reprezentaci omezení (pro každou dvojici hodnot si pamatuji, zdaje/není v doméně) Poměr výkon/cena PC eliminuje více (nebo stejně) nekonzistencí jako AC 3 poměr výkonu ke zjednodušení problému je ale mnohem horší než u AC Změny grafu omezení PC přidává hrany (omezení) i tam, kde původně nebyly a mění tak konektivitu grafu to vadí při dalším řešení problému, kdy se nemohou používat heuristiky odvozené od grafu (resp. dané původním problémem) PC stále není dostatečné M V,X,Y,Z e {1,2,3}, XŕY, Y ŕ Z, Z ŕ X, V ŕ X, V ŕ Y, V^Z je PC a přesto nemá řešení Hana Rudová, Omezující podmínky, 7. října 2019 11 Konzistence po cestě Na půli cesty od AC k PC Jak oslabit PC, aby algoritmus: neměl paměťové nároky PC -» neměnil graf podmínek M byl silnější než AC? Hana Rudová, Omezující podmínky, 7. října 201 9 12 Konzistence po cestě Na půli cesty od AC k PC Jak oslabit PC, aby algoritmus: 3 neměl paměťové nároky PC neměnil graf podmínek byl silnější než AC? Omezená konzistence po cestě - Restricted Path Consistency (RPC) M testujeme PC jen v případě, když je šance, že to povede k vyřazení hodnoty z domény proměnné Příklad: Vi,V2e {a,b},V3e {a,b,c},Vľ^ V2,V2 ± V3,Vi ± V3 je AC ale není PC RPC odstraní z domény V3 hodnoty a, b Hana Rudová, Omezující podmínky, 7. října 201 9 12 Konzistence po cestě Omezená konzistence po cestě (RPC) PC hrany se testuje pouze tehdy, pokud vyřazení dvojice může vést k vyřazení některého z prvků z domény příslušné proměnné Proměnná Vije omezeně konzistentní po cestě (Restricted Path Consistent, RPC): 3 každá hrana vedoucí z Ví je hranově konzistentní M pro každé a e Dt platí: je-li b jediná podpora a ve vrcholu j, potom v každém vrcholu k (spojeném s i a j) existuje hodnota c tak, že (a,c) a (b,c) jsou kompatibilní s příslušnými podmínkami 3 Jak to poznáme? Jedná se o jedinou vzájemnou podporu. Hana Rudová, Omezující podmínky, 7. října 201 9 13 Konzistence po cestě Omezená konzistence po cestě (RPC) PC hrany se testuje pouze tehdy, pokud vyřazení dvojice může vést k vyřazení některého z prvků z domény příslušné proměnné 3 Jak to poznáme? Jedná se o jedinou vzájemnou podporu. Proměnná Vije omezeně konzistentní po cestě (Restricted Path Consistent, RPC). * každá hrana vedoucí z Ví je hranově konzistentní M pro každé a e Dí platí: je-li b jediná podpora a ve vrcholu j, potom v každém vrcholu k (spojeném s i a j) existuje hodnota c tak, že (a,c) a (b,c) jsou kompatibilní s příslušnými podmínkami Algoritmus: založen na AC-4 + seznam cest pro PC (viz Barták přednáška) Hana Rudová, Omezující podmínky, 7. října 2019 13 Konzistence po cestě Propagace pro nebinární omezení Nebinární omezení 3 Zobecnění principů NC, AC, a PC směrem ke k-konzistenci 3 zajímavé z pohledu složitosti řešení problémů pracuje se s libovolnými k-ticemi proměnných 3 v praxi se vzhledem k paměťové a časové složitosti nevyužívá Hana Rudová, Omezující podmínky, 7. října 201 9 Propagace pro nebinární omezení Nebinární omezení 3 Zobecnění principů NC, AC, a PC směrem ke k-konzistenci 3 zajímavé z pohledu složitosti řešení problémů pracuje se s libovolnými k-ticemi proměnných 3 v praxi se vzhledem k paměťové a časové složitosti nevyužívá Obecné typy konzistence pro nebinární podmínky 3 pracuje se přímo s n-árními podmínkami příklad: obecná hranová konzistence, konzistence mezí Hana Rudová, Omezující podmínky, 7. října 201 9 Propagace pro nebinární omezení Nebinární omezení 3 Zobecnění principů NC, AC, a PC směrem ke k-konzistenci 3 zajímavé z pohledu složitosti řešení problémů pracuje se s libovolnými k-ticemi proměnných 3 v praxi se vzhledem k paměťové a časové složitosti nevyužívá Obecné typy konzistence pro nebinární podmínky 3 pracuje se přímo s n-árními podmínkami příklad: obecná hranová konzistence, konzistence mezí Globální omezení: specifické typy konzistencí 3 využívá se sémantika omezení, zaměřené opět na konkrétní omezení speciální typy konzistence pro globální omezení (př. all_different) Hana Rudová, Omezující podmínky, 7. října 201 9 Propagace pro nebinární omezení Nebinární omezení 3 Zobecnění principů NC, AC, a PC směrem ke k-konzistenci 3 zajímavé z pohledu složitosti řešení problémů pracuje se s libovolnými k-ticemi proměnných 3 v praxi se vzhledem k paměťové a časové složitosti nevyužívá Obecné typy konzistence pro nebinární podmínky 3 pracuje se přímo s n-árními podmínkami příklad: obecná hranová konzistence, konzistence mezí Globální omezení: specifické typy konzistencí 3 využívá se sémantika omezení, zaměřené opět na konkrétní omezení speciální typy konzistence pro globální omezení (př. all_different) Pro různé podmínky lze použít různý druh konzistence 3 A k-konzistence Silná k-konzistence => j-konzistence V j < k k-konzistence ^> silná k-konzistence Hana Rudová, Omezující podmínky, 7. října 201 9 18 Propagace pro nebinární omezení Silná k-konzistence ABC 3-konzistentní graf (1.1) lze rozšířit na (1,1,1) (2.2) lze rozšířit na (2,2,2) (1.3) ani (2,3) nejsou konzistentní dvojice (nerozšiřujeme je) není 2-konzistentní (3) nelze rozšířit CSPje silně k-konzistentní právě tehdy, když je j-konzistentní pro každéj k-konzistence Silná k-konzistence => j-konzistence V j < k k-konzistence ^> silná k-konzistence NC = silná 1-konzistence = 1-konzistence AC = (silná) 2-konzistence PC = (silná) 3-konzistence & Cvičení: uveďte příklad problému, který je 4-konzistentní, ale není 3-konzistentní Hana Rudová, Omezující podmínky, 7. října 201 9 18 Propagace pro nebinární omezení Konzistence pro nalezení řešení 3 Máme-li graf s n vrcholy, jak silnou konzistenci potřebujeme, abychom přímo našli řešení? CSP vyřešíme bez navracení vzhledem k uspořádání proměnných (xi,... ,xn), jestliže pro každé i < n může být každé částečné řešení (xi,..., Xi) konzistentně rozšířeno o proměnnou Xi+i. Hana Rudová, Omezující podmínky, 7. října 201 9 19 Propagace pro nebinární omezení Konzistence pro nalezení řešení 3 Máme-li graf s n vrcholy, jak silnou konzistenci potřebujeme, abychom přímo našli řešení? CSP vyřešíme bez navracení vzhledem k uspořádání proměnných (xi,... ,xn), jestliže pro každé i < n může být každé částečné řešení (xi,..., Xi) konzistentně rozšířeno o proměnnou Xi+i. M Nalezení řešení bez navracení pro libovolné uspořádání proměnných? Hana Rudová, Omezující podmínky, 7. října 201 9 19 Propagace pro nebinární omezení Konzistence pro nalezení řešení 3 Máme-li graf s n vrcholy, jak silnou konzistenci potřebujeme, abychom přímo našli řešení? CSP vyřešíme bez navracení vzhledem k uspořádání proměnných (xi,... ,xn), jestliže pro každé i < n může být každé částečné řešení (xi,..., Xi) konzistentně rozšířeno o proměnnou Xi+i. M Nalezení řešení bez navracení pro libovolné uspořádání proměnných? silná n-konzistence je nutná pro graf s n vrcholy ±> n-konzistence nestačí (viz předchozí příklad) 3 silná k-konzistence pro k