CLP(FD) - prohledávání Vestavěné predikáty pro labeling Instanciace proměnné Variable hodnotami v její doméně indomain( Variable ) hodnoty jsou instanciovány pri backtrackingu ve vzrůstajícím poradí ?- X in 4..5, indomain(X). X = 4 ? ; X = 5 ? Hana Rudová, Logické programování I, 29. dubna 2012 2 CLP(FD) Vestavěné predikáty pro labeling Instanciace proměnné Variable hodnotami v její doméně indomain( Variable ) hodnoty jsou instanciovány pri backtrackingu ve vzrůstajícím poradí ?- X in 4..5, indomain(X). X = 4 ? ; X = 5 ? labeling( [] ). labeling( [Var|Rest] ) :- % výběr nejlevější proměnné k instanciaci indomain( Var ), % výběr hodnot ve vzrUstajícím poradí labeling( Rest ). Hana Rudová, Logické programování I, 29. dubna 2012 2 CLP(FD) Vestavěné predikáty pro labeling Instanciace proměnné Variable hodnotami v její doméně indomain( Variable ) hodnoty jsou instanciovány pri backtrackingu ve vzrůstajícím poradí ?- X in 4..5, indomain(X). X = 4 ? ; X = 5 ? labeling( [] ). labeling( [Var|Rest] ) :- % výběr nejlevější proměnné k instanciaci indomain( Var ), % výběr hodnot ve vzrUstajícím poradí labeling( Rest ). labeling( Options, Variables ) ľ- A in G..2, B in G..2, B#< A, 1abe1ing([], [A,B]). Hana Rudová, Logické programování I, 29. dubna 2012 2 CLP(FD) Uspořádání hodnot a proměnných Při prohledávání je rozhodující uspořádání hodnot a proměnných Určují je heuristiky výběru hodnot a výběru proměnných labeling( [] ). labeling( Variables ) :- select_variable(Variables,Var,Rest), select_value(Var,Value), Hana Rudová, Logické programování I, 29. dubna 2012 3 CLP(FD) Uspořádání hodnot a proměnných & Pri prohledávání je rozhodující uspořádání hodnot a proměnných UrCujíje heuristiky výběru hodnot a výběru proměnných labeling( [] ). labeling( Variables ) select_van'able(Van'ables,Var,Rest), select_value(Var,Value), ( Var #= Value, labeling( Rest ) Hana Rudová, Logické programování I, 29. dubna 2012 3 CLP(FD) Usporádání hodnot a proměnných & Pri prohledávání je rozhodující usporádání hodnot a proměnných Urcujíje hěuristiky výběru hodnot a výběru proměnných labeling( [] ). labeling( Variables ) :- select_variableCVariables,Var,Rest), select_value(Var,Value), ( Var #= Value, labeling( Rest ) Var #\= Value , % nemusí dojít k instanciaci Var labeling( Variables ) % proto pokracujeme se všemi promennými vcetne Var Hana Rudová, Logické programování I, 29. dubna 2012 3 CLP(FD) Uspořádání hodnot a proměnných & Pri prohledávání je rozhodující uspořádání hodnot a proměnných UrCujíje heuristiky výběru hodnot a výběru proměnných labeling( [] ). labeling( Variables ) select_van'able(Van'ables,Var,Rest), select_value(Var,Value), ( Var #= Value, labeling( Rest ) Var #\= Value , % nemusí dojít k instanciaci Var labeling( Variables ) % proto pokraCujeme se všemi proměnnými vCetne Var -í* Statické usporádání: urCeno už pred prohledáváním JS> Dynamické usporádání: poCítá se behem prohledávání Hana Rudová, Logické programování I, 29. dubna 2012 3 CLP(FD) Výběr hodnoty JS> Obecný princip výběru hodnoty: první úspěch (succeed first) J> volíme poradí tak, abychom výběr nemuseli opakovat ?- domain([A,B,C],1,2), A#=B+C. Hana Rudová, Logické programování I, 29. dubna 2012 4 CLP(FD) Výběr hodnoty JS> Obecný princip výběru hodnoty: první úspěch (succeed first) J* volíme poradí tak, abychom výběr nemuseli opakovat a ?- domain([A,B,C],1,2), A#=B+C. optimální výber A=2,B=1,C=1 je bez backtrackingu Hana Rudová, Logické programování I, 29. dubna 2012 4 CLP(FD) Výběr hodnoty JS> Obecný princip výběru hodnoty: první úspěch (succeed first) J* volíme poradí tak, abychom výběr nemuseli opakovat a ?- domain([A,B,C],1,2), A#=B+C. optimální výber A=2,B=1,C=1 je bez backtrackingu & Parametry labeling/2 ovlivnující výber hodnoty pr. labeling([down], Vars) -i- up: doména procházena ve vzrůstajícím poradí (default) -fc down: doména procházena v klesajícím poradí Hana Rudová, Logické programování I, 29. dubna 2012 4 CLP(FD) Výběr hodnoty JS> Obecný princip výběru hodnoty: první úspěch (succeed first) J> volíme poradí tak, abychom výběr nemuseli opakovat a ?- domain([A,B,C],1,2), A#=B+C. optimální výběr A=2,B=1,C=1 je bez backtrackingu & Parametry labeling/2 ovlivnující výběr hodnoty pr. 1abe1ing([down], Vars) -i- up: doména procházena ve vzrůstajícím poradí (default) down: doména procházena v klesajícím poradí Parametry labeling/2 rídící, jak je výběr hodnoty realizován step: volba mezi X #= M, X #\= M (default) viz drívější príklad u "Usporádání hodnot a proměnných" S enum: vícenásobná volba mezi všemi hodnotami v doméně podobně jako pri indomain/1 Hana Rudová, Logické programování I, 29. dubna 2012 4 CLP(FD) Výběr proměnné Obecný princip výběru proměnné: first-fail výběr proměnné, pro kterou je nejobtížnější nalézt správnou hodnotu pozdější výběr hodnoty pro tuto proměnnou by snadněji vedl k failu A výbereme proměnnou s nějměnší doménou ?- domain([A,B,C],1,3), A#<3, A#=B+C. Hana Rudová, Logické programování I, 29. dubna 2012 5 CLP(FD) Výběr proměnné Obecný princip výběru proměnné: first-fail výběr proměnné, pro kterou je nejobtížnější nalézt správnou hodnotu pozdější výběr hodnoty pro tuto proměnnou by snadněji vedl k failu vybereme proměnnou s nejmenší doménou ?- domain([A,B,C],1,3), A#<3, A#=B+C. nejlépe je zaCít s výběrem A Hana Rudová, Logické programování I, 29. dubna 2012 5 CLP(FD) Výběr proměnné Obecný princip výběru proměnné: first-fail výběr proměnné, pro kterou je nejobtížnější nalézt správnou hodnotu pozdější výběr hodnoty pro tuto proměnnou by snadněji vedl k failu A výbereme proměnnou s nějměnší doménou J* ?- domain([A,B,C],1,3), A#<3, A#=B+C. nejlépe je zaCít s výběrem A Parametry labeling/2 ovlivnující výběr proměnné -i- leftmost: nejlevější (default) M ff: s (1) nejmenší velikostí domény fd_size(Var,Size) (2) (pokud s nejmenší velikostí domény více, tak) nejlevější z nich Hana Rudová, Logické programování I, 29. dubna 2012 5 CLP(FD) Výběr proměnné Obecný princip výběru proměnné: first-fail výběr proměnné, pro kterou je nejobtížnější nalézt správnou hodnotu pozdější výběr hodnoty pro tuto proměnnou by snadněji vedl k failu vybereme proměnnou s nejmenší doménou ?- domain([A,B,C],1,3), A#<3, A#=B+C. nejlépe je zaCít s výběrem A & Parametry labeling/2 ovlivnující výběr proměnné -i- leftmost: nejlevější (default) M ff: s (1) nejmenší velikostí domény fd_size(Var,Size) (2) (pokud s nejmenší velikostí domény více, tak) nejlevější z nich S> ffc: s (1) nejmenší velikostí domény (2) největším množstvím omezením „Cekajících" na proměnné fd_degree(Var,Size) (3) nejlevější z nich min/max: s (1) nějmenší/největší hodnotou v doméně proměnné (2) nejlevnějšíz nich fd_min(Var,Min)/fd_max(Var,Max) Hana Rudová, Logické programování I, 29. dubna 2012 5 CLP(FD) rěšění (předpokládejme minimalizaci) Parametry labeling/2 pro optimalizaci: minimize(F)/maxirrrize(F) iľ Cena #= A+B+C, labeling([minimize(Cena)], [A,B,C]) Mětoda větví a mězí (branch&bound) -fc algoritmus, který implementuje proceduru pro minimalizaci (duálně pro maximalizaci) -i- uvažujeme nejhorší možnou cenu r ešení UB (nap r . cena už nalezeného rešení) pocítáme dolní odhad LB ceny cástecného r ešení LB je tedy nejlepší možná cena pro rozšír ení tohoto r ešení procházíme strom a vyžadujeme, aby prozkoumávaná větev měla cenu LB < UB pokud je LB > UB, tak víme, že v této větvi není lepší rešení a od r ízneme ji p r idává se tedy inkrementálně omezení LB#= S+D, after(Ss, Ds, End). Hana Rudová, Logické programování I, 29. dubna 2012 8 CLP(FD) Algoritmy pro řešení problému splňování podmínek (CSP) Grafová reprezentace CSP & Reprezentace podmínek & intenzionální (matematická/logická formule) J* extenzionální (výCet k-tic kompatibilních hodnot, 0-1 matice) Hana Rudová, Logické programování I, 29. dubna 2012 10 Algoritmy pro CSP Grafová reprezentace CSP Reprezentace podmínek & intenzionální (matematická/logická formule) J* extenzionální (výCet k-tic kompatibilních hodnot, 0-1 matice) Graf: vrcholy, hrany (hrana spojuje dva vrcholy) Hypergraf: vrcholy, hrany (hrana spojuje množinu vrcholU) Reprezentace CSP pomocí hypergrafu podmínek a- vrchol = promenná, hyperhrana = podmínka Hana Rudová, Logické programování I, 29. dubna 2012 10 Algoritmy pro CSP Grafová reprezentace CSP Reprezentace podmínek & intenzionální (matematická/logická formule) J* extenzionální (výCet k-tic kompatibilních hodnot, 0-1 matice) Graf: vrcholy, hrany (hrana spojuje dva vrcholy) Hypergraf: vrcholy, hrany (hrana spojuje množinu vrcholU) Reprezentace CSP pomocí hypergrafu podmínek vrchol = promenná, hyperhrana = podmínka Cl Príklad promenné x1,...,x6 s doménou {0,1} omezení c1 : x1 + x2 + x6 = 1 c2: x1 - x3 + x4 = 1 c3 : x4 + x5 - x6 > 0 c4: x2 + x5 - x6 = 0 Hana Rudová, Logické programování I, 29. dubna 2012 10 3 Algoritmy pro CSP Binární CSP M Binární CSP i* CSP, ve kterém jsou pouze binární podmínky unární podmínky zakódovány do domény proměnné JS> Graf podmínek pro binární CSP není nutné uvažovat hypergraf, stací graf (podmínka spojuje pouze dva vrcholy) Hana Rudová, Logické programování I, 29. dubna 2012 11 Algoritmy pro CSP Binární CSP M Binární CSP i* CSP, ve kterém jsou pouze binární podmínky unární podmínky zakódovány do domény promenné JS> Graf podmínek pro binární CSP a není nutné uvažovat hypergraf, stací graf (podmínka spojuje pouze dva vrcholy) & Každý CSP lze transformovat na "korespondující" binární CSP ii> Výhody a nevýhody binarizace 3 získáváme unifikovaný tvar CSP problému, rada algoritmu navržena pro binární CSP -fc bohužel ale znacné zvetšení velikosti problému Hana Rudová, Logické programování I, 29. dubna 2012 11 Algoritmy pro CSP Binární CSP M Binární CSP i* CSP, ve kterém jsou pouze binární podmínky unární podmínky zakódovány do domény promenné JS> Graf podmínek pro binární CSP a není nutné uvažovat hypergraf, stací graf (podmínka spojuje pouze dva vrcholy) & Každý CSP lze transformovat na "korespondující" binární CSP ii> Výhody a nevýhody binarizace 3 získáváme unifikovaný tvar CSP problému, rada algoritmu navržena pro binární CSP -fc bohužel ale znacné zvetšení velikosti problému JS> Nebinární podmínky a složitejší propagacní algoritmy lze využít jejich sémantiky pro lepší propagaci X príklad: all_different vs. množina binárních nerovností Hana Rudová, Logické programování I, 29. dubna 2012 11 Algoritmy pro CSP Vrcholová a hranová konzistence & Vrcholová konzistence (node consistency) NC J* každá hodnota z aktuální domény Ví promenné splnuje všechny unární podmínky s promennou Ví Hana Rudová, Logické programování I, 29. dubna 2012 12 Algoritmy pro CSP Vrcholová a hranová konzistěncě & Vrcholová konzistěncě (node consistency) NC -fc každá hodnota z aktuální domény Vi proměnné splnuje všechny unární podmínky s proměnnou Vi & Hranová konzistěncě (arc consistency) AC pro binární CSP J* hrana (Vi,Vj) jě hranově konzistěntní, právě když pro každou hodnotu x z aktuální domény Di existuje hodnota y tak, že ohodnocení [Vi = x,Vj = y] splnuje všechny binární podmínky nad Vi,Vj. Hana Rudová, Logické programování I, 29. dubna 2012 12 Algoritmy pro CSP Vrcholová a hranová konzistěncě Vrcholová konzistěncě (node consistency) NC -fc každá hodnota z aktuální domény Vi proměnné splnuje všechny unární podmínky s proměnnou Vi Hranová konzistěncě (arc consistency) AC pro binární CSP J* hrana (Vi,Vj) jě hranově konzistěntní, právě když pro každou hodnotu x z aktuální domény Di existuje hodnota y tak, že ohodnocení [Vi = x,Vj = y] splnuje všechny binární podmínky nad Vi,Vj. a hranová konzistence je směrová konzistence hrany (Vi,Vj) nezarucuje konzistenci hrany (Vj,Vi) A I 3..7 A procedure revise((i,j)) Deleted := false for V x in Dl do if neexistuje y g Dj takové, že (x,y) je konzistentní then Di := Di - {x} Deleted := true end if return Deleted end revise Hana Rudová, Logické programování I, 29. dubna 2012 13 Algoritmy pro CSP Algoritmus revize hrany & Jak udělat hranu (Vi,Vj) hranově konzistentní? -í* Z domény Di vyřadím takové hodnoty x, které nejsou konzistentní s aktuální doménou Dj (pro x neexistuje žádá hodnoty y v Dj tak, aby ohodnocení Vi = x a Vj = y spinovalo všechny binární podmínky mezi Vl a Vj) JS> procedure revise((i,j)) Deleted := false for V x in Dl do if neexistuje y g Dj takové, že (x,y) je konzistentní then Di := Di - {x} Deleted := true end if return Deleted end revise M domain([Vi,V2],2,4), Vi#< V2 Hana Rudová, Logické programování I, 29. dubna 2012 13 Algoritmy pro CSP Algoritmus revize hrany & Jak udělat hranu (Vi,Vj) hranově konzistentní? -í* Z domény Di vyradím takové hodnoty x, které nejsou konzistentní s aktuální doménou Dj (pro x neexistuje žádá hodnoty y v Dj tak, aby ohodnocení Vi = x a Vj = y spinovalo všechny binární podmínky mezi Vl a Vj) JS> procedure revise((i,j)) Deleted := false for V x in Dl do if neexistuje y g Dj takové, že (x,y) je konzistentní then Di := Di - {x} Deleted := true end if return Deleted end revise M domain([Vi, V2J,2,4), Vi#< V2 revise((1,2)) smaže 4 z Di, Hana Rudová, Logické programování I, 29. dubna 2012 13 Algoritmy pro CSP Algoritmus revize hrany & Jak udělat hranu (Vi,Vj) hranově konzistentní? -í* Z domény Di vyradím takové hodnoty x, které nejsou konzistentní s aktuální doménou Dj (pro x neexistuje žádá hodnoty y v Dj tak, aby ohodnocení Vi = x a Vj = y spinovalo všechny binární podmínky mezi Vl a Vj) JS> procedure revise((i,j)) Deleted := false for V x in Dl do if neexistuje y g Dj takové, že (x,y) je konzistentní then Di := Di - {x} Deleted := true end if return Deleted end revise JS> domain([Vi, V2],2,4), Vi#< V2 revise((1,2)) smaže 4 z Di,D2 se nezmení Hana Rudová, Logické programování I, 29. dubna 2012 13 Algoritmy pro CSP Dosažení hranové konzistence problému Jak udělat CSP hranově konzistentní? a revize je potreba opakovat, dokud se mění doména nějaké proměnné a efektivnější: opakování revizí mužeme dělat pomocí fronty pridáváme do ní hrany, jejichž konzistence mohla být narušena zmenšením domény Hana Rudová, Logické programování I, 29. dubna 2012 14 Algoritmy pro CSP Dosažení hranové konzistence problému Jak udělat CSP hranově konzistentní? Jt revize je potreba opakovat, dokud se mění doména nějaké proměnné s> efektivnější: opakování revizí mUžeme dělat pomocí fronty pridávame do ní hrany, jejichž konzistence mohla být narušena zmenšením domény Jaké hrany presně revidovat po zmenšení domény? ty, jejichž konzistence mUže být zmenšením domény proměnné narušena jsou to hrany (i,k), které vedou do proměnné Vk se zmenšenou doménou V < V k m hranu (m, k) vedoucí z proměnné Vm, která zmenšení domény způsobila, není treba revidovat (změna se jí nedotkne) Hana Rudová, Logické programování I, 29. dubna 2012 14 Algoritmy pro CSP Algoritmus AC-3 procedure AC-3(G) ____^ Vk *^ Vm Q : = ) I ) g hrany(G), í = j} % seznam hran pro revizi while Q non empty do vyber a smaž (k,m) z Q if revise((k, m)) then % pridani pouze hran, ktere Q := Q u {(í,k) g hrany(G), í = k, í = m} % dosud nejsou ve fronte end while end AC-3 Hana Rudová, Logické programování I, 29. dubna 2012 15 Algoritmy pro CSP Algoritmus AC-3 procedure AC-3(G) ____^ Vk *^ Vm Q := {(i,j) | (i,j) £ hrany(G), í = j} % seznam hran pro revizi while Q non empty do vyber a smaž (k,m) z Q if revise((k,m)) then % pridani pouze hran, ktere Q := Q u {(i,k) g hrany(G), i = k, i = m} % dosud nejsou ve fronte end while end AC-3 Pr íklad: A Víme alespon zda r ešení existuje? NE Hana Rudová, Logické programování I, 29. dubna 2012 16 Algoritmy pro CSP Je hranová konzistence dostateCná? Použitím AC odstraníme mnoho nekompatibilních hodnot a Dostaneme potom rešení problému? NE %> Víme alespon zda r ešení existuje? NE domain([X,Y,Z],1,2), X#\= Y, Y#\= Z, Z#\= X s» hranově konzistentní a nemá žádné r ešení Hana Rudová, Logické programování I, 29. dubna 2012 16 Algoritmy pro CSP Jě hranová konzistěncě dostatěcná? Použitím AC odstraníme mnoho nekompatibilních hodnot a Dostaneme potom rešení problému? NE %> Víme alespon zda r ešení existuje? NE domain([X,Y,Z],1,2), X#\= Y, Y#\= Z, Z#\= X a hranově konzistentní a nemá žádné r ešení Jaký je tedy význam AC? a někdy dá r ešení p rímo nějaká doména se vyprázdní ^ rešení neexistuje všechny domény jsou jednoprvkové ^ máme r ešení a v obecném p rípadě se alespon zmenší prohledávaný prostor Hana Rudová, Logické programování I, 29. dubna 2012 16 Algoritmy pro CSP k-konzistence Mají NC a AC něco spolecného? s> NC: konzistence jedné proměnné & AC: konzistence dvou promenných ... mUžeme pokracovat Hana Rudová, Logické programování I, 29. dubna 2012 17 Algoritmy pro CSP k-konzistence Mají NC a AC neco spoleCného? s> NC: konzistence jedné proměnné & AC: konzistence dvou promenných ... mUžeme pokracovat CSP je k-konzistěntní práve tehdy, když můžeme libovolné konzistentní ohodnocení (k-1) rUzných promenných rozšířit do libovolné k-té promenné Hana Rudová, Logické programování I, 29. dubna 2012 17 Algoritmy pro CSP k-konzistence Mají NC a AC něco společného? s NC: konzistence jedné proměnné & AC: konzistence dvou proměnných ... mUžeme pokračovat CSP je k-konzistentní práve tehdy, když mUžeme libovolné konzistentní ohodnocení (k-1) rUzných promenných rozšířit do libovolné k-té promenné 1,2,3 1,2,3 1,2,3 4 -í* Pro obecné CSP, tedy i pro nebinární podmínky Hana Rudová, Logické programování I, 29. dubna 2012 17 4-konzistentní graf Algoritmy pro CSP Silná k-konzistence 3-konzistentní graf 1,2 1,2 1,2,3 není 2-konzistentní Hana Rudová, Logické programování I, 29. dubna 2012 18 Algoritmy pro CSP Silná k-konzistence 3-konzistentní graf (1,1) lze rozšírit na (1,1,1) (2, 2) lze rozšírit na (2, 2,2) 1,2 1,2 1,2,3 není 2-konzistentní (3) nelze rozšírit (1, 3) ani (2, 3) nejsou konzistentní dvojice (nerozširujeme je) Hana Rudová, Logické programování I, 29. dubna 2012 18 Algoritmy pro CSP Silná k-konzistence 3-konzistentní graf (1,1) lze rozšírit na (1,1,1) (2, 2) lze rozšírit na (2, 2,2) 1,2 1,2 1,2,3 není 2-konzistentní (3) nelze rozšírit (1, 3) ani (2, 3) nejsou konzistentní dvojice (nerozširujeme je) & CSP je silne k-konzistentní práve tehdy, když je j-konzistentní pro každé j k-konzistence -í* Silná k-konzistence => j-konzistence V j < k -í* k-konzistence ^ silná k-konzistence Hana Rudová, Logické programování I, 29. dubna 2012 18 Algoritmy pro CSP Silná k-konzistence 3-konzistentní graf (1,1) lze rozšírit na (1,1,1) 1,2 1,2 1,2,3 není 2-konzistentní (3) nelze rozšírit (2, 2) lze rozšírit na (2, 2,2) (1, 3) ani (2, 3) nejsou konzistentní dvojice (nerozširujeme je) & CSPje silne 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 Hana Rudová, Logické programování I, 29. dubna 2012 18 Algoritmy pro CSP Konzistěncě pro nalězění rěšění Máme-li graf s n vrcholy, jak silnou konzistenci potrebujeme, abychom p rímo našli rešení? a silná n-konzistence je nutná pro graf s n vrcholy Hana Rudová, Logické programování I, 29. dubna 2012 19 Algoritmy pro CSP Konzistence pro nalezení rešení Máme-li graf s n vrcholy, jak silnou konzistenci potrebujeme, abychom prímo našli rešení? a silná n-konzistence je nutná pro graf s n vrcholy n-konzistence nestac (viz předchozí príklad) Hana Rudová, Logické programování I, 29. dubna 2012 19 Algoritmy pro CSP Konzistence pro nalezení řešení Máme-li graf s n vrcholy, jak silnou konzistenci potřebujeme, abychom přímo našli řešení? a silná n-konzistence je nutná pro graf s n vrcholy n-konzistence nestací (viz predchozí príklad) silná k-konzistence pro k Využívá se sémantika podmínek speciální typy konzistence pro globální omezení ±* viz all_distinct a konzistence mezí propagace pouze p r i změně nejmenší a největší hodnoty v doméně proměnné C- Pro různé podmínky lze použít mzný druh konzistence & A# B => min(A) = min(B)+1, max(B) = max(A)-1 príklad: A in 4..10, B in 6..18, A #> B min(A) = 6+1 => A in 7..10 max(B) = 10-1 => B in 6..9 Hana Rudová, Logické programování I, 29. dubna 2012 22 Algoritmy pro CSP Konzistence mezí & Bounds consistency BC: slabší než obecná hranová konzistence & podmínka má konzistentní meze (BC), práve když pro každou promennou Vj z této podmínky a každou hodnou x g Dj existuje ohodnocení zbylých proměnných v podmínce tak, že je podmínka splnena a pro vybrané ohodnocení yí promenné Ví platí min(Di) < yi < max(Di) a stací propagace pouze pri zmene minimální nebo maximální hodnoty (při zmene mezí) v doméne promenné & Konzistence mezí pro nerovnice L- A #> B => min(A) = min(B)+1, max(B) = max(A)-1 príklad: A in 4..10, B in 6..18, A #> B min(A) = 6+1 ^ A in 7..10 max(B) = 10-1 ^ B in 6..9 podobne: A #< B, A #>= B, A #=< B Hana Rudová, Logické programování I, 29. dubna 2012 22 Algoritmy pro CSP 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) Hana Rudová, Logické programování I, 29. dubna 2012 23 Algoritmy pro CSP 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) a zmena min(A)vyvolá pouze zmenu min(B) a min(C) a zmena max(A)vyvolá pouze zmenu max(B) a max(C), ... Hana Rudová, Logické programování I, 29. dubna 2012 23 Algoritmy pro CSP 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) Jt změna min(A)vyvolá pouze změnu min(B) a min(C) Jt změna max(A)vyvolá pouze změnu max(B) a max(C), ... C Príklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 ^> Hana Rudová, Logické programování I, 29. dubna 2012 23 Algoritmy pro CSP 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) a změna min(A)vyvolá pouze změnu min(B) a min(C) a změna max(A)vyvolá pouze změnu max(B) a max(C), ... C Príklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 => min(A)=1+2, max(A)=10+2 => A in 3..10 => min(B)=1-2, max(B)=10-2 => B in 1..8 Hana Rudová, Logické programování I, 29. dubna 2012 23 Algoritmy pro CSP Konzistěncě mězí a aritmětická omězění & 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) a změna min(A)vyvolá pouze změnu min(B) a min(C) a změna max(A)vyvolá pouze změnu max(B) a max(C), ... M Príklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 => min(A)=1+2, max(A)=10+2 => A in 3..10 = min(B)=1-2, max(B)=10-2 = B in 1..8 A #> 5 == min(A)=6 == A in 6..10 == min(B)=6-2 == B in 4..8 (nové vyvolání A #= B + 2) Hana Rudová, Logické programování I, 29. dubna 2012 23 Algoritmy pro CSP 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) a zmena min(A)vyvolá pouze zmenu min(B) a min(C) a zmena max(A)vyvolá pouze zmenu max(B) a max(C), ... M Príklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 => min(A)=1+2, max(A)=10+2 => A in 3..10 => min(B)=1-2, max(B)=10-2 => B in 1..8 A #> 5 ^ min(A)=6 ^ A in 6..10 => min(B)=6-2 => B in 4..8 (nové vyvolání A #= B + 2) A #\= 8 => A in (6..7) \/ (9..10) (meze stejné, k propagaci A #= B + 2 nedojde) Hana Rudová, Logické programování I, 29. dubna 2012 23 Algoritmy pro CSP 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) a změna min(A)vyvolá pouze změnu min(B) a min(C) a změna max(A)vyvolá pouze změnu max(B) a max(C), ... M Príklad: A in 1..10, B in 1..10, A #= B + 2, A #> 5, A #\= 8 A #= B + 2 => min(A)=1+2, max(A)=10+2 => A in 3..10 = min(B)=1-2, max(B)=10-2 = B in 1..8 A #> 5 == min(A)=6 == A in 6..10 == min(B)=6-2 == B in 4..8 (nové vyvolání A #= B + 2) A #\= 8 = A in (6..7) \/ (9..10) (meze stejné, k propagaci A #= B + 2 nedojde) JS* Vyzkoušejte si: A #= B - C, A #>= B + C Hana Rudová, Logické programování I, 29. dubna 2012 23 Algoritmy pro CSP Globální podmínky & Propagace je lokální a pracuje se s jednotlivými podmínkami i* interakce mezi podmínkami je pouze p res domény proměnných C Jak dosáhnout více, když je silnější propagace drahá? & Seskupíme několik podmínek do jedné tzv. globální podmínky JS> Propagaci p res globální podmínku r ešíme speciálním algoritmem navrženým pro danou podmínku C Príklady: M all_different omezení: hodnoty všech proměnných různé Jt serialized omezení: rozvržení úloh zadaných startovním casem a dobou trvání tak, aby se nep rekrývaly Hana Rudová, Logické programování I, 29. dubna 2012 24 Algoritmy pro CSP Propagace pro all_distinct -I U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro X1, X3, X6 učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 29. dubna 2012 25 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 29. dubna 2012 25 Algoritmy pro CSP Propagace pro all_distinct -I U = {X2, X4, X5}, dom(U) = {2,3,4} nelze pro X1, X1 in 5..6, X3 = 5, & Konzistence: V[X\,... ,Xk} 2, 3, 4}: X3, X6 X6 in {1} \/ (5..6) c V : card{Di u • • • u Dk} > k učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 29. dubna 2012 25 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: učitel min max {2,3,4} nelze pro X1, X3, X6 Jan 3 6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Petr 4 Konzistence: V{X1,.. .,Xk} c V : card{D1 u • • • u Dk} > k Anna 2 5 stací hledat Hallův interval I: velikost intervalu I je rovna Ota 4 poctu proměnných, jejichž doména je v I Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 29. dubna 2012 25 Algoritmy pro CSP Propagacě pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistěncě: \/{Xi,.. .,Xk} c V : card{D1 u • • • u Dk} > k stací hledat Hallův intěrval I: velikost intervalu I je rovna poctu proměnných, jejichž doména je v I Infěrěncní pravidlo U = {Xu...,Xk}, dom(U) = {Di u • • • u Dk} učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 card(U) = card(dom(U)) => Vv g dom(U), VX g (V - U),X = v Hana Rudová, Logické programování I, 29. dubna 2012 25 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: VjXi,.. .,Xk} c V : card{D1 u • • • u Dk} > k stací hledat Hallův interval I: velikost intervalu I je rovna poctu proměnných, jejichž doména je v I Inferencní pravidlo U = {Xi,...,Xk}, dom(U) = {Di u • • • u Dk} card(U) = card(dom(U)) => Vv e dom(U), VX e (V - U),X = v s» hodnoty v Hallove intervalu jsou pro ostatní promenné nedostupné učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 29. dubna 2012 25 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: \/{Xi,.. .,Xk} c V : card{D1 u • • • u Dk} > k stací hledat Hallův interval I: velikost intervalu I je rovna poctu proměnných, jejichž doména je v I InferenCní pravidlo U = {Xu...,Xk}, dom(U) = {Di u • • • u Dk} card(U) = card(dom(U)) => Vv g dom(U), VX g (V - U),X = v s» hodnoty v Hallove intervalu jsou pro ostatní promenné nedostupné učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Složitost: O(2n) - hledání všech podmnožin množiny n proměnných (naivní) Hana Rudová, Logické programování I, 29. dubna 2012 25 Algoritmy pro CSP Propagace pro all_distinct U = {X2, X4, X5}, dom(U) = {2, 3, 4}: {2,3,4} nelze pro X1, X3, X6 X1 in 5..6, X3 = 5, X6 in {1} \/ (5..6) Konzistence: V{X1,.. .,Xk} c V : card{D1 u • • • u Dk} > k stací hledat Hallův interval I: velikost intervalu I je rovna poctu proměnných, jejichž doména je v I Inferencní pravidlo U = {X1,...,Xk}, dom(U) = {D1 u • • • u Dk} card(U) = card(dom(U)) => Vv e dom(U), VX e (V - U),X = v s» hodnoty v Hallově intervalu jsou pro ostatní proměnné nedostupné Složitost: O(2n) - hledání všech podmnožin množiny n proměnných (naivní) O(nlogn) - kontrola hranicních bodu Hallových intervalu (1998) učitel min max Jan 3 6 Petr 4 Anna 2 5 Ota 4 Eva 4 Marie 1 6 Hana Rudová, Logické programování I, 29. dubna 2012 25 Algoritmy pro CSP