Směrová konzistence Směrová hranová konzistence (Probinárnícsp> CSPje směrově hranově konzistentní vzhledem k uspořádání proměnných (x\,... ,xn), právě když je každá hrana (xj,Xí) hranově konzistentní pro každé j < í. proceduře DAC(G, (xi,..., xn)) Directed are consistency DAC for i = n to 1 by -1 do for V j < i takové, že existuje hrana (xj,Xí) do revise ((j, í))) end DAC ©white blue 4 black x3 red i white blue ©green white 4 black x1 red white black Hana Rudová, Omezující podmínky, 14. října 201 9 2 Směrová konzistence Směrová hranová konzistence (Probinárnícsp> CSPje směrově hranově konzistentní vzhledem k uspořádání proměnných (x\,... ,xn), právě když je každá hrana (xj,Xí) hranově konzistentní pro každé j < í. proceduře DAC(G, (xi,..., xn)) Directed are consistency DAC for i = n to 1 by -1 do for V j < i takové, že existuje hrana (xj,Xí) do revise ((j, í))) end DAC Příklad: x\ = x2, x\ = x3, x3 = x\ ©white blue 4 black x3 red i white blue ©green white 4 black x1 red white black Dl ={red,white,black}, D2={green,white,black}, D3={red,white,blue}, D4={white,blue,black} Po DAC: Hana Rudová, Omezující podmínky, 14. října 201 9 2 Směrová konzistence Směrová hranová konzistence (Probinárnícsp> CSPje směrově hranově konzistentní vzhledem k uspořádání proměnných (x\,... ,xn), právě když je každá hrana (xj,Xí) hranově konzistentní pro každé j < í. proceduře DAC(G, (xi,..., xn)) Directed are consistency DAC for i = n to 1 by -1 do for V j < i takové, že existuje hrana (xj,Xí) do revise ((j, í))) end DAC Příklad: x\ = x2, x\ = x3, x3 = x\ ©white blue 4 black x3 red i white blue ©green white 4 black x1 red white black Dl ={red,white,black}, D2={green,white,black}, D3={red,white,blue}, D4={white,blue,black} Po DAC: D4={white,blue,black}, Hana Rudová, Omezující podmínky, 14. října 201 9 2 Směrová konzistence Směrová hranová konzistence (Probinárnícsp> CSPje směrově hranově konzistentní vzhledem k uspořádání proměnných (x\,... ,xn), právě když je každá hrana (xj,Xí) hranově konzistentní pro každé j < í. proceduře DAC(G, (xi,..., xn)) Directed are consistency DAC for i = n to 1 by -1 do for V j < i takové, že existuje hrana (xj,Xí) do revise ((j, í))) end DAC Příklad: x\ = x2, x\ = x3, x3 = x\ ©white blue 4 black x3 red i white blue ©green white 4 black x1 red white black Dl ={red,white,black}, D2={green,white,black}, D3={red,white,blue}, D4={white,blue,black} Po DAC: D4={white,blue,black}, D3={white,blue}, Hana Rudová, Omezující podmínky, 14. října 201 9 2 Směrová konzistence Směrová hranová konzistence (Probinárnícsp> CSPje směrově hranově konzistentní vzhledem k uspořádání proměnných (x\,... ,xn), právě když je každá hrana (xj,Xí) hranově konzistentní pro každé j < í. proceduře DAC(G, (xi,..., xn)) Directed are consistency DAC for i = n to 1 by -1 do for V j < i takové, že existuje hrana (xj,Xí) do revise ((j, í))) end DAC Příklad: x\ = x2, x\ = x3, x3 = x\ ©white blue 4 black x3 red i white blue ©green white 4 black x1 red white black Dl ={red,white,black}, D2={green,white,black}, D3={red,white,blue}, D4={white,blue,black} Po DAC: D4={white,blue,black}, D3={white,blue}, D2={green,white,black}, Hana Rudová, Omezující podmínky, 14. října 201 9 2 Směrová konzistence Směrová hranová konzistence (Probinárnícsp> CSPje směrově hranově konzistentní vzhledem k uspořádání proměnných (x\,... ,xn), právě když je každá hrana (xj,Xí) hranově konzistentní pro každé j < í. proceduře DAC(G, (xi,..., xn)) Directed are consistency DAC for i = n to 1 by -1 do for V j < i takové, že existuje hrana (xj,Xí) do revise ((j, í))) end DAC Příklad: x\ = x2, x\ = x3, x3 = x\ ©white blue 4 black x3 red i white blue ©green white 4 black x1 red white black Dl ={red,white,black}, D2={green,white,black}, D3={red,white,blue}, D4={white,blue,black} Po DAC: D4={white,blue,black}, D3={white,blue}, D2={green,white,black}, Dl = {white}, Hana Rudová, Omezující podmínky, 14. října 201 9 2 Směrová konzistence Směrová hranová konzistence (Probinárnícsp> CSPje směrově hranově konzistentní vzhledem k uspořádání proměnných (x\,... ,xn), právě když je každá hrana (xj,Xí) hranově konzistentní pro každé j < í. proceduře DAC(G, (xi,..., xn)) Directed are consistency DAC for i = n to 1 by -1 do for V j < i takové, že existuje hrana (xj,Xí) do revise ((j, í))) end DAC Příklad: x\ = x2, x\ = x3, x3 = x\ ©white blue 4 black x3 red i white blue ©green white 4 black x1 red white black Dl ={red,white,black}, D2={green,white,black}, D3={red,white,blue}, D4={white,blue,black} Po DAC: D4={white,blue,black}, D3={white,blue}, D2={green,white,black}, Dl = {white}, není AC, ale máme řešení bez navracení vzhledem k Hana Rudová, Omezující podmínky, 14. října 201 9 2 Směrová konzistence Směrová hranová konzistence (Probinárnícsp> CSPje směrově hranově konzistentní vzhledem k uspořádání proměnných (x\,... ,xn), právě když je každá hrana (xj,Xí) hranově konzistentní pro každé j < í. proceduře DAC(G, (xi,..., xn)) Directed are consistency DAC for i = n to 1 by -1 do for V j < i takové, že existuje hrana (xj,Xí) do revise ((j, í))) end DAC Příklad: x\ = x2, x\ = x3, x3 = x\ ©white blue 4 black x3 red i white blue ©green white 4 black x1 red white black Dl ={red,white,black}, D2={green,white,black}, D3={red,white,blue}, D4={white,blue,black} Po DAC: D4={white,blue,black}, D3={white,blue}, D2={green,white,black}, Dl = {white}, není AC, ale máme řešení bez navracení vzhledem k (x\, X2, X3, X4) Hana Rudová, Omezující podmínky, 14. října 201 9 2 Směrová konzistence Směrová hranová konzistence (Probinárnícsp> CSPje směrově hranově konzistentní vzhledem k uspořádání proměnných (xi,... ,xn), právě když je každá hrana (xj,Xí) hranově konzistentní pro každé j < í. proceduře DAC(G, (xi,..., xn)) Directed are consistency DAC for i = n to 1 by -1 do for V j < i takové, že existuje hrana (xj,Xí) do revise ((j, í))) end DAC Příklad: x\ = x2, x\ = x3, x3 = x\ ©white blue 4 black x3 red i white blue ©green white 4 black x1 red white black Dl ={red,white,black}, D2={green,white,black}, D3={red,white,blue}, D4={white,blue,black} Po DAC: D4={white,blue,black}, D3={white,blue}, D2={green,white,black}, Dl = {white}, není AC, ale máme řešení bez navracení vzhledem k (x\, X2, x$, X4) Opakování revizí není nutné, Hana Rudová, Omezující podmínky, 14. října 201 9 2 Směrová konzistence Směrová hranová konzistence (Probinárnícsp> CSPje směrově hranově konzistentní vzhledem k uspořádání proměnných (xi,... ,xn), právě když je každá hrana (xj,Xí) hranově konzistentní pro každé j < í. proceduře DAC(G, (xi,..., xn)) Directed are consistency DAC for i = n to 1 by -1 do for V j < i takové, že existuje hrana (xj,Xí) do revise ((j, í))) end DAC Příklad: x\ = x2, x\ = x3, x3 = x\ ©white blue 4 black x3 red i white blue ©green white 4 black x1 red white black 3 Dl ={red,white,black}, D2={green,white,black}, D3={red,white,blue}, D4={white,blue,black} Po DAC: D4={white,blue,black}, D3={white,blue}, D2={green,white,black}, Dl = {white}, není AC, ale máme řešení bez navracení vzhledem k (x\, X2, x$, x4) & Opakování revizí není nutné, doména revidované proměnné se v dalších cyklech nemění Složitost Hana Rudová, Omezující podmínky, 14. října 2019 2 Směrová konzistence Směrová hranová konzistence (Probinárnícsp> CSPje směrově hranově konzistentní vzhledem k uspořádání proměnných (xi,... ,xn), právě když je každá hrana (xj,Xí) hranově konzistentní pro každé j < í. proceduře DAC(G, (xi,..., xn)) Directed are consistency DAC for i = n to 1 by -1 do for V j < i takové, že existuje hrana (xj,Xí) do revise ((j, í))) end DAC Příklad: x\ = x2, x\ = x3, x3 = x\ ©white blue 4 black x3 red i white blue ©green white 4 black x1 red white black 3 Dl ={red,white,black}, D2={green,white,black}, D3={red,white,blue}, D4={white,blue,black} Po DAC: D4={white,blue,black}, D3={white,blue}, D2={green,white,black}, Dl = {white}, není AC, ale máme řešení bez navracení vzhledem k (x\, X2, x$, x4) Opakování revizí není nutné, doména revidované proměnné se v dalších cyklech nemění Složitost 0(ek2) Hana Rudová, Omezující podmínky, 14. října 201 9 každá hrana se reviduje jednou se složitostí 0(k2) 2 Směrová konzistence Směrová í-konzistence Algoritmus pro DAC byl pouze pro binární CSP í-konzistence vyžaduje uvažování omezení s větším rozsahem proměnných «• musíme aktualizovat relace až nad (í - 1) proměnnými => uvažujeme obecné CSP (tedy i nebinární podmínky) Hana Rudová, Omezující podmínky, 14. října 201 9 3 Směrová konzistence Směrová í-konzistence Algoritmus pro DAC byl pouze pro binární CSP í-konzistence vyžaduje uvažování omezení s větším rozsahem proměnných musíme aktualizovat relace až nad (í - 1) proměnnými => uvažujeme obecné CSP (tedy i nebinární podmínky) CSP je směrově í-konzistentní vzhledem k uspořádání proměnných (x\,...,xn) právě tehdy, když každých (í- 1) proměnných je í-konzistentní vzhledem ke všem proměnným, které je následují v uspořádání. CSP je silně směrově i-konzistentní (DIC-í) právě tehdy, když je směrově j-konzistentní pro každé j < i Hana Rudová, Omezující podmínky, 14. října 201 9 3 Směrová konzistence Vlastnosti DIC-i Opakování AC = silná 2-konzistence 3 PC = silná 3-konzistence DIC-2 je ekvivalentní DAC 3 u obou uvažujeme unární a binární omezení 3 DAC je definován pouze na binární CSP DIC-2 je sice definován pro obecné CSP, ale je pouze schopen k dané hodnotě proměnné hledat konzistentní hodnotu v doméně další proměnné, nezachytí tedy omezení s více než dvěmi proměnnými M DIC-3 lze podobně srovnat se směrovou konzistencí po cestě (directed path consistency, DPC) 3 Algoritmus pro silnou směrovou konzistenci viz [Dechter, Constraint Processing] Hana Rudová, Omezující podmínky, 14. října 2019 4 Směrová konzistence Řešení bez navracení pomocí DIC-í M Opakování: 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í (x\,..., X\) konzistentně rozšířeno o proměnnou Xi+i. Hana Rudová, Omezující podmínky, 14. října 201 9 5 Směrová konzistence Řešení bez navracení pomocí DIC-í 3 Opakování: 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,..., X\) konzistentně rozšířeno o proměnnou Xi+i. M Proměnná musí být kompatibilní s již ohodnocenými proměnnými, tj. s tolika proměnnými, kolik má „zpětných" hran Pro i zpětných hran potřebujeme směrovou (í + l)-konzistenci Je-li m maximum počtu zpětných hran pro všechny vrcholy, stačí nám silná směrovou (m + l)-konzistence 3 Při různém uspořádání vrcholů je počet zpětných hran různý => hledáme uspořádání vrcholů s nejmenším počtem zpětných hran m Hana Rudová, Omezující podmínky, 14. října 201 9 5 Směrová konzistence Šířka grafu Uspořádaný graf je graf s lineárním uspořádáním vrcholů. Šířka vrcholu v uspořádaném grafu je počet hran vedoucích z tohoto vrcholu do předchozích vrcholů. Šířka uspořádaného grafu je maximum z šířek jeho vrcholů. Šířka grafu je minimum z šířek všech jeho uspořádaných grafů. Hana Rudová, Omezující podmínky, 14. října 201 9 6 Směrová konzistence Šířka grafu Uspořádaný graf je graf s lineárním uspořádáním vrcholů. Šířka vrcholu v uspořádaném grafu je počet hran vedoucích z tohoto vrcholu do předchozích vrcholů. Šířka uspořádaného grafu je maximum z šířek jeho vrcholů. Šířka grafu je minimum z šířek všech jeho uspořádaných grafů. M proceduře MinWidthOrdering((V,E)) Hana Rudová, Omezující podmínky, 14. října 201 9 6 Směrová konzistence Šířka grafu Uspořádaný graf je graf s lineárním uspořádáním vrcholů. Šířka vrcholu v uspořádaném grafu je počet hran vedoucích z tohoto vrcholu do předchozích vrcholů. Šířka uspořádaného grafu je maximum z šířek jeho vrcholů. Šířka grafu je minimum z šířek všech jeho uspořádaných grafů. M proceduře MinWidthOrdering((V,E)) (konstruujeme od konce) Hana Rudová, Omezující podmínky, 14. října 201 9 6 Směrová konzistence Šířka grafu Uspořádaný graf je graf s lineárním uspořádáním vrcholů. Šířka vrcholu v uspořádaném grafu je počet hran vedoucích z tohoto vrcholu do předchozích vrcholů. Šířka uspořádaného grafu je maximum z šířek jeho vrcholů. Šířka grafu je minimum z šířek všech jeho uspořádaných grafů. M proceduře MinWidthOrdering((V,E)) (konstruujeme od konce) Q := {} (do vybraného uzlu povede nejméně zpětných hran) while V not empty do N := vyber a smaž uzel s nejmenšim počtem hran z (V,E) zařaď N do Q return Q Hana Rudová, Omezující podmínky, 14. října 2019 6 Směrová konzistence Graf podmínek s šířkou 1 = strom Tvrzení: Graf je strom právě tehdy, když má šířku 1. 2Á3 Hana Rudová, Omezující podmínky, 14. října 2019 7 Směrová konzistence Graf podmínek s šířkou 1 = strom Tvrzení: Graf je strom právě tehdy, když má šířku 1. Důkaz: M Předpoklad: Strom neobsahuje cyklus. 2Á3 Hana Rudová, Omezující podmínky, 14. října 2019 7 Směrová konzistence Graf podmínek s šířkou 1 = strom Tvrzení: Graf je strom právě tehdy, když má šířku 1. Důkaz: M Předpoklad: Strom neobsahuje cyklus. <= Mějme graf šířky 1. Pokud by obsahoval cyklus, tak bychom pro libovolné uspořádání proměnných měli proměnnou se dvěma rodiči, tj. spor. Hana Rudová, Omezující podmínky, 14. října 201 9 7 Směrová konzistence Graf podmínek s šířkou 1 = strom Tvrzení: Graf je strom právě tehdy, když má šířku 1. Důkaz: M Předpoklad: Strom neobsahuje cyklus. <= Mějme graf šířky 1. Pokud by obsahoval cyklus, tak bychom pro libovolné uspořádání proměnných měli proměnnou se dvěma rodiči, tj. spor. => Mějme graf bez cyklů. Pak lze vytvořit orientovaný strom s kořenem tak, že všechny hrany směřují z kořenového uzlu. 1 Hana Rudová, Omezující podmínky, 14. října 201 9 7 Směrová konzistence Graf podmínek s šířkou 1 = strom Tvrzení: Graf je strom právě tehdy, když má šířku 1. Důkaz: M Předpoklad: Strom neobsahuje cyklus. <= Mějme graf šířky 1. Pokud by obsahoval cyklus, tak bychom pro libovolné uspořádání proměnných měli proměnnou se dvěma rodiči, tj. spor. => Mějme graf bez cyklů. Pak lze vytvořit orientovaný strom s kořenem tak, že všechny hrany směřují z kořenového uzlu. V tomto stromu má každý uzel nejvýše jednoho rodiče. Libovolné uspořádání, ve kterém rodič předchází potomky ve stromě, má šířku 1. 1 Hana Rudová, Omezující podmínky, 14. října 201 9 7 Směrová konzistence Konzistence pro stromové CSP Tvrzení: Nechť d = (x\,... ,xn) je uspořádání stromového grafu podmínek T pro daný CSP. Jestliže T je směrově hranově konzistentní vzhledem k d, pak má CSP řešení bez navracení vzhledem k d. Hana Rudová, Omezující podmínky, 14. října 201 9 8 Směrová konzistence Konzistence pro stromové CSP Tvrzení: Nechť d = (x\,... ,xn) je uspořádání stromového grafu podmínek T pro daný CSP. Jestliže T je směrově hranově konzistentní vzhledem k d, pak má CSP řešení bez navracení vzhledem k d. M Důkaz: * Uvažujme uspořádání proměnných d = (x\,..., xn) s šířkou 1. M Předpokládejme, že X\,..., Xt jsou konzistentně nainstanciovány. «• Snažíme se nainstanciovat Xi+\\ d je uspořádaní šířky 1, tedy existuje pouze jeden rodič x j (j < í) proměnné xt+i, který může omezovat Xt+i :wq {Xj,Xi+i) je hranově konzistentní (z DAC), tedy a existuje hodnota konzistentní se současným přiřazením Xj ±> tuto hodnotu přiřadíme xt+i 10 Hana Rudová, Omezující podmínky, 14. října 201 9 8 Směrová konzistence Algoritmus zajištění DAC pro stromové CSP i proceduře TreeSolving(T) nalezeni uspořádáni (xi,...,xn) s šiřkou 1 pomoci stromu T (rodič předcházi potomky) nechť x p a) označuje rodiče xt v uspořádaném stromu f or í = n to 1 by -1 do revise((xP(í),Xí)) 2 ř \ 3 if Dvu) = 0 exit (řešeni neexistuje) x A end TreeSol vi ng ^ ~ Cvičení: XI, X2.X3.X4 in 1..5, X1=X2+1, X1 Složitost algoritmu 0(nk2) M Algoritmus zajistí DAC pro stromové CSP, tj. bude možné nalézt řešení bez navracení Pokud aplikujeme DAC vzhledem k uspořádání šířky 1, a pak v opačném směru, tak dosáhneme plné hranové konzistence. viz Barták, přednáška revise((xP(í),Xí)) if Dpd) = 0 exit (řešeni neexistuje) end TreeSolving Hana Rudová, Omezující podmínky, 14. října 201 9 9 Směrová konzistence Šířka grafu a stupeň konzistence Tvrzení: Nechť je dán CSP, jehož uspořádaný graf podmínek s uspořádáním d má šířku i - 1. Jestliže je problém silně směrově í-konzistentní, pak je problém řešitelný bez navracení vzhledem k d. Hana Rudová, Omezující podmínky, 14. října 201 9 10 Směrová konzistence Šířka grafu a stupeň konzistence Tvrzení: Nechť je dán CSP, jehož uspořádaný graf podmínek s uspořádáním d má šířku i - 1. Jestliže je problém silně směrově í-konzistentní, pak je problém řešitelný bez navracení vzhledem k d. Důkaz: 3 existuje uspořádaný graf s uspořádáním d a šířkou i - 1 3 speciálně, počet zpětných hran pro každou proměnnou je maximálně i - 1 3 proměnné ohodnocujeme v pořadí uspořádání grafu nyní, pokud ohodnocujeme proměnnou: X musíme najít hodnotu kompatibilní se všemi již ohodnocenými proměnnými, které jsou s proměnnou spojené podmínkou (hranou) 3 nechť takových proměnných je m, potom m < (í - 1) (<= graf má šířku (í - 1)) X* graf je směrově í-konzistentní, tedy taková hodnota musí existovat (<= z definice) Hana Rudová, Omezující podmínky, 14. října 201 9 maximálne w 10 Směrová konzistence Adaptivní konzistence 3 Původní intuice: proměnná musí být kompatibilní s již ohodnocenými proměnnými, tj. s tolika proměnnými, kolik má „zpětných" hran. 3 Je tedy nutná směrová í-konzistence odpovídající šířce grafu? Problém: algoritmy silné směrové í-konzistence pro i > 3 mění graf podmínek přidáváním hran, nutná úroveň i se může zvětšovat Hana Rudová, Omezující podmínky, 14. října 201 9 Směrová konzistence Adaptivní konzistence 3 Původní intuice: proměnná musí být kompatibilní s již ohodnocenými proměnnými, tj. s tolika proměnnými, kolik má „zpětných" hran. 3 Je tedy nutná směrová í-konzistence odpovídající šířce grafu? Problém: algoritmy silné směrové í-konzistence pro i > 3 mění graf podmínek přidáváním hran, nutná úroveň i se může zvětšovat 3 Algoritmus adaptivní konzistence ADC pro nalezení řešení bez navracení 3 uvažujme uspořádání proměnných d M rekurzivně vytváříme směrovou í-konzistenci (od poslední k první proměnné v d) M měníme úroveň i od uzlu k uzlu tak, abychom se adaptovali aktuální šířce uzlu v momentě zpracování Hana Rudová, Omezující podmínky, 14. října 201 9 Směrová konzistence Adaptivní konzistence 3 Původní intuice: proměnná musí být kompatibilní s již ohodnocenými proměnnými, tj. s tolika proměnnými, kolik má „zpětných" hran. 3 Je tedy nutná směrová í-konzistence odpovídající šířce grafu? Problém: algoritmy silné směrové í-konzistence pro i > 3 mění graf podmínek přidáváním hran, nutná úroveň i se může zvětšovat 3 Algoritmus adaptivní konzistence ADC pro nalezení řešení bez navracení 3 uvažujme uspořádání proměnných d 3 rekurzivně vytváříme směrovou í-konzistenci (od poslední k první proměnné v d) 3 měníme úroveň í od uzlu k uzlu tak, abychom se adaptovali aktuální šířce uzlu v momentě zpracování Proč algoritmus funguje? 3 v momentě zpracování uzlu je určena finální šířka uzlu 3 víme tedy, jakou úroveň směrové í-konzistence musíme dosáhnout Hana Rudová, Omezující podmínky, 14. října 2019 11 Směrová konzistence Polynomiální CSP w šířka grafu, n počet proměnných, k horní mez velikosti domén Složitost DIC-í 0(nwl ■ (2k)1) důkaz viz Dechter, Constraint Processing Časová a prostorová složitost algoritmu adaptivní konzistence je 0(n ■ (2k)w+1) a 0(n ■ kw) důkaz viz Dechter, Constraint Processing Hana Rudová, Omezující podmínky, 14. října 201 9 12 Směrová konzistence Polynomiální CSP w šířka grafu, n počet proměnných, k horní mez velikosti domén Složitost DIC-í 0(nwl ■ (2k)1) důkaz viz Dechter, Constraint Processing Časová a prostorová složitost algoritmu adaptivní konzistence je 0(n ■ (2k)w+1) a 0(n ■ kw) důkaz viz Dechter, Constraint Processing Věta: Třída CSP problémů, jejichž šířka grafu je ohraničena konstantou b je řešitelná v polynomiálním čase a prostoru. Hana Rudová, Omezující podmínky, 14. října 201 9 12 Směrová konzistence Polynomiální CSP w šířka grafu, n počet proměnných, k horní mez velikosti domén Složitost DIC-í 0(nwl ■ (2k)1) důkaz viz Dechter, Constraint Processing Časová a prostorová složitost algoritmu adaptivní konzistence je 0(n ■ (2k)w+1) a 0(n ■ kw) důkaz viz Dechter, Constraint Processing Věta: Třída CSP problémů, jejichž šířka grafu je ohraničena konstantou b je řešitelná v polynomiálním čase a prostoru. Použitelnost algoritmu ADC 3 ADC není jen procedura pro rozhodnutí konzistence M ADC může sloužit i ke kompilaci ±> ADC transformuje problém na ekvivalentní graf, ze kterého může být každé řešení odvozeno v lineárním čase M prostorová složitost ale zůstává Hana Rudová, Omezující podmínky, 14. října 2019 12 Směrová konzistence Obecná hranová konzistence, konzistence mezí Pojmy a značení Rozsah omezení scope(c) množina proměnných, na kterých je c definováno příklad: A,B,C e {0,1,2} scope(A < B) = {A,B} Hana Rudová, Omezující podmínky, 14. října 201 9 14 Nebinární podmínky Pojmy a značení Rozsah omezení scope(c) množina proměnných, na kterých je c definováno příklad: A,B,C e {0,1,2} scope(A < B) = {A,B} M k-tice t hodnot patřících do c\ t e c M příklad (pokračování): (0,1) e (A < B) Hana Rudová, Omezující podmínky, 14. října 201 9 14 Nebinární podmínky Pojmy a značení Rozsah omezení scope(c) množina proměnných, na kterých je c definováno příklad: A,B,C e {0,1,2} scope(A < B) = {A,B} M k-tice t hodnot patřících do c: t e c M příklad (pokračování): (0,1) e (A < B) 3 Proměnná x e scope(c), k-tice tec t[x] je hodnota proměnné x v t M příklad (pokračování): (0,1) [A] = 0 Hana Rudová, Omezující podmínky, 14. října 201 9 14 Nebinární podmínky Definice obecné hranové konzistence (GAC) Generalized arc consistency (někdy nazývána doménová konzistence) 3 pro každou proměnnou z podmínky a každou její hodnotu existuje ohodnocení zbylých proměnných v podmínce tak, že podmínka platí * A + B = C, A g {1,2, 3}, B g {2, 3,4}, C g {3,..., 7} je obecně hranově konzistentní Hana Rudová, Omezující podmínky, 14. října 201 9 Nebinární podmínky Definice obecné hranové konzistence (GAC) Generalized arc consistency (někdy nazývána doménová konzistence) 3 pro každou proměnnou z podmínky a každou její hodnotu existuje ohodnocení zbylých proměnných v podmínce tak, že podmínka platí * A + B = C, A g {1,2, 3}, B g {2, 3,4}, C g {3,..., 7} je obecně hranově konzistentní Omezení c je obecně hranově konzistentní, jestliže má každá hodnota a každé proměnné x e scope(c) doménovou podporu v c Hodnota a proměnné x e scope(c) má doménovou podporu ívc, jestliže t g c a platí a = t[x] M pro každé y e scope(c) platí t[y] e Dy M Příklad: A g {0,1}, Bg {0,1}, C g {1, 2}, A = B+C, 0 u A Hana Rudová, Omezující podmínky, 14. října 201 9 Nebinární podmínky Definice obecné hranové konzistence (GAC) Generalized arc consistency (někdy nazývána doménová konzistence) 3 pro každou proměnnou z podmínky a každou její hodnotu existuje ohodnocení zbylých proměnných v podmínce tak, že podmínka platí * A + B = C, A g {1,2, 3}, B g {2, 3,4}, C g {3,..., 7} je obecně hranově konzistentní Omezení c je obecně hranově konzistentní, jestliže má každá hodnota a každé proměnné x e scope(c) doménovou podporu v c Hodnota a proměnné x e scope(c) má doménovou podporu ívc, jestliže t g c a platí a = t[x] M pro každé y e scope(c) platí t[y] e Dy M Příklad: A g {0,1}, Bg {0,1}, C g {1, 2}, A = B+C, 0 u A nemá podporu, 1 u A Hana Rudová, Omezující podmínky, 14. října 201 9 Nebinární podmínky Definice obecné hranové konzistence (GAC) Generalized arc consistency (někdy nazývána doménová konzistence) 3 pro každou proměnnou z podmínky a každou její hodnotu existuje ohodnocení zbylých proměnných v podmínce tak, že podmínka platí 3 A + B = C, A g {1,2, 3}, B g {2, 3,4}, C g {3,..., 7} je obecně hranově konzistentní Omezení c je obecně hranově konzistentní, jestliže má každá hodnota a každé proměnné x e scope(c) doménovou podporu v c Hodnota a proměnné x e scope(c) má doménovou podporu ívc, jestliže t g c a platí a = t[x] M pro každé y e scope(c) platí t[y] e Dy M Příklad: A g {0,1}, Bg {0,1}, C g {1, 2}, A = B+C, 0 u A nemá podporu, 1 u A má podporu (1,0,1) Hana Rudová, Omezující podmínky, 14. října 201 9 Nebinární podmínky Definice obecné hranové konzistence (GAC) Generalized arc consistency (někdy nazývána doménová konzistence) 3 pro každou proměnnou z podmínky a každou její hodnotu existuje ohodnocení zbylých proměnných v podmínce tak, že podmínka platí * A + B = C, A g {1,2, 3}, B g {2, 3,4}, C g {3,..., 7} je obecně hranově konzistentní Omezení c je obecně hranově konzistentní, jestliže má každá hodnota a každé proměnné x e scope(c) doménovou podporu v c Hodnota a proměnné x e scope(c) má doménovou podporu t v c, jestliže j ř g c a platí a = t[x] M pro každé y e scope(c) platí t[y] e Dy M Příklad: A g {0,1}, Bg {0,1}, C g {1, 2}, A = B+C, 0 u A nemá podporu, 1 u A má podporu (1,0,1) 3 CSP je obecně hranově konzistentní <=> všechna jeho omezení jsou obecně hranově konzistentní & Příklad (pokračování): po GAC dostaneme Hana Rudová, Omezující podmínky, 14. října 2019 15 Nebinární podmínky Definice obecné hranové konzistence (GAC) Generalized arc consistency (někdy nazývána doménová konzistence) 3 pro každou proměnnou z podmínky a každou její hodnotu existuje ohodnocení zbylých proměnných v podmínce tak, že podmínka platí 3 A + B = C, A g {1,2, 3}, B g {2, 3,4}, C g {3,..., 7} je obecně hranově konzistentní Omezení c je obecně hranově konzistentní, jestliže má každá hodnota a každé proměnné x e scope(c) doménovou podporu v c Hodnota a proměnné x e scope(c) má doménovou podporu t v c, jestliže j ř g c a platí a = t[x] M pro každé y e scope(c) platí t[y] e Dy M Příklad: A g {0,1}, Bg {0,1}, C g {1, 2}, A = B+C, 0 u A nemá podporu, 1 u A má podporu (1,0,1) 3 CSP je obecně hranově konzistentní <=> všechna jeho omezení jsou obecně hranově konzistentní Příklad (pokračování): po GAC dostaneme A=l, B=0, C=l Hana Rudová, Omezující podmínky, 14. října 2019 15 Nebinární podmínky Konzistence mezí Bounds consistency BC: slabší než obecná hranová konzistence propagace pouze při změně minimální nebo maximální hodnoty v doméně proměnné M tedy došlo ke změně mezí domény proměnné Hana Rudová, Omezující podmínky, 14. října 201 9 16 Nebinární podmínky Konzistence mezí 3 Bounds consistency BC: slabší než obecná hranová konzistence propagace pouze při změně minimální nebo maximální hodnoty v doméně proměnné tedy došlo ke změně mezí domény proměnné Konzistence mezí pro nerovnice 3 A > B Hana Rudová, Omezující podmínky, 14. října 201 9 16 Nebinární podmínky Konzistence mezí M Bounds consistency BC: slabší než obecná hranová konzistence propagace pouze při změně minimální nebo maximální hodnoty v doméně proměnné tedy došlo ke změně mezí domény proměnné Konzistence mezí pro nerovnice 3 A > B=> min(A) > min(B)+l, max(B) < max(A)-l příklad: A g {4,..., 10}, Be {6,... 18}, A > B mi n (A) > Hana Rudová, Omezující podmínky, 14. října 201 9 16 Nebinární podmínky Konzistence mezí Bounds consistency BC: slabší než obecná hranová konzistence 3 propagace pouze při změně minimální nebo maximální hodnoty v doméně proměnné tedy došlo ke změně mezí domény proměnné Konzistence mezí pro nerovnice 3 A > B=> min(A) > min(B)+l, max(B) < max(A)-l 3 příklad: A g {4,..., 10}, Be {6,... 18}, A > B min(A) > 6+1 => A g {7,..., 10} max(B) < 10-1 => B e {6,...,9} Hana Rudová, Omezující podmínky, 14. října 201 9 16 Nebinární podmínky Konzistence mezí Bounds consistency BC: slabší než obecná hranová konzistence propagace pouze při změně minimální nebo maximální hodnoty v doméně proměnné tedy došlo ke změně mezí domény proměnné Konzistence mezí pro nerovnice A > B => min(A) > min(B)+l, max(B) < max(A)-l * příklad: A e {4,..., 10}, Be {6,... 18}, A > B min(A) > 6+1 => A e {7,..., 10} max(B) < 10-1 => B g {6,...,9} Cvičer napište pravidla pro konzistenci mezí pro uvedená omezení -•AB, A min(A) > min(B)+min(C), max(A) < max(B)+max(C) min(B) > mi n(A)-max(C), max(B) < max(A)-min(C) min(C) > min(A)-max(B), max(C) < max(A)-min(B) Hana Rudová, Omezující podmínky, 14. října 201 9 17 Nebinární podmínky Konzistence mezí a aritmetická omezení A = B + C => min(A) > min(B)+min(C), max(A) < max(B)+max(C) min(B) > mi n(A)-max(C), max(B) < max(A)-min(C) min(C) > min(A)-max(B), max(C) < max(A)-min(B) M změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) 3 změna max (A)vyvolá pouze změnu max(B) amax(C), ... Hana Rudová, Omezující podmínky, 14. října 201 9 17 Nebinární podmínky Konzistence mezí a aritmetická omezení A = B + C => min(A) > min(B)+min(C), max(A) < max(B)+max(C) min(B) > mi n(A)-max(C), max(B) < max(A)-min(C) min(C) > min(A)-max(B), max(C) < max(A)-min(B) M změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) 3 změna max (A)vyvolá pouze změnu max(B) amax(C), ... Příklad: A e {1,..., 6,9,10}, B e {1,..., 10}, A = B + 2 A = B + 2 => Hana Rudová, Omezující podmínky, 14. října 201 9 17 Nebinární podmínky Konzistence mezí a aritmetická omezení A = B + C => min(A) > min(B)+min(C), max(A) < max(B)+max(C) min(B) > mi n(A)-max(C), max(B) < max(A)-min(C) min(C) > min(A)-max(B), max(C) < max(A)-min(B) M změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) * změna max (A)vyvolá pouze změnu max(B) amax(C), ... Příklad: A e {1,..., 6,9,10}, B e {1,..., 10}, A = B + 2 A = B + 2 => min(A)>l+2, max(A)<10+2 => A g {3,..., 6,9,10} => min(B)>l-2, max(B)<10-2 => B g{1,...,8} Hana Rudová, Omezující podmínky, 14. října 201 9 17 Nebinární podmínky Konzistence mezí a aritmetická omezení A = B + C => min(A) > min(B)+min(C), max(A) < max(B)+max(C) min(B) > min(A)-max(C), max(B) < max(A)-min(C) min(C) > min(A)-max(B), max(C) < max(A)-min(B) M změna mi n(A)vyvolá pouze změnu mi n(B) amin(C) 3 změna max(A)vyvolá pouze změnu max(B) amax(C), ... Příklad: A e {1,..., 6,9,10}, B e {1,..., 10}, A = B + 2 A = B + 2 => min(A)>l+2, max(A)<10+2 => A g {3,..., 6,9,10} => min(B)>l-2, max(B)<10-2 => B g{1,...,8} tj. doména B má pouze změněny meze a hodnoty 5, 6 zůstanou v doméně A e {3,..., 6, 9,10}, B g {1,..., 8}, A = B + 2 je BC, není GAC, není AC Hana Rudová, Omezující podmínky, 14. října 201 9 17 Nebinární podmínky Konzistence mezí a aritmetická omezení A = B + C => min(A) > min(B)+min(C), max(A) < max(B)+max(C) min(B) > mi n(A)-max(C), max(B) < max(A)-min(C) min(C) > min(A)-max(B), max(C) < max(A)-min(B) M změna mi n (A) vyvolá pouze změnu mi n (B) a mi n (C) * změna max (A)vyvolá pouze změnu max(B) amax(C), ... Příklad: A e {1,..., 6,9,10}, B e {1,..., 10}, A = B + 2 A = B + 2 => min(A)>l+2, max(A)<10+2 => A g {3,..., 6,9,10} => min(B)>l-2, max(B)<10-2 => B g{1,...,8} tj. doména B má pouze změněny meze a hodnoty 5, 6 zůstanou v doméně A g {3,..., 6, 9,10}, B g {1,..., 8}, A = B + 2 je BC, není GAC, není AC Cvičení: napište pravidla pro konzistenci mezí pro uvedená omezení A = B - 3, a = b-c, a=b + c, a příklad: a = 1, t = (1, 5, 7) Hana Rudová, Omezující podmínky, 14. října 201 9 18 Nebinární podmínky Definice konzistence mezí 3 Hodnota a proměnné x e scope(c) má intervalovou podporu řve, jestliže j f g c a platí a = t[x] * příklad: a = 1, t = (1, 5, 7) pro každé y g 5cope(c) platí t[y] g [mín(Dy),max(Dy)] ± př. (pokrač.) y = 5, z = 7, Dy = Dz = {1, 2,4, 5,10} Hana Rudová, Omezující podmínky, 14. října 201 9 18 Nebinární podmínky Definice konzistence mezí 3 Hodnota a proměnné x g scope(c) má intervalovou podporu řve, jestliže j f g c a platí a = t[x] 3 příklad: a = 1, t = (1, 5, 7) pro každé y g 5cope(c) platí t[y] g [mín(Dy),max(Dy)] * př. (pokrač.) y = 5, z = 7, Dy = Dz = {1, 2,4, 5,10} 5 = t[y] i 7 = t[z] mají intervalovou podporu Hana Rudová, Omezující podmínky, 14. října 201 9 18 Nebinární podmínky Definice konzistence mezí 3 Hodnota a proměnné x e scope(c) má intervalovou podporu řve, jestliže j f g c a platí a = t[x] 3 příklad: a = 1, t = (1, 5, 7) pro každé y g 5cope(c) platí t[y] g [mín(Dy),max(Dy)] * př. (pokrač.) y = 5, z = 7, Dy = Dz = {1, 2,4, 5,10} 5 = t[y] i 7 = t[z] mají intervalovou podporu Srovnání: doménová podpora GAC pro každé y g scope(c) platí t[y] g Dy Hana Rudová, Omezující podmínky, 14. října 201 9 18 Nebinární podmínky Definice konzistence mezí 3 Hodnota a proměnné x g scope(c) má intervalovou podporu řve, jestliže M t g c a platí a = t[x] 3 příklad: a = 1, t = (1, 5, 7) pro každé y g 5cope(c) platí t[y] g [mín(Dy),max(Dy)] St př. (pokrač.) y = 5, z = 7, Dy = Dz = {1, 2,4, 5,10} 5 = t[y] i 7 = t[z] mají intervalovou podporu Srovnání: doménová podpora GAC pro každé y g scope(c) platí t[y] g Dy ± př. (pokrač.) 7 = t[z] nemá doménovou podporu Hana Rudová, Omezující podmínky, 14. října 201 9 18 Nebinární podmínky Definice konzistence mezí 3 Hodnota a proměnné x e scope(c) má intervalovou podporu řve, jestliže j f g c a platí a = t[x] 3 příklad: a = 1, t = (1, 5, 7) pro každé y g 5cope(c) platí t[y] g [mín(Dy),max(Dy)] * př. (pokrač.) y = 5, z = 7, Dy = Dz = {1, 2,4, 5,10} 5 = t[y] i 7 = t[z] mají intervalovou podporu Srovnání: doménová podpora GAC pro každé y e scope(c) platí t[y] e Dy ± př. (pokrač.) 7 = t[z] nemá doménovou podporu Omezení má konzistentní meze, jestliže každá hodnota a proměnné x g scope(c) má intervalovou podporu v c 3 CSP má konzistentní meze <=> všechna jeho omezení mají konzistentní meze Hana Rudová, Omezující podmínky, 14. října 2019 18 Nebinární podmínky