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 DACl 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 I 3 Dl ={red,white,black}, D2={green,white,black}, D3={red,white,blue}, D4={white,blue,black} M Po DAC: t>4={white,blue,black}, t>3={white,blue}, t)2={green,white,black}, Dl = {white}, I není AC, ale máme řešení bez navracení vzhledem k %x\, X2, x$, ^4)! Opakování revizí není nutné, lomena 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)l 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 J u obou uvažujeme unární a binární omezení M 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 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-í 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 Xí+i.I 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 Pro i zpětných hran potřebujeme směrovou (i + 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ů. M proceduře MinWidthOrdering((V,E)) Jkonstruujeme od konce)l Q := {} (do vybraného uzlu povede nejméně zpětných hran) while V not empty do N := vyber a smaž uzel s nejmenším 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 J Důkaz: 3 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. I => Mějme graf bez cyklů. Pak lze vytvořit orientovaný strom s kořenem tak, že všechny hranVj směřují z kořenového uzlu. \ 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 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 dl M Důkaz: 3 Uvažujme uspořádání proměnných d = (x\,..., xn) s šířkou 1. 3 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 proceduře TreeSolving(T) nalezeni uspořádáni (xi,...,xn) s šířkou 1 pomoci stromu T (rodič předchází potomky) 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 nechť Xp{i) označuje rodiče xt v uspořádaném stromu for i = n to 1 by -1 do 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\ Důkaz: M existuje uspořádaný graf s uspořádáním d a šířkou i - 1 M speciálně, počet zpětných hran pro každou proměnnou je maximálně i - 1 proměnné ohodnocujeme v pořadí uspořádání grafu nyní, pokud ohodnocujeme proměnnou: -i* musíme najít hodnotu kompatibilní se všemi již ohodnocenými proměnnými, které jsou s proměnnou spojené podmínkou (hranou) S 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) I 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šovatl 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? M 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 Processingl 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.l 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}i I k-tice t hodnot patřících do c: t e c M příklad (pokračování): (0,1) e (A < B)i 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í 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 I 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 Iná podporu (1,0,1) I 3 CSP je obecně hranově konzistentní <=> všechna jeho omezení jsou obecně hranově konzistentní ^ Příklad (pokračování): po GAC dostaneme ^=1, B=0, C=l Hana Rudová, Omezující podmínky, 14. října 2019 15 Nebinární podmínky Konzistence mezí 3 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él Konzistence mezí pro nerovnice M A > Bl=> 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 e {7,..., 10} max(B) < 10-1 => B g{6,...,9}I Cvičer napište pravidla pro konzistenci mezí pro uvedená omezení A < B, A>B, 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)l 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), ...I Příklad: A g {1,..., 6,9,10}, B g {1,..., 10}, A = B + 2 1 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}I 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í ACl Cvičení: napište pravidla pro konzistenci mezí pro uvedená omezení A = B - 3, a = b-c, a=b + c, a všechna jeho omezení mají konzistentní meze Hana Rudová, Omezující podmínky, 14. října 2019 18 Nebinární podmínky